А.А. Вылиток, Т.К. Матвеева - Динамические структуры данных. Задание практикума. Язык Паскаль (1113471), страница 5
Текст из файла (страница 5)
«последним вошёл – первым вышел».- 24 -procedure push (var S: stack;x:elemtype);{ положить x в стек S}begin S.top:=S.top+1;S.elems[S.top]:=xend; {push}procedure pop (var S: stack; var x:elemtype);{ взять из стека S верхний элемент и присвоить его x}begin x:=S.elems[S.top];S.top:=S.top-1;end; {pop}Перед началом работы со стеком нужно сделать его пустым. Для этого опишемпроцедуру init_stack(S):procedure init_stack (var S: stack);{ начальная установка стека }begin S.top:=0;end; {init_stack}К пустому стеку нельзя применять операцию pop, а к полному стеку нельзяприменять операцию push.
Опишем функции full_stack(S)иempty_stack(S), проверяющие стек на переполнение и пустоту.function full_stack(var S: stack):boolean;{ возвращает истину, если стек полон, иначе – ложь}beginfull_stack:=L.top=stacksizeend; {full_stack}function empty_stack (var S: stack):boolean;{ возвращает истину, если стек пуст, иначе – ложь}beginempty_stack:=L.top=0end; {empty_stack}В некоторых алгоритмах, использующих стек, проверка на пустоту илипереполнение перед обращением к стеку не требуется, поскольку для нихдоказано, что при корректных входных данных подобных ситуаций невозникает.1 Для отладки программ, построенных по таким алгоритмам, было быудобно, чтобы процедуры pop и push сами проверяли корректность операциисо стеком и в случае ошибки сообщали о ней.
Пусть процедура error с однимпараметром – строкой – печатает эту строку и приводит к завершениюпрограммы. Дадим соответствующие описания push и pop .1В задаче 9 раздела «Примеры задач с решениями» описан алгоритм, использующий стек, вкотором при корректных входных данных попытка взять элемент из пустого стека исключена.См. также замечание в решении задачи 10 в том же разделе.- 25 -procedure push (var S: stack;x:elemtype);{ положить x в стек S с контролем переполнения}beginif S.top=stacksize then error('стек полон')else beginS.top:=S.top+1;S.elems[S.top]:=xendend; {push}procedure pop (var S: stack; var x:elemtype);{ если стек непуст, взять из стека S верхний элемент иприсвоить его x, иначе сообщить об ошибке}beginif S.top=0 then error('стек пуст ')else beginx:=S.elems[S.top];S.top:=S.top-1;endend; {pop}После того, как программа отлажена, проверки становятся ненужными и ихследует исключить в целях повышения быстродействия программы.Заметим, что в случаях, когда максимальный размер стека не может бытьзаранее определён, лучше воспользоваться реализацией на основе динамическихцепочек.
Тогда размер ограничивается только ресурсами вычислительнойсреды.Представление очереди с помощью списка с заглавным звеномПоскольку операции вставки и удаления осуществляются на разных концахочереди, для работы с ней удобно иметь два указателя – на заглавное и напоследнее звенья.
Если очередь пуста, оба указателя ссылаются на заглавноезвено. Приведём необходимые описания.type link =↑node; { ссылка на звено }elemtype = … {подходящий тип элементов очереди};node= recordelem: elemtype; {элемент }next: link{ссылка на следующее звено}end;queue = recordfront: link {ссылка на заглавное звено};rear: link {ссылка на последнее звено}end;var Q: queue;{очередь}- 26 -{ init_queue(Z) }ZZnilZ1{ enqueue(Z,1) }nilZ{ enqueue(Z,2) }2nil1Zy121nil{ dequeue(Z,y) }Рис.
2аprocedure init_queue(var Q: queue);{ начальная установка очереди }begin new(Q.front);{создание заглавного звена}Q.front↑.next:=nil;Q.rear := Q.front;end; {init_queue}function empty_queue(Q: queue):boolean;{ возвращает истину, если очередь пуста, иначе – ложь}beginempty_queue:= Q.rear = Q.frontend; {empty_queue}procedure enqueue(var Q: queue; x:elemtype);{поставить в очередь Q элемент х}beginnew(Q.rear↑.next);Q.rear:= Q.rear↑.next;Q.rear↑.elem:=x;- 27 -Q.rear↑.next:= nilend; {enqueue}procedure dequeue(var Q: queue; var x:elemtype);{взять из очереди Q элемент и присвоить х}var p:link;beginx:= Q.front↑.next↑.elem;p:= Q.front;Q.front:= Q.front↑.next;dispose(p)end; {dequeue}Пусть в основной программе описаны переменные: Z – очередь целыхчисел, y – целое.
На рисунке 2а показан результат последовательногоприменения команд init_queue(Z), enqueue(Z,1), enqueue(Z,2),dequeue(Z,y). На рисунке 2б подробно изображён процесс выполненияпоследней команды. Как видим, после исключения из очереди единицаоказалась в поле elem заглавного звена, перестав быть частью очереди.При необходимости контролировать корректность использованияочереди во время отладки программы, в процедуру dequeue можно добавитьобращение к процедуре error при попытке взять элемент из пустой очереди.Примеры задач с решениямиВ задачах 1-8 используются списки без заглавного звена при следующемих описании:type link=↑node; { ссылка на звено }elemtype = … {подходящий для задачи тип элементов};node= record{звено состоит из двух полей:}elem: elemtype; {элемент списка}next: link{ссылка на следующее звено}end;list=link; {список задаётся ссылкой на звено }Задача 1.
Описать процедуру create(L), которая создаёт список L из строкитекстового файла input.Решениеprocedure create(var L:list);{создает список из символов строки текстового файлаinput; elemtype=char}- 28 -yZ{ dequeue(Z,y) }2nil1procedure dequeue(var Q: queue;var x:elemtype);var p:link;xbeginQx:= Q.front↑.next ↑.elem; pp:=Q.front;xQpQ.front:= Q.front↑.next;xQpdispose(p)end; {dequeue}y1Z21y1Z2Zy1nil211nilРис. 2бvar p: link;beginwrite('=>'); {выводим приглашение для ввода строки}if eoln then {пустая строка - список пуст}L:=nilelsebegin {создаем первое звено}new(p); read(p↑.elem);L:=p;- 29 -nilwhile not eoln dobegin {добавляем в список следующее звено}new(p↑.next); read(p↑.next↑.elem );p:=p↑.next{p указывает на добавленное звено }end;{ последнее звено должно иметь ссылку nil }p↑.next:=nilend ;readln {пропускаем маркер конца строки}end;Задача 2. Описать процедуру print(L), которая печатает все элементы спискаL.
Тип элементов – char.Решениеprocedure print(L:list);{печатает в файл output строку из элементов списка L}beginwhile L<>nil dobegin write(L↑.elem);L:=L↑.nextend;writelnend;Рекурсивное решение было приведено в разделе «Рекурсивная обработкасписков».Задача 3. Описать процедуру exchange(L), которая меняет первый ипоследний элементы непустого списка L.Решениеprocedure exchange(L:list);{ меняет местами элементы первого и последнего звеньевнепустого списка L}var e: elemtype;p: link;beginp:=L; {находим последнее звено}while p↑.next<>nil do p:=p↑.next;{теперь p указывет на последнее звено;L указывает на первое}{меняем местами первый и последний элементы}e:=L↑.elem; L↑.elem:=p↑.elem; p↑.elem:=eend;- 30 -Задача 4.
Описать функцию equal(L1,L2), которая проверяет на равенствосписки L1 и L2.РешениеЕсли хотя бы один из списков пуст, то в качестве результата функцииможно взять значение выражения L1 = L2. Действительно, если оба спискапусты (т.е. L1 = nil и L2 = nil), то они равны и выражение L1 = L2 даётзначение «истина»; если один пуст, другой не пуст (т.е. списки не равны), тозначением выражения будет «ложь». В случае, когда оба списка не пусты,нужно организовать цикл, в котором два указателя L1 и L2 будут синхронно«пробегать» по звеньям обоих списков, начиная с первых звеньев.
Выход изцикла происходит, если достигнуто последнее звено хотя бы в одном изсписков (т.е. L1↑.next = nil или L2↑.next = nil) или найдены звенья сразличающимисяэлементами(L1↑.elem < > L2↑.elem).Есливыходпроизошёл из-за неравенства элементов, то результат функции – «ложь». Еслиже элементы равны, то результат зависит от того, указывают ли оба указателяL1 и L2 на последние звенья. Это можно проверить с помощью выраженияL1↑.next = L2↑.next, которое принимает значение «истина» если и толькоесли L1↑.next = nil и L2↑.next = nil.function equal(L1,L2:list): boolean;{возвращает истину, если списки L1 и L2 равны, иначе –ложь}beginif (L1 = nil) or (L2 = nil)then equal:= L1=L2 {истина, если и только если обасписка пусты}else {оба списка непусты; L1 и L2 синхронно пробегаютзвенья списков}beginwhile (L1↑.next<>nil) and (L2↑.next<>nil)and (L1↑.elem=L2↑.elem){пока не достигли последнего звена в каком-либоиз списков и текущие элементы списков равны,переходим в каждом из списков к следующему звену}do begin L1:=L1↑.next; L2:=L2↑.next end;equal:=(L1↑.next=L2↑.next) and (L1↑.elem=L2↑.elem){истина, если и только если L1 и L2 указывают напоследние звенья и элементы в этих звеньях равны}endend;Задача 5.
Описать процедуру reverse(L), которая переворачивает список L,то есть первый элемент списка становится последним, второй – предпоследними т. д., бывший последним становится первым.Решение- 31 -Для решения данной задачи достаточно изменить ссылки так, чтобызвенья в цепочке расположились в обратном порядке. Для этого в поле nextпервого звена следует записать nil, тем самым сделав его последним; в полеnext второго звена записать ссылку на бывшее первое звено и далееаналогично поступать с остальными звеньями, пока не дойдём до последнего.Чтобы бывшее последним звено стало первым, надо присвоить ссылку на негопеременной L, представляющей список.procedure reverse(var L:list);{ переворачивает список L, т.е. изменяет ссылки в этомсписке так, чтобы его элементы оказались расположеннымив обратном порядке }var p,q:link;beginif L<>nil {если L=nil, результатом будет пустой список}thenbegin p:=L; q:=L↑.next;L↑.next:=nil; {первое звено становится последним}while q<>nil {пока есть следующее звено} dobegin L:=q; {перешли к новому звену; L – указывает на текущее звено, p – на предыдущее }q:=q↑.next; {запомнили ссылку на хвостсписка }L↑.next:=p; {соединили текущее звено спредыдущим}p:=L {запомнили ссылку на текущее звено}endendend;Задача 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
