А.А. Вылиток, Т.К. Матвеева - Динамические структуры данных. Задание практикума. Язык Паскаль (1113471), страница 3
Текст из файла (страница 3)
Проверку условий длякорректной работы со списками реализуем в виде логических функций:function is_full(var L: list):boolean;{ возвращает истину, если длина списка максимальна,иначе – ложь}beginis_full:=L.last=maxlenend; {is_full}function is_empty(var L: list):boolean;{ возвращает истину, если список пуст, иначе – ложь}beginis_empty:=L.last=0end; {is_empty}function is_valid(var L: list;i:integer):boolean;{ возвращает истину, если в списке есть i-й элемент,иначе - ложь }beginis_valid:=(1<=i) and (i<=L.last)end; {is_valid}Опишем также логическую функцию is_present(L, x), проверяющую,есть ли элемент x в списке L.function is_present(var L: list; x: elemtype):boolean;{ возвращает истину, если элемент со значением xприсутствует в списке, иначе – ложь}var found:boolean;p:integer;beginfound:= false;p:=1;while not found and (p <= L.last) dobeginfound:= x = L.elems[p];p:= p+1end;is_present:= foundend; {is_present}Рассмотрим работу этой функции для разных случаев.
Если список L пуст(L.last=0), цикл в теле функции не выполнится ни разу, так как условиеp<=L.last ложно, и функция возвращает значение «ложь». Если элемент созначением x присутствует в списке, то переменная found после несколькихповторений тела цикла получит значение «истина», и цикл завершится, так как- 13 -условие not found станет ложным. Функция возвращает значение «истина».Наконец, если элемент отсутствует в непустом списке, то значение переменнойfound в цикле не изменится. Цикл завершится, поскольку на каждой итерациизначение p увеличивается, и условие p<=L.last станет ложным.
Значениемфункции будет «ложь».Отметим, что рассмотренная реализация списков посредством массивовпозволяет достаточно легко просматривать содержимое списка (естьвозможность непосредственного доступа к элементу по его индексу) и вставлятьновые элементы списка в его конец. Однако, при вставке элемента в серединуили при его удалении требуется перемещение всех последующих элементов.Кроме того, длина списка ограничена константой maxlen.
При достаточнобольших значениях maxlen нерационально используется оперативная память,так как размер переменной, представляющей список, пропорционален константеmaxlen, а не фактической длине списка. Таким образом, пустой списокзанимает столько же места в оперативной памяти, что и список максимальнойдлины.Реализация списков посредством цепочек динамических объектовДругой подход к реализации списков на языке Паскаль заключается вследующем. Для хранения отдельного элемента списка создается динамическийобъект – запись из двух полей, называемая звеном.
В одном из полей(информационном) располагается сам элемент, а другое поле содержит ссылкуна звено, содержащее следующий элемент списка, или пустую ссылку, еслиследующего элемента нет. С помощью ссылок звенья как бы сцеплены вцепочку. Зная ссылку на первое звено можно добраться и до остальных звеньев,то есть ссылка на первое звено задаёт весь список. Пустой списокпредставляется пустой ссылкой.
Приведём соответствующие описания на языкеПаскаль.type link=↑node; { ссылка на звено }elemtype = … {подходящий для задачи тип элементов};node= record{звено состоит из двух полей:}elem: elemtype; {элемент списка}next: link{ссылка на следующее звено}end;list=link; {список задаётся ссылкой на звено }var L: list;{список}Обратим внимание на то, что в описании типа link используется имяnode, а в описании типа node используется имя link.
По правилам Паскаля взадании ссылочного типа можно укзывать имя, которое ещё не описано.Поэтому тип link описывается раньше, чем node.Пример. Список символов <'a','b','c'>, представленный цепочкойзвеньев, изображается так (в переменной L – ссылка на первое звено):- 14 -L'a''b''c'nilПри этом в программе выражение L означает ссылку на первое звено в цепочке;L↑ означает само первое звено, L↑.elem – первый элемент списка, L↑.next– ссылка на второе звено.
Далее,L↑.next↑ – само второе звено,L↑.next↑.elem – второй элемент списка,L↑.next↑.next – ссылка на третье звено,L↑.next↑.next↑ – само третье звено,L↑.next↑.next↑.elem – третий элемент списка,L↑.next↑.next↑.next – пустая ссылка (конец списка).Выражение L имеет и другой смысл. Оно обозначает список в программе,поскольку, зная ссылку на первое звено, мы имеем доступ ко всем остальнымзвеньям, т.е. «знаем» весь список. С этой точки зрения выражение L↑.next внашемпримереобозначаетсписок1<'b','c'>,авыражениеL↑.next↑.next↑.next – пустой список.Подчеркнём, что соседние звенья цепочки располагаются в оперативнойпамяти произвольно относительно друг друга, в отличие от соседних компонентмассива, всегда занимающих смежные участки памяти.
Такое расположениезвеньев облегчает операции вставки и удаления, так как нет необходимостиперемещать элементы, как это было в случае реализации списков массивами.Поясним это на примерах.Пусть из списка <'a','b','c'>, представленного в программепеременной L, требуется удалить второй элемент.
Для этого достаточноисключить из цепочки второе звено – «носитель» второго элемента. Изменимссылку в поле next первого звена: L↑.next:= L↑.next↑.next. Теперьпосле первого звена в цепочке идёт звено, содержащее элемент 'c'.Получился список <'a','c'>. Чтобы исключённое звено не занимало места впамяти, его следует уничтожить процедурой dispose, предварительнозапомнив ссылку на него во вспомогательной переменной q. Итак,окончательное решение таково:q:=L↑.next; L↑.next:= L↑.next↑.next; dispose(q).Покажем на рисунке происходящие после каждого действия изменения.{q:=L↑.next}L'a''b''c'nilq1По правилам Паскаля имена link и list обозначают один и тот же тип, и мы вправерассматривать L↑.next как переменную типа list, означающую список.- 15 -{ L↑.next:= L↑.next↑.next }'a'L'c''b'nilq{ dispose(q)}L'a''c'nilqПусть теперь требуется вставить 'd' после первого элемента списка<'a', 'c'>.
Решение состоит из двух этапов. Во-первых, необходимо создать«носитель» – звено для хранения вставляемого элемента, и занести этот элементв поле elem «носителя». Во-вторых, путём изменения указателей включитьсозданное звено в цепочку после первого звена. Первый этап реализуетсяфрагментом new(q);q↑.elem:= 'd', где q – вспомогательная переменнаятипа link. Фрагмент q↑.next:= L↑.next; L↑.next:=q осуществляетвторой этап вставки. Следующий рисунок иллюстрирует этапы вставки.{ new(q);q↑.elem:=’d’ }Lq'a''c''d'- 16 -nil{ q↑.next:= L↑.next; L↑.next:=q }Lq'a''c'nil'd'Из примеров видно, что длина цепочки (количество звеньев в ней) можетдинамически изменяться, т.е.
изменяться в процессе выполнения программы.Подобно цепочкам можно сконструировать и более сложные структуры, вкоторых объекты связаны между собой с помощью ссылок. Такого родаструктуры данных называются динамическими.Приведём реализацию некоторых операций над списками.function is_empty(L: list):boolean;{ возвращает истину, если список пуст, иначе – ложь}beginis_empty:= L = nilend; {is_empty}function is_valid(L: list; i:integer):boolean;{ возвращает истину,если в списке есть i-й элемент,иначе - ложь }var p: link; k:integer;beginp:=L; k:=1;while (p< > nil) and (k<=i) dobegin p:=p↑.next; k:=k+1 end;is_valid:=(k>i) and (i>0)end; {is_valid}Рассмотрим работу функции is_valid для разных случаев.
Если список Lпуст (L = nil), цикл в теле функции не выполнится ни разу, так как условиеp < > nil ложно. Значение переменной k равно единице, поэтому выражение(k>i) and (i>0) ложно для любого i. Функция возвратит значение «ложь».Если i<1, то цикл также ни разу не выполнится, так как при начальномзначении k, равном единице, отношение k<=i ложно. Отношение i>0 такжеложно, следовательно, значением выражения (k>i) and (i>0) будет«ложь», т.е. функция возвращает значение «ложь».
Если i>=1 и в списке естьi-й элемент, то тело цикла выполнится ровно i раз. Переменная k получит- 17 -значение i+1, выражение (k>i) and (i>0) истинно, и функция возвращаетзначение «истина». Наконец, если i>=1 и в списке нет i-го элемента, товыход из цикла произойдёт из-за ложности выражения p < > nil (подостижении конца списка). При этом выражение k<=i останется истинным.Следовательно, k>i ложно и (k>i) and (i>0)ложно.
Значением функциибудет «ложь».function ref(L: list; x: elemtype):link;{ возвращает ссылку на звено, содержащее элемент x,еслиx входит в список L, иначе – nil }var p: link; found: boolean;beginfound:=false; p:=L;while not found and (p< > nil) doif x = p↑.elem then found:=trueelse p:=p↑.next;ref:=p ;end; {ref}procedure insert(var L: list; x,y: elemtype);{ вставляет в список L элемент y после элемента x, еслиx входит в список }var p,q: link;beginp:=ref(L,x);if p < > nil thenbegin q:= p↑.next;new(p↑.next)p↑.next↑.elem:= y;p↑.next↑.next:= qendend; {insert}procedure delete(var L: list; x elemtype);{ удаляет из списка L элемент, следующий за x, еслиx входит в список и x – не последний элемент в списке}var p,q: link;beginp:=ref(L,x);if p< >nil thenbegin q:=p↑.next;if q<>nil thenbegin p↑.next:= q↑.next; dispose(q)endendend; {delete}- 18 -procedure destruct(L: list);{ разрушает список L,освобождая память, занимаемуюзвеньями }var q: link;beginwhile L < > nil dobegin q:=L;L:=L↑.next;dispose(q)endend; {destruct}Формальный параметр процедуры destruct описан как параметрзначение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
