Динамические структуры данных: списки
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;
}
Пример. Составить программу, которая на основе заданного списка формирует два других, помещая в первый из них положительные, а во второй — отрицательные элементы исходного списка.
При реализации алгоритма будем использовать подпрограммы разработанного модуля. Это существенно облегчает решение задачи.
{Программа на 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 — соответственно указатели на предыдущее и последующее звенья списка. Разработать основные подпрограммы для обслуживания такого списка.