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

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

               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 — соответственно указатели на предыдущее и последующее звенья списка. Разработать основные подпрограммы для обслуживания такого списка.

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

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

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

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