Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)
| {Процедура удаления звена из списка после звена,
на которое ссылается указатель 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);
}
Контрольные вопросы и задания
- Чем отличаются статические и динамические величины?
- Какая память называется динамически распределяемой?
- Что такое указатель?
- Какие виды указателей вам известны?
- Как определяется адрес переменной?
- Приведите примеры объявления указателей.
- Как выделить память под динамическую переменную? Как освободить память от динамической переменной?
- Что такое "разыменование"?
- Что в языке Pascal обозначает константа Nil (в языке C константа NULL)?
- В каком случае возможно присваивание указателей?
- Какие ситуации приводят к возникновению в динамически распределяемой памяти "мусора"?
- Что понимают под "связанным списком"?
- Как классифицируют связанные списки?
- Какие основные действия над списками и компонентами списков обычно реализуют?
- Как описывается список?
- Двунаправленный список объявлен следующим образом:
17. Type BT = Byte;
18. U = ^Zveno;
19. Zveno = Record Inf : BT; Pred, Next: U End;
Здесь Pred, Next — соответственно указатели на предыдущее и последующее звенья списка. Разработать основные подпрограммы для обслуживания такого списка.
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|