Реферат: Мультисписки

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

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

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

 

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

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

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

 

Виконав: студент гр. 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;

}

еще рефераты
Еще работы по информатике, программированию