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

Posted on by — Leave a reply

Линейные
списки, изучение основных операций

Списком называется структура данных, каждый элемент
которой посредством указателя связывается со следующим элементом. Из
определения следует, что каждый элемент списка содержит как минимуму
одно поле данных (назовем его data
и для простоты считаем его типа Integer),
оно может иметь сложную структуру, и поле ссылки на следующий элемент
(назовем его next). Поле ссылки
последнего элемента списка имеет значение Nil.
Указатель на начало списка (первый элемент) является значением отдельной
переменной. Пример списка, содержащего в поле данных целые числа 3. 5,
1, 9, приведен на рисунке.

Urok12

Описание элемента списка, используемого в течение данного понятия, имеет
вид:

Основные операции с элементами списка:

  • просмотр элементов списка;

  • вставка элементов в список;

  • удаление элемента из списка;

Просмотр элементов списка, если он создан,
очевидная процедура.


Procedure Print(s:pt);


begin


While
x<>Nill do


begin


Write(x^.data, ‘ ‘);


z:=z^.next);


end;


end;

Ее рекурсивная реализация:


Procedure Print(s:pt);


begin


If
x<>Nill then


begin


Write(x^.data, ‘ ‘);


Print(z^.next);


end;


end;

Измените ее так, чтобы элементы списка выводились, начиная с последнего.

Вставка элемента в список возможна логически в его начало, конец и
середину. Разберем эти случаи. Вставка в начало имеет вид:

Urok13


Procedure Ins_begin(Var first:pt;
el:Integer);


Var new_first:pt;


begin


New(new_first); (*1*)


new_first^.next:=first; (*2*)


new_first^.data:=el;


first:=new_first; (*3*)


end;

«Красными»
отрезками на рисунке выделены действия, выполняемые в процедуре. С
помощью цифр на рисунке и в тексте процедуры показаны действия
соответствующих операторов.

Вставка в конец списка осуществляется с
помощью следующей процедуры. Вопрос о том, каким образом значением
указателя last стал адрес последнего элемента
списка, пока оставим открытым.

Urok14

Procedure
Ins_end(Var last:pt; el:Integer);

Begin

New(last^.next) ;(*1*)

last:=last^.next;(*2*)

last^.data:=el;

last^.next:=Nil;

End;

Вставку в средину списка проиллюстрируем очередным рисунком.

wpsuk91r

Очевидно, что для вставки элемента в список необходимо знать, как
минимум, адрес предшествующего элемента списка, т. е. элемента, после
которого осуществляется вставка. И мы считаем, что этот элемент не
последний. При вставке разрывается существующая связь (отмечена
«крестиком») и появляются две новые связи, выделенные на рисунке
«жирными» отрезками.

Пусть мы создаем упорядоченный по неубыванию список элементов
(информационная часть любого элемента списка меньше информационных
частей следующих за ним элементов списка или равна им). Для того, чтобы
найти место для вставки очередного элемента (значение указателя рх на
рисунке), следует просматривать элементы списка до тех пор, пока
вставляемый элемент больше информационной части текущего элемента.

Urok15

Procedure
Ins_med(Var first:pt; el:Integer);

Var
t,new_m:pt;

Begin

New(new_m);

t:=first;

While el>t^. next* .data Do
t:=t*.next;

new_m*.next;=tA.next;

new_mA. data : =e;

t*.next :=new_m;

End;

И наконец, общая логика вставки элемента в упорядоченный список.
Создаваемый список отличается от декларированного в начале тем, что он
описывается двумя указателями: на первый и последний элементы списка.

Procedure
Ins(Var first,last:pt; el:Integer);

Begin

If eKfirst».data Then
Ins_begin(first,el) Else

If el>last».data Then
Ins_end(last,el) Else Ins_med (first,el);

End;

Ввод исходных данных при создании упорядоченного списка осуществляется с
клавиатуры. Напомним, что признак конца файла (Eof = True) в этом случае
вырабатывается при нажатии клавиш Ctrl+Z. Все действия по организации
ввода представлены в процедуре Solve.

Procedure
Solve(Var first,last:pt);

Var
el:Integer;

Begin

Write(‘First element: ‘);

Read(el) ;

If Not Eof Then

Begin

first:~Nil;

Ins_begin(first,el);

last:=first;

End

Else

Begin

first:=Nil;

last:=Nil;

End;

While Not Eof Do

Begin

Write(‘Next: ‘);

Read(el);

If Not Eof Then
Ins(first,last,el);

End;

End;

Проведите несколько экспериментов и проанализируйте результаты:

маркированный список

исключите логику отдельного ввода первого элемента списка из
Solve;
маркированный список

исключите анализ признака конца файла из тела цикла While;
маркированный список

исключите переменную Last, список должен иметь только один
указатель на начало.

Действия при удалении элемента из списка различны в зависимости от места
удаляемого элемента: первый он или нет. На рисунке показано удаление
элемента из средины списка. Для сохранения структуры списка необходимо
помнить адрес элемента списка, предшествующего удаляемому элементу (dx),
а также запоминать адрес удаляемого элемента для корректного
использования процедуры Dispose.

Urok16

Приведем процедуру удаления всех элементов списка, информационная часть
которых равна заданному числу (el).

Procedure
Del_el(Var first:pt; el:Integer);

Var t,x,dx:pt;

Begin

t:=first;(*Переменная цикла. *)

While tO
Nil Do (*Пока список не
просмотрен.*)

If t^.data=el
Then (*Есть совпадение.*)

If t=first Then

Begin (*Удаляем первый элемент списка.*)

х:=first;
(*’Запоминаем,
ибо «кучу» засорять
не следует.*)

First:=first^.next;{*Изменяем
значение
указателя на первый элемент
списка.*)

Dispose(х);
(*Освобождаем место в «куче».*)

t:=first; (*Переменная цикла изменила свое значение.*)

End

Else

Begin

x:=t; (*Запоминаем адрес удаляемого элемента.*)

t:=t^.next;

dx^.next:=t;
(*Удаление
элемента не должно нарушать структуру списка, ключевой оператор
процедуры.*)

Dispose(x);

End

Else

Begin

dx:=t;

t:=t^.next;

End; (*Переход
к следующему элементу списка. Адрес текущего запоминается в переменной dx.*)
End;

Отладка
программ, использующих указатели, достаточно непростое занятие, особенно
при первом знакомстве. Рекомендуется создавать небольшой список,
например из четырех элементов 1, 2, 3, 4, и в окне Watches отслеживать
изменение всех связей. При отладке процедуры Del_el в пошаговом режиме
окно Watches может иметь в начальный момент времени следующий вид.

Watches
t^. data 1
t^.next^.data 2
t^.next^, next^, data 3
t^.next^.next^.next^.data 4
first^.data 1
firstt^.next^.data 2
firstt^.next^.next^.data 3
first».next».next».next».data 4

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *