Реферат: Мультисписки
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ХЕРСОНСЬКИЙНАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ
КАФЕДРАІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ
Контрольнаробота
здисципліни:
«Інформаційнісистеми та структури даних»
Виконав: студент гр. 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;
Begin
New(Vsp);
Vsp^.Inf := X;
Vsp^.Next := First; {То звено, что было заглавным, становится вторым по счёту}
First := Vsp; {Новое звено становится заглавным}
End;
2. Удалениезвена из начала списка
/>
{Процедура удаления звена из начала списка;
в 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;
3. Добавлениезвена в произвольное место списка, отличное от начала (после звена, указательна которое задан)
/>
{Процедура добавления звена в список после звена,
на которое ссылается указатель 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;
}