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