Xreferat.com » Рефераты по информатике и программированию » Динамические структуры данных: списки

Динамические структуры данных: списки

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;

}

Пример. Составить программу, которая на основе заданного списка формирует два других, помещая в первый из них положительные, а во второй — отрицательные элементы исходного списка.

При реализации алгоритма будем использовать подпрограммы разработанного модуля. Это существенно облегчает решение задачи.

{Программа на 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);

}

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: