Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Контрольная работа: Мультисписки

Название: Мультисписки
Раздел: Рефераты по информатике
Тип: контрольная работа Добавлен 13:44:56 04 декабря 2010 Похожие работы
Просмотров: 6 Комментариев: 14 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно     Скачать

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ

КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ

Контрольна робота

з дисципліни:

«Інформаційні системи та структури даних»

Виконав:студент гр. 4зКСМ2

Авраменко І.

Перевірив: Везумський О.К.

Херсон - 2009

Тема : Мультисписки

В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи, каждая из которых требует, возможно, обработки не всего множества объектов, а лишь какого-то его подмножества. Так, например, в автоматизированной системе учета лиц, пострадавших вследствие аварии на ЧАЭС, каждая запись об одном пострадавшем содержит более 50 полей в своей информационной части.

Решаемые же автоматизированной системой задачи могут потребовать выборки, например:

· участников ликвидации аварии;

· переселенцев из зараженной зоны;

· лиц, состоящих на квартирном учете;

· лиц с заболеваниями щитовидной железы;

· и т.д., и т.п.

Рис.5.11. Пример мультисписка


Для того, чтобы при выборке каждого подмножества не выполнять полный просмотр с отсеиванием записей, к требуемому подмножеству не относящихся, в каждую запись включаются дополнительные поля ссылок, каждое из которых связывает в линейный список элементы соответствующего подмножества. В результате получается многосвязный список или мультисписок, каждый элемент которого может входить одновременно в несколько односвязных списков. Пример такого мультисписка для названной нами автоматизированной системы показан на рис.5.11.

К достоинствам мультисписков помимо экономии памяти (при множестве списков информационная часть существует в единственном экземпляре) следует отнести также целостность данных - в том смысле, что все подзадачи работают с одной и той же версией информационной части и изменения в данных, сделанные одной подзадачей немедленно становятся доступными для другой подзадачи.

Каждая подзадача работает со своим подмножеством как с линейным списком, используя для этого определенное поле связок. Специфика мультисписка проявляется только в операции исключения элемента из списка. Исключение элемента из какого-либо одного списка еще не означает необходимости удаления элемента из памяти, так как элемент может оставаться в составе других списков. Память должна освобождаться только в том случае, когда элемент уже не входит ни в один из частных списков мультисписка. Обычно задача удаления упрощается тем, что один из частных списков является главным - в него обязательно входят все имеющиеся элементы. Тогда исключение элемента из любого неглавного списка состоит только в переопределении указателей, но не в освобождении памяти. Исключение же из главного списка требует не только освобождения памяти, но и переопределения указателей как в главном списке, так и во всех неглавных списках, в которые удаляемый элемент входил.

Списки

Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера.

Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько будет произведено измерений.

Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое "связанный список"? Схематически он выглядит так:

Здесь Inf — информационная часть звена списка (величина любого простого или структурированного типа, кроме файлового ), Next — указатель на следующее звено списка; First — указатель на заглавное звено списка.

Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы.

Для объявления списка сделано исключение: указатель на звено списка объявляется раньше, чем само звено. В общем виде объявление выглядит так.

Type U = ^Zveno;Zveno = Record Inf : BT; Next: U End;

Здесь BT — некоторый базовый тип элементов списка.

Если указатель ссылается только на следующее звено списка (как показано на рисунке и в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья — двунаправленным списком. Если указатель в последнем звене установлен не в Nil, а ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки.

Более подробно рассмотрим работу со связанными списками на примере однонаправленного некольцевого списка.

Выделим типовые операции над списками:

· добавление звена в начало списка;

· удаление звена из начала списка;

· добавление звена в произвольное место списка, отличное от начала (например, после звена, указатель на которое задан);

· удаление звена из произвольного места списка, отличного от начала (например, после звена, указатель на которое задан);

· проверка, пуст ли список;

· очистка списка;

· печать списка.

Реализуем выделенный набор операций в виде модуля. Подключив этот модуль, можно решить большинство типовых задач на обработку списка. Пусть список объявлен так, как было описано выше. Первые четыре действия сначала реализуем отдельно, снабдив их иллюстрациями.

1. Добавление звена в начало списка

{Процедура добавления звена в начало списка; в x содержится добавляемая информация}Procedure V_Nachalo(Var First : U; X : BT);Var Vsp : U;BeginNew(Vsp);Vsp^.Inf := X;Vsp^.Next := First; {То звено, что было заглавным, становится вторым по счёту}First := Vsp; {Новое звено становится заглавным}End;

2. Удаление звена из начала списка

{Процедура удаления звена из начала списка;в x содержится информация из удалённого звена}Procedure Iz_Nachala(Var First : U; Var X : BT);Var Vsp : U;BeginVsp := First; {Забираем ссылку на текущее заглавное звено}First := First^.Next; {То звено, что было вторым по счёту, становится заглавным}X := Vsp^.Inf; {Забираем информацию из удаляемого звена}Dispose(Vsp); {Уничтожаем звено}End;

3. Добавление звена в произвольное место списка, отличное от начала (после звена, указатель на которое задан)

{Процедура добавления звена в список после звена,на которое ссылается указатель Pred;в x содержится информация для добавления}Procedure V_Spisok(Pred : U; X : BT);Var Vsp : U;BeginNew(Vsp); {Создаем пустое звено}Vsp^.Inf := X; {Заносим информацию}Vsp^.Next := Pred^.Next; {Теперь это звено ссылается на то,что было следом за звеном Pred}Pred^.Next := Vsp; {Теперь новое звено встало вслед за звеном Pred}End;

4. Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)

{Процедура удаления звена из списка после звена,на которое ссылается указатель Pred;в x содержится информация из удалённого звена}Procedure Iz_Spiska(Pred : U; Var X : BT);Var Vsp : U;BeginVsp := Pred^.Next; {Забираем ссылку на удаляемое звено}{Удаляем звено из списка, перенаправив ссылку на следующееза ним звено}Pred^.Next := Pred^.Next^.Next;X := Vsp^.Inf; {Забираем информацию из удаляемого звена}Dispose(Vsp); {Уничтожаем звено}End;

Приведём полный текст модуля.

{Язык Pascal}Unit Spisok; Interface Type BT = LongInt;U = ^Zveno;Zveno = Record Inf : BT; Next: U End;Procedure V_Nachalo(Var First : U; X : BT);Procedure Iz_Nachala(Var First : U; Var X : BT);Procedure V_Spisok(Pred : U; X : BT);Procedure Iz_Spiska(Pred : U; Var X : BT);Procedure Ochistka(Var First: U);Function Pust(First : U) : Boolean;Procedure Print(First : U);ImplementationProcedure V_Nachalo;Var Vsp : U;BeginNew(Vsp);Vsp^.Inf := X;Vsp^.Next := First;First := Vsp;End; Procedure Iz_Nachala;Var Vsp : U;BeginVsp := First;First := First^.Next;X := Vsp^.Inf;Dispose(Vsp);End; Procedure V_Spisok;Var Vsp : U;BeginNew(Vsp);Vsp^.Inf := X;Vsp^.Next := Pred^.Next;Pred^.Next := Vsp;End; Procedure Iz_Spiska;Var Vsp : U;BeginVsp := Pred^.Next;Pred^.Next := Pred^.Next^.Next;X := Vsp^.Inf;Dispose(Vsp);End; Procedure Ochistka;Var Vsp : BT;BeginWhile Not Pust(First) Do Iz_Nachala(First, Vsp)End; Function Pust;BeginPust := First = NilEnd; Procedure Print;Var Vsp : U;BeginVsp := First;While Vsp <> Nil DoBeginWrite(Vsp^.Inf : 6);Vsp := Vsp^.NextEnd; WriteLnEnd; BeginEnd. // Язык С++#include < iostream.h >#include < conio.h >#include < stdlib.h >#include < time.h >typedef long BT;struct Zveno{BT Inf;Zveno *Next; }; Zveno *V_Nachalo(Zveno *First, BT X){Zveno *Vsp;Vsp = (Zveno *) malloc(sizeof(Zveno));Vsp->Inf=X; Vsp->Next=First; First=Vsp;return First;} Zveno *Iz_Nachala(Zveno *First){Zveno *Vsp;Vsp=First->Next;free(First);return Vsp;} Zveno *V_Spisok(Zveno *Pred, BT X){Zveno *Vsp;Vsp = (Zveno *) malloc(sizeof(Zveno));Vsp->Inf=X;Vsp->Next=Pred->Next;Pred->Next=Vsp;return Vsp;} BT Iz_Spiska(Zveno *Pred){BT X;Zveno *Vsp;Vsp=Pred->Next;Pred->Next=Pred->Next->Next;X=Vsp->Inf;free(Vsp);return X;} void Print(Zveno *First){Zveno *Vsp;Vsp=First;while (Vsp){cout << Vsp->Inf << ' '; Vsp=Vsp->Next;}cout << "\n";} int Pust(Zveno *First){return !First;} Zveno *Ochistka(Zveno *First){while (!Pust(First)) First=Iz_Nachala(First);return First;}
Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Olya03:02:12 27 августа 2019
.
.03:02:11 27 августа 2019
.
.03:02:10 27 августа 2019
.
.03:02:09 27 августа 2019
.
.03:02:09 27 августа 2019

Смотреть все комментарии (14)
Работы, похожие на Контрольная работа: Мультисписки

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(260264)
Комментарии (3521)
Copyright © 2005-2020 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru