Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ХЕРСОНСЬКИЙ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
КАФЕДРА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Контрольна робота
з дисципліни:
«Інформаційні системи та структури даних»
Виконав:студент гр. 4зКСМ2
Авраменко І.
Перевірив: Везумський О.К.
Херсон - 2009
В программных системах, обрабатывающих объекты сложной структуры, могут решаться разные подзадачи, каждая из которых требует, возможно, обработки не всего множества объектов, а лишь какого-то его подмножества. Так, например, в автоматизированной системе учета лиц, пострадавших вследствие аварии на ЧАЭС, каждая запись об одном пострадавшем содержит более 50 полей в своей информационной части.
Решаемые же автоматизированной системой задачи могут потребовать выборки, например:
Рис.5.11. Пример мультисписка
Для того, чтобы при выборке каждого подмножества не выполнять полный просмотр с отсеиванием записей, к требуемому подмножеству не относящихся, в каждую запись включаются дополнительные поля ссылок, каждое из которых связывает в линейный список элементы соответствующего подмножества. В результате получается многосвязный список или мультисписок, каждый элемент которого может входить одновременно в несколько односвязных списков. Пример такого мультисписка для названной нами автоматизированной системы показан на рис.5.11.
К достоинствам мультисписков помимо экономии памяти (при множестве списков информационная часть существует в единственном экземпляре) следует отнести также целостность данных - в том смысле, что все подзадачи работают с одной и той же версией информационной части и изменения в данных, сделанные одной подзадачей немедленно становятся доступными для другой подзадачи.
Каждая подзадача работает со своим подмножеством как с линейным списком, используя для этого определенное поле связок. Специфика мультисписка проявляется только в операции исключения элемента из списка. Исключение элемента из какого-либо одного списка еще не означает необходимости удаления элемента из памяти, так как элемент может оставаться в составе других списков. Память должна освобождаться только в том случае, когда элемент уже не входит ни в один из частных списков мультисписка. Обычно задача удаления упрощается тем, что один из частных списков является главным - в него обязательно входят все имеющиеся элементы. Тогда исключение элемента из любого неглавного списка состоит только в переопределении указателей, но не в освобождении памяти. Исключение же из главного списка требует не только освобождения памяти, но и переопределения указателей как в главном списке, так и во всех неглавных списках, в которые удаляемый элемент входил.
Списки
Обсудим вопрос о том, как в динамической памяти можно создать структуру данных переменного размера.
Разберем следующий пример. В процессе физического эксперимента многократно снимаются показания прибора (допустим, термометра) и записываются в компьютерную память для дальнейшей обработки. Заранее неизвестно, сколько будет произведено измерений.
Если для обработки таких данных не использовать внешнюю память (файлы), то разумно расположить их в динамической памяти. Во-первых, динамическая память позволяет хранить больший объем информации, чем статическая. А во-вторых, в динамической памяти эти числа можно организовать в связанный список, который не требует предварительного указания количества чисел, подобно массиву. Что же такое "связанный список"? Схематически он выглядит так:
Здесь Inf — информационная часть звена списка (величина любого простого или структурированного типа, кроме файлового), Next — указатель на следующее звено списка; First — указатель на заглавное звено списка.
Согласно определению, список располагается в динамически распределяемой памяти, в статической памяти хранится лишь указатель на заглавное звено. Структура, в отличие от массива, является действительно динамической: звенья создаются и удаляются по мере необходимости, в процессе выполнения программы.
Для объявления списка сделано исключение: указатель на звено списка объявляется раньше, чем само звено. В общем виде объявление выглядит так.
Type U = ^Zveno;
Zveno = Record Inf : BT; Next: U End;
Здесь BT — некоторый базовый тип элементов списка.
Если указатель ссылается только на следующее звено списка (как показано на рисунке и в объявленной выше структуре), то такой список называют однонаправленным, если на следующее и предыдущее звенья — двунаправленным списком. Если указатель в последнем звене установлен не в Nil, а ссылается на заглавное звено списка, то такой список называется кольцевым. Кольцевыми могут быть и однонаправленные, и двунаправленные списки.
Более подробно рассмотрим работу со связанными списками на примере однонаправленного некольцевого списка.
Выделим типовые операции над списками:
Реализуем выделенный набор операций в виде модуля. Подключив этот модуль, можно решить большинство типовых задач на обработку списка. Пусть список объявлен так, как было описано выше. Первые четыре действия сначала реализуем отдельно, снабдив их иллюстрациями.
|
{Процедура добавления звена в начало списка; в x содержится добавляемая информация} Procedure V_Nachalo(Var First : U; X : BT); Var Vsp : U; Begin New(Vsp); Vsp^.Inf := X; Vsp^.Next := First; {То звено, что было заглавным, становится вторым по счёту} First := Vsp; {Новое звено становится заглавным} End; |
|
{Процедура удаления звена из начала списка; в x содержится информация из удалённого звена} Procedure Iz_Nachala(Var First : U; Var X : BT); Var Vsp : U; Begin Vsp := First; {Забираем ссылку на текущее заглавное звено} First := First^.Next; {То звено, что было вторым по счёту, становится заглавным} X := Vsp^.Inf; {Забираем информацию из удаляемого звена} Dispose(Vsp); {Уничтожаем звено} End; |
|
{Процедура добавления звена в список после звена, на которое ссылается указатель Pred; в x содержится информация для добавления} Procedure V_Spisok(Pred : U; X : BT); Var Vsp : U; Begin New(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; Begin Vsp := 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); Implementation Procedure V_Nachalo; Var Vsp : U; Begin New(Vsp); Vsp^.Inf := X; Vsp^.Next := First; First := Vsp; End; Procedure Iz_Nachala; Var Vsp : U; Begin Vsp := First; First := First^.Next; X := Vsp^.Inf; Dispose(Vsp); End; Procedure V_Spisok; Var Vsp : U; Begin New(Vsp); Vsp^.Inf := X; Vsp^.Next := Pred^.Next; Pred^.Next := Vsp; End; Procedure Iz_Spiska; Var Vsp : U; Begin Vsp := Pred^.Next; Pred^.Next := Pred^.Next^.Next; X := Vsp^.Inf; Dispose(Vsp); End; Procedure Ochistka; Var Vsp : BT; Begin While Not Pust(First) Do Iz_Nachala(First, Vsp) End; Function Pust; Begin Pust := First = Nil End; Procedure Print; Var Vsp : U; Begin Vsp := First; While Vsp <> Nil Do Begin Write(Vsp^.Inf : 6); Vsp := Vsp^.Next End; WriteLn End; Begin End. |
|
// Язык С++ #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; } |