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

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

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

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

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

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

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

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

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;}