Динамические структуры данных: списки (стр. 2 из 2)
Здесь 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;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;} |
Пример. Составить программу, которая на основе заданного списка формирует два других, помещая в первый из них положительные, а во второй — отрицательные элементы исходного списка.
При реализации алгоритма будем использовать подпрограммы разработанного модуля. Это существенно облегчает решение задачи.
{Программа на Turbo Pascal}
Program Ex_sp_1;
Uses Spisok;
Var S1, S2, S3, V1, V2, V3 : U; A : BT; I, N : Byte;
Begin
Randomize;
N := 1 + Random(20);
S1 := Nil; A := -100 + Random(201);
V_Nachalo(S1, A); V1 := S1;
For I := 2 To N Do
Begin A := -100 + Random(201); V_Spisok(V1, A); V1 := V1^.Next End;
WriteLn('Исходныйсписок: '); Print(S1);
V1 := s1; S2 := Nil; S3 := Nil;
While V1 <> Nil Do
Begin
If V1^.Inf > 0
Then If S2 = Nil
Then Begin V_Nachalo(S2, V1^.Inf); V2 := S2 End
Else Begin V_Spisok(V2, V1^.Inf); V2 := V2^.Next End;
If V1^.Inf < 0
Then If S3 = Nil
Then Begin V_Nachalo(s3, V1^.Inf); V3 := S3 End
Else Begin V_Spisok(V3, V1^.Inf); V3 := V3^.Next End;
V1:= V1^.Next
End;
WriteLn('Результирующий список из положительных элементов: '); Print(S2);
WriteLn('Результирующий список из отрицательных элементов: '); Print(S3);
Ochistka(S1); Ochistka(S2); Ochistka(S3);
End.
// Программа на C++
#include "SPIS.CPP"
void main()
{Zveno *S1, *S2, *S3, *V1, *V2, *V3;
BT a; int i, n;
clrscr();
randomize();
S1=NULL;
// создаём первый элемент
a=-100+random(201);
S1=V_Nachalo(S1, a);
n=1+random(20);
// формируем список произвольной длины и выводим на печать
V1=S1;
for (i=2; i<=n; i++)
{
a=-100+random(201);
V1=V_Spisok(V1, a);
}
Print(S1);
V1 = S1; S2 = NULL; S3 = NULL;
while (V1)
{if (V1->Inf > 0)
if (!S2)
{S2=V_Nachalo(S2, V1->Inf); V2 = S2;}
else {V_Spisok(V2, V1->Inf); V2 = V2->Next;};
if (V1->Inf < 0)
if (!S3)
{S3=V_Nachalo(S3, V1->Inf); V3 = S3;}
else {V_Spisok(V3, V1->Inf); V3 = V3->Next;};
V1= V1->Next;}
cout << "Результирующий список из положительных элементов: \n";
Print(S2);
cout << "Результирующий список из отрицательных элементов: \n";
Print(S3);
S1=Ochistka(S1); S2=Ochistka(S2); S3=Ochistka(S3);
}
Контрольные вопросы и задания
Чем отличаются статические и динамические величины?
Какая память называется динамически распределяемой?
Что такое указатель?
Какие виды указателей вам известны?
Как определяется адрес переменной?
Приведите примеры объявления указателей.
Как выделить память под динамическую переменную? Как освободить память от динамической переменной?
Что такое "разыменование"?
Что в языке Pascal обозначает константа Nil (в языке C константа NULL)?
В каком случае возможно присваивание указателей?
Какие ситуации приводят к возникновению в динамически распределяемой памяти "мусора"?
Что понимают под "связанным списком"?
Как классифицируют связанные списки?
Какие основные действия над списками и компонентами списков обычно реализуют?
Как описывается список?
Двунаправленный список объявлен следующим образом:
Type BT = Byte;
U = ^Zveno;
Zveno = Record Inf : BT; Pred, Next: U End;
Здесь Pred, Next — соответственно указатели на предыдущее и последующее звенья списка. Разработать основные подпрограммы для обслуживания такого списка.