Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






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

{Процедура удаления звена из списка после звена, на которое ссылается указатель Pred; в x содержится информация из удалённого звена} Procedure Iz_Spiska(Pred : U; Var X : BT); VarVsp : U; Begin Vsp := 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);   Implementation   Procedure V_Nachalo; VarVsp : U; Begin New(Vsp); Vsp^.Inf := X; Vsp^.Next := First; First := Vsp; End;   Procedure Iz_Nachala; VarVsp : U; Begin Vsp := First; First := First^.Next; X := Vsp^.Inf; Dispose(Vsp); End;   Procedure V_Spisok; VarVsp : U; Begin New(Vsp); Vsp^.Inf := X; Vsp^.Next := Pred^.Next; Pred^.Next := Vsp; End;   Procedure Iz_Spiska; VarVsp : U; Begin Vsp := Pred^.Next; Pred^.Next := Pred^.Next^.Next; X := Vsp^.Inf; Dispose(Vsp); End;   Procedure Ochistka; VarVsp : BT; Begin While Not Pust(First) Do Iz_Nachala(First, Vsp) End;   Function Pust; Begin Pust := First = Nil End;   Procedure Print; VarVsp : 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; structZveno{ 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"; }   intPust(Zveno *First) { return !First; }   Zveno *Ochistka(Zveno *First) { while (!Pust(First)) First=Iz_Nachala(First); returnFirst; }

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

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

{Программа на TurboPascal}

Program Ex_sp_1;

UsesSpisok;

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

ThenIf 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; inti, 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);

}

 

Контрольные вопросы и задания

  1. Чем отличаются статические и динамические величины?
  2. Какая память называется динамически распределяемой?
  3. Что такое указатель?
  4. Какие виды указателей вам известны?
  5. Как определяется адрес переменной?
  6. Приведите примеры объявления указателей.
  7. Как выделить память под динамическую переменную? Как освободить память от динамической переменной?
  8. Что такое "разыменование"?
  9. Что в языке Pascal обозначает константа Nil (в языке C константа NULL)?
  10. В каком случае возможно присваивание указателей?
  11. Какие ситуации приводят к возникновению в динамически распределяемой памяти "мусора"?
  12. Что понимают под "связанным списком"?
  13. Как классифицируют связанные списки?
  14. Какие основные действия над списками и компонентами списков обычно реализуют?
  15. Как описывается список?
  16. Двунаправленный список объявлен следующим образом:

17. Type BT = Byte;

18. U = ^Zveno;

19. Zveno = Record Inf : BT; Pred, Next: U End;

Здесь Pred, Next — соответственно указатели на предыдущее и последующее звенья списка. Разработать основные подпрограммы для обслуживания такого списка.

 

 

12

Последнее изменение этой страницы: 2016-06-09

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...