Структуры данных и алгоритмы (1021739), страница 15
Текст из файла (страница 15)
Поскольку имя спискаявляется обязательным параметром операторов, использующих позиции элементов, спомощью имен можно различать первые позиции различных списков. ПозицияEND(L) — это индекс последнего элемента списка L.На рис. 2.5 показаны два списка, L — a,b,CTiiM = d,e, вложенные в один массивSPACE длиной 10. Отметим, что все ячейки массива, незанятые элементами списков,образуют отдельный список, называемый свободным (ниже в листингах он обозначается available). Этот список используется как "источник" пустых ячеек при вставкеэлементов в любой список, а также как место хранения перед дальнейшим использованием освободившихся (после удаления элементов) ячеек..SPACE17dсвободный234:,5678>910саеbelement4068003102nextРис. 2.5. Реализация связанных списков с использованием курсоровДля вставки элемента х в список L мы берем первую ячейку из свободного спискаи помещаем ее в нужную позицию списка L.
Далее элемент х помещается в полеelement этой ячейки. Для удаления элемента х из списка L мы удаляем ячейку, содержащую элемент х, из списка и помещаем ее в начало свободного списка. Эти двадействия являются частными случаями следующей операции. Пусть есть ячейка С,на которую указывает курсор р, необходимо сделать так, чтобы на ячейку С указывал другой курсор q, курсор ячейки С должен указывать на ячейку, на которую ранее указывал курсор q, курсор р должен указывать на ячейку, на которую до выполнения этой операции указывал курсор ячейки С. Другими словами, надо переместитьячейку из одного места списка (указываемого курсором р) в другое место того же илидругого списка, новое место указывается курсором q.
Например, если необходимоудалить элемент Ь из списка L (рис. 2.5), то С — это строка 8 в массиве SPACE, рравно SPACE[5].next, а курсор q указывает на первую ячейку свободного списка. Нарис. 2.6 схематически показан процесс перемещения ячейки С из одного списка вдругой (курсоры до и после выполнения операции показаны соответственно сплошными и пунктирными линиями). Код функции move (перемещение), выполняющейописанную операцию, приведен в листинге 2.5. Если в массиве нет ячейки С, тофункция возвращает значение false (ложь), при успешном выполнении функции возвращается значение true (истина).2.2.
РЕАЛИЗАЦИЯ СПИСКОВ55Рис. 2.6. Перемещение ячейки из одного списка в другойЛистинг 2.5. Функция перемещения ячейкиfunction move ( var p, g: integer ): boolean;vartemp-, integer;beginif p = 0 then begin { ячейка не существует }writeln('Ячейка не существует')return(false)endelse begintemp:= q;q:= p,p:= SPACE[q].next;*., ,-£PACE('q] .hext:= temp;----- return (true)endend; { move }В листинге 2.6 приведены коды процедур INSERT и DELETE, а также процедурыinitialize (инициализация), связывающей ячейки массива SPACE в свободный список.
В этих процедурах опущены проверки "нештатных" ситуаций, которые могутвызвать ошибки (оставляем написание кода этих проверок читателю в качестве упражнений). Кроме того, в Качестве упражнений оставляем читателю реализацию других операторов, выполняемых над списками (их код подобен коду аналогичных процедур при использовании указателей).Листинг 2.6. Реализация некоторых операторов списка при использовании курсоровprocedure INSERT ( х: elementtype; p: position; var L: LIST );beginif p = 0 then begin { вставка х в первую позицию }if move(available, L) thenendSPACE [L] .element :•= xelse { вставка x в позицию, отличную от первой }if.
move (available, SPACE[p] .next) thenSPACE[SPACE[p].next].element:= xend; {INSERT }56ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХprocedure DELETE ( p: position; var L: LIST );beginif p = 0 thenmoved,, available)elsemove(SPACE[p].next, available)end; { DELETE }-••••••'"•••H.'f *j .„ ^...?••""procedure initialize{ initialize связывает ячейки SPACE в один свободный список }vari: integerbeginfor i:= maxlength - 1 downto 1 doSPACE[i].next:= i + 1;available:= 1;SPAC£[maxlengt.h] .next: = 0{ помечен конец свободного списка >}'end; { initialize }Дважды связные спискиВо многих приложениях возникает необходимость организовать эффективное перемещение по списку как в прямом, так и в обратном направлениях.
Или по заданному элементу нужно быстро найти предшествующий ему и последующий элементы.В этих ситуациях можно дать каждой ячейке указатели и на следующую, и на предыдущую ячейки списка, т.е. организовать дважды связный список (рис. 2.7). В главе 12 будут приведены ситуации, когда использование дважды связных списков особенно эффективно.Рис. 2.7. Дважды связный списокДругое важное преимущество дважды связных списков заключается в том,что мы можем использовать указатель ячейки, содержащей i-Й элемент, для определения i-й позиций — вместо использования указателя предшествующейячейки.
Но ценой этой возможности являются дополнительные указатели в каждой ячейке и определенное удлинение некоторых процедур, реализующих основные операторы списка. Если мы используем указатели (а-,не курсоры), то объявление ячеек, содержащих элементы списка и два указателя, можно выполнитьследующим образом (previous — поле,, содержащее указатель на предшествующую ячейку):type...... -^.; - -='__•':'•:-.' .;Т *" :;-""..<.!.:':.."3 ,'.-х-.;" ; 'celltype = recordelement: elementtype;next, previous: t celltypeend;position = t celltype;,;:, ;,Процедура удаления элемента в позиции р дважды связного списка показана влистинге 2.7.
На рис. 2.8 Приведена схема удаления элемента в предположении, что2.2. РЕАЛИЗАЦИЯ СПИСКОВ57удаляемая ячейка не является ни первой, ни последней в списке1. На этой схемесплошными линиями показаны указатели до удаления, а пунктирными — послеудаления элемента.
В процедуре удаления сначала с помощью указателя поляprevious определяется положение предыдущей ячейки. Затем в поле next этой(предыдущей) ячейки устанавливается указатель, указывающий на ячейку, следующую за позицией р. Далее подобным образом определяется следующая за позицией рячейка и в ее поле previous устанавливается указатель на ячейку, предшествующуюпозиции р. Таким образом, ячейка в позиции р исключается из цепочек указателей ипри необходимости может быть использована повторно.Листинг 2.7.
Удаление элемента из дважды связного спискаprocedure DELETE ( var р: position );beginif pt.previous <> nil then{ удаление ячейки, которая не является первой }рТ.previous?.next:= pt.next;if pf.next <> nil then{ удаление ячейки, которая не является последней }pT.nextt.previous:= pt.previousend; { DELETE }Рис. 2.8. Схема удаления ячейки в дважды связном списке2.3.
СтекиСтек — это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). Стеки также иногда называют "магазинами", а в англоязычной литературе для обозначения стеков еще используется аббревиатура LIFO (last-in-first-out — последний вошел — первый вышел).
Интуитивными моделями стека могут служить колода карт на столе при игре впокер, книги, сложенные в стопку, или стопка тарелок на полке буфета; во всех этихмоделях взять можно только верхний предмет, а добавить новый объект можно,только положив его на верхний. Абстрактные типы данных семейства STACK (Стек)обычно используют следующие пять операторов.1.2.MAKENULL(S). Делает стек S пустым.TOP(S).
Возвращает элемент из вершины стека S. Обычно вершина стека идентифицируется позицией 1, тогда TOP(S) можно записать в терминах общих операторов списка как RETRIEVE(FIRST(S), S).POP(S). Удаляет элемент из вершины стека (выталкивает из стека), в терминахоператоров списка этот оператор можно записать как DELETE(FIRST(S), S).3.1В этой связи отметим, что на практике обычно делают так, что ячейка заголовка дваждысвязного списка "замыкает круг" ячеек, т.е. указатель поля previous ячейки заголовка указываетна последнюю ячейку, а указатель поля next — на первую. Поэтому при такой реализации дважды связного списка нет необходимости в выполнении проверки на "нулевой указатель".58ГЛАВА 2. ОСНОВНЫЕ АБСТРАКТНЫЕ ТИПЫ ДАННЫХИногда этот оператор реализуется в виде функции, возвращающей удаляемыйэлемент.4.PUSH(;e, S).
Вставляет элемент х в вершину стека S (заталкивает элемент встек). Элемент, ранее находившийся в вершине стека, становится элементом,следующим за вершиной, и т.д. В терминах общих операторов списка данныйоператор можно записать как INSERT(*, FIRST(S), S).5. EMPTY(S). Эта функция возвращает значение true (истина), если стек S пустой,и значение false (ложь) в противном случае.Пример 2.2. Все текстовые редакторы имеют определенные символы, которыеслужат в качестве стирающих символов (erase character), т.е. таких, которые удаляют (стирают) символы, стоящие перед ними; эти символы "работают" как клавиша<Backspace> на клавиатуре компьютера.
Например, если символ # определен стирающим символом, то строка afrc#d##e в действительности является строкой ае.Здесь первый символ # удаляет букву с, второй стирающий символ стирает букву d,а третий — букву Ъ.Текстовые редакторы имеют также символ-убийцу (kill character), который удаляет все символы текущей строки, находящиеся перед ним. В этом примере в качествесимвола-убийцы определим символ @.Операции над текстовыми строками часто выполняются с использованием стеков.Текстовый редактор поочередно считывает символы, если считанный символ не является ни символом-убийцей, ни стирающим символом, то он помещается в стек. Если вновь считанный символ — стирающий символ, то удаляется символ в вершинестека.
В случае, когда считанный символ является символом-убийцей, редакторочищает весь стек. В листинге 2.7 представлена программа, выполняющая описан1ные действия.Листинг 2.7. Программа, реализующая действия стирающего символаи символа-убийцыprocedure EDIT;varS: STACK;с: char;beginMAKENULL(S);while not eoln do beginread(c);if с = '#' thenPOP(S)else if с = '@' thenMAKENULL(S);else { с — обычный символ }PURSH(c, S)end;печать содержимого стека S в обратном порядкеend; { EDIT }В этой программе тип STACK можно объявить как список символов. Процесс вывода содержимого стека в обратном порядке в последней строке программы требуетнебольшой хитрости. Выталкивание элементов из стека по одному за один раз впринципе позволяет получить последовательность элементов стека в обратном порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
