Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Удаление звена из произвольного места списка, отличного от начала (после звена, указатель на которое задан)
|
|
| {Процедура удаления звена из списка после звена, на которое ссылается указатель Pred; в x содержится информация из удалённого звена} Procedure Iz_Spiska(Pred: U; Var X: BT); Var Vsp: 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; Var 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);
}
Контрольные вопросы и задания
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 — соответственно указатели на предыдущее и последующее звенья списка. Разработать основные подпрограммы для обслуживания такого списка.
|
|