А.А. Вылиток, Т.К. Матвеева - Динамические структуры данных. Задание практикума. Язык Паскаль (1113471), страница 4
Текст из файла (страница 4)
Следовательно, на месте фактического параметра при обращении кэтой процедуре может быть любое ссылочное выражение. Например, вызовфункции, которая возвращает ссылку на первое звено списка или nil.Пусть переменные L1 и L2 имеют одинаковые значения – ссылку напервое звено некоторого списка. Чтобы сделать список L1 (и L2) пустым,понадобится такой фрагмент: destruct(L1); L1:=nil; L2:=nil.
Послевыполнения оператора destruct(L1) значения обеих переменных L1 и L2 неопределены, но после операторов присваивания их значением становится пустаяссылка, т.е. L1 (и L2) представляют теперь пустой список.Как уже отмечалось, операции вставки и удаления при реализациисписков цепочками требуют меньше действий, чем при реализации массивами,так как не требуется перемещать элементы, следующие за вставляемым (илиудаляемым). Поэтому данная реализация больше подходит для задач, в которыхизменения в списках происходят часто. Кроме того, в ней нет ограничения надлину списка (максимальная длина зависит только от ресурсов вычислительнойсистемы); эффективнее используется память (занимаемый объём памятипропорционален текущей длине списка).Недостатками данной реализации являются необходимость хранить взвеньях дополнительную информацию – ссылки, а так же отсутствие прямогодоступа к i-му элементу списка.
Если нужно присвоить переменной x значениеi-го элемента списка L, то в случае реализации массивами это делается однимоператором x:=L.elems[i], а при реализации цепочками понадобитсяфрагмент, содержащий цикл: p:=L; for k:=1 to i-1 do p:=p↑.next;x:= p↑.elem. По этой причине в задачах, где списки меняются сравнительноредко, а просмотр элементов осуществляется часто, выгоднее использоватьреализацию с помощью массивов.Цепочку динамических объектов, реализующую список, называютоднонаправленным списком.
В литературе по программированию под термином«список» часто подразумевается именно однонаправленный список. Данноезначение термина обычно имеется в виду и тогда, когда употребляютвыражение «звено списка». В некоторых задачах важно уметь продвигаться посписку не только от начала к концу, но и в обратном направлении. Для этогоиспользуются двунаправленные списки.
Звено двунаправленного спискасодержит две ссылки – на следующее и на предыдущее звенья. Эта особенность- 19 -должна учитываться при реализации операций (например, вставки, удаления)для двунаправленных списков. Ещё один вариант реализации списков в видединамических цепочек – так называемые списки с заглавным звеном –рассматривается в следующем подразделе.Списки с заглавным звеномЕсли в начало обычного однонаправленного списка добавитьдополнительное звено, не содержащее элемента (т.е. поле elem в этом звене неопределено), то получим список с заглавным звеном. Пример:L'a''b'nilДля таких списков некоторые алгоритмы обработки записываютсяпроще, так как в списке всегда есть хотя бы одно звено (даже если он пуст).Пусть надо реализовать операцию вставки в конец списка L элемента х.Сравним решения для списка без заглавного звена и для списка с заглавнымзвеном:procedure insert1(var L: list; x: elemtype);{ вставляет в конец списка L без заглавного звенаэлемент x}var p,q: link;beginnew(q); q↑.elem:= x; q↑.next:= nil;{q указывает на созданное для вставляемого элементазвено }if L = nil then L:= q {случай пустого спискаобрабатывается отдельно}elsebegin p:= L;while p↑.next< > nil do p:= p↑.next;{p указывает на последнее звено в списке}p↑.next:= q{присоединили в конец списка новое звено}endend; {insert1}procedure insert2(L: list; x: elemtype);{ вставляет в конец списка L с заглавным звеномэлемент x}var p,q : link;beginnew(q); q↑.elem := x; q↑.next:= nil; p:= L;while p↑.next< > nil do p:= p↑.next;{p указывает на последнее звено в списке}- 20 -p↑.next := q {присоединили в конец списка новое звено}end; {insert2}Как видим, для списка с заглавным звеном нет нужды рассматривать случайL = nil отдельно.Рекурсивная обработка списковВспомним математическое определение списка: это конечнаяпоследовательностьэлементов(возможно,пустая).Внепустойпоследовательности можно выделить первый элемент – «голову»последовательности – и оставшуюся часть – «хвост».
Заметим, что «хвост» всвою очередь также является последовательностью. Таким образом, получаемрекурсивное определение последовательности:<последовательность>::= <голова> <хвост> | <пусто><голова>::=<элемент><хвост>::=<последовательность>Опираясь на это определение, можно задать рекурсивную процедуру(функцию)1 поэлементной обработки последовательности. Пусть, например,требуется напечатать список символов L (тип элементов – char). Процедурупечати можно сформулировать так: если список пуст – ничего не делать (так какнечего печатать), иначе напечатать «голову», а за ней напечатать «хвост».
Дляпечати «хвоста» используем эту же процедуру (рекурсивное применение). Нижеприводятся рекурсивные процедуры print1 и print2 для печати списковсоответственно без заглавного звена и с заглавным звеном.procedure print1 (L: list);{ печать списка без заглавного звена }begin if L <> nil thenbegin write(L↑.elem,'9'); {печать «головы»}print1(L↑.next){печать «хвоста»}end;end; {print1}procedure print2 (L: list);{ печать списка с заглавным звеном }begin if L↑.next <> nil thenbegin write(L↑.next↑.elem,'9');print2(L↑.next)end;end; {print2}1Процедуры (функции), которые во время исполнения могут прямо или косвенно (через другиепроцедуры или функции) обратиться сами к себе, называются рекурсивными.- 21 -Рассмотрим ещё одну задачу: «Не используя операторов цикла иперехода, описать функцию sum(L), вычисляющую сумму элементов спискацелых чисел L.
Считать, что сумма пустого списка равна нулю, и что списокпредставлен цепочкой звеньев без заглавного звена».Поскольку циклы запрещены условием задачи, для прохода по спискувоспользуемся рекурсией (как в реализации процедуры print1). Дадимрекурсивное определение суммы списка. Сумма пустого списка равна нулю,сумма непустого списка есть результат сложения «головы» с суммой «хвоста»:sum(L)=0, если L пуст,L↑.elem+sum(L↑.next),иначе.Теперь запишем определение функции на Паскале.function sum(L:list):integer;beginif L = nil then sum:= 0else sum:= L↑.elem +sum(L↑.next)end;{sum}Параметр L передаётся по значению.
Поэтому при каждом вызове этойфункции создаётся локальная (по отношению к данному вызову) переменная L,и ей присваивается значение фактического параметра. При выходе из функциилокальная переменная исчезает, и значение функции возвращается в точкуобращения к ней. При рекурсивном обращении могут одновременносуществовать несколько (различных !) локальных переменных с именем L (поодной для каждого вызова).
Рисунок 1 иллюстрирует выполнение оператораwrite(sum(Z))основной программы, где Z представляет список <5,-3>.Очереди и стекиВ повседневной жизни часто приходится иметь дело с хранилищамиразличных объектов. В библиотеке хранятся книги; в автоматическом оружииесть магазин, в котором хранятся патроны; в холле парикмахерской «хранятся»клиенты, ожидающие своей очереди на обслуживание. Хранилище может бытьпустым, если в данный момент никаких объектов в нём нет.
Независимо оттого, как устроено хранилище, и какие объекты в нём хранятся, можно выделитьдва основных действия для работы с ним: 1) добавить объект (положить нахранение); 2) взять объект (изъять из хранилища). Если потребовать, чтобыоперации добавления и изъятия объектов удовлетворяли некоторым условиям,можно выделить два особых типа хранилищ: очередь и стек.- 22 -…write(sum(Z));Z5-3function sum(L:list):integer;beginLif L=nil then sum:=0else sum:=L↑.elem +sum(L↑.next)end;{sum}возвращает 2function sum(L:list):integer;beginLif L=nil then sum:=0else sum:=L↑.elem +sum(L↑.next)end;{sum}возвращает -3function sum(L:list):integer;beginL nilif L=nil then sum:=0else sum:=L↑.elem +sum(L↑.next)end;{sum}возвращает 0Рис.
1В хранилищах типа «очередь» (или FIFO1) для каждого добавляемогообъекта справедливо следующее: он не может быть изъят раньше, чем любой1FIFO означает “First In – First Out”, т.е. «первым вошёл – первым вышел».- 23 -nilдругой объект, уже находящийся в данный момент на хранении. Пример –транспортёрная лента для погрузки багажа. Чемодан, раньше других попавшийна ленту, раньше других сойдёт с неё.В хранилищах типа «стек» (или LIFO2) каждый добавляемый объект неможет быть изъят позже, чем любой другой объект, уже находящийся в данныймомент на хранении.
Примеры: стопка тарелок на полке буфета; магазин вавтоматическом оружии. В этих примерах соблюдается дисциплина LIFO, таккак взять можно только верхний предмет (тарелку или патрон), а добавитьновый объект можно, только положив его на верхний.Потребность в использовании стека или очереди возникает припрограммировании многих реальных процессов и ситуаций. Рассмотрим одиниз способов организации очередей и стеков в программе. В качестве структурыданных для хранения объектов (элементов) будем использовать список.
Вслучае очереди элементы добавляются в конец списка, а удаляются из егоначала. В случае стека элементы добавляются и удаляются с одного концасписка. Такой способ представления стеков и очередей очень распространён,так что на его основе можно дать более узкие определения данных понятий:Очередь – это список, в который элементы всегда добавляются в конец, аудаляются из начала.Стек – это список, в котором все вставки и удаления выполняются наодном конце, называемом вершиной стека.Каждая из возможных реализаций списка на Паскале может бытьиспользована для представления очередей и стеков. Для стеков рассмотримвариант представления с помощью массивов, а для очередей – с помощьюдинамических цепочек.Представление стеков с помощью массивовОпишем тип данных stack и две процедуры: push(S,x) – положить встек S элемент x и pop(S,x) – взять с вершины стека S элемент, присвоив егопараметру x.conststacksize = … {максимальное число элементов, которыемогут одновременно находиться в стеке};typeelemtype = … {подходящий для задачи тип элементовстека};stack = recordelems: array [1..stacksize] of elemtype;top: integer {индекс вершины стека}end;var S: stack; {стек}2LIFO означает “Last In – First Out”, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
