В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 62
Текст из файла (страница 62)
В связи с этим списки подобного рода называюткольцевымисписками.Чтобы сослаться на двунаправленный кольцевой список как на единыйпрограммный объект, используется указатель, значением которого является ссылка на заглавное звено списка. Информационное поле заглавногозвена либо вообще не используется, либо может служить для храненияпризнака того, что это есть заглавное звено, и некоторой информациио списке в целом, например о количестве звеньев в списке (если типыполей позволяют хранить в них эту информацию).Следует заметить, что предложенный выше способ образования двунаправленного кольцевого списка не является единственно возможным.Можно, например, не включать заглавное звено списка в кольцо:Каждый из способов образования двунаправленного кольцевого спискаимеет как положительные, так и отрицательные стороны.
Например, в первом варианте образования такого списка очень просто реализуется вставканового звена как в начало списка (после заглавного звена), так и в его конец, ибо вставка нового звена в конец списка эквивалентна его вставкеперед заглавным звеном. Однако здесь при циклической обработке элементов списка придется каждый раз проверять, не является ли очередноезвено заглавным звеном списка.
Этого недостатка лишен второй варианторганизации списка, но в этом случае труднее реализуется добавлениезвена в конец списка.Для определенности мы остановимся на первом из рассмотренныхвариантов организации двунаправленного кольцевого списка. Читателюв качестве упражнений можно порекомендовать модифицировать приводимые ниже описания процедур и паскаль-программы применительноко второму варианту организации рассмотренных здесь списков.Над списками определены те же основные операции, что и над строкой(как мы уже отмечали, строка-цепочка является частным случаем списка):— поиск элемента в списке;— вставка заданного элемента в указанное место списка;— удаление из списка заданного элемента.271Рассмотрим реализацию этих операций применительно к двунаправленномукольцевому списку.При описании процедур, реализующих основные операции над списками, будем предполагать наличие в паскаль-программе следующих описаний типов:typeЭлемсписка = {описание типа значения, являющегосяинформационной частью звена спиока};связь =• t з в е н о ;звено = r e c o r d След,Пред:связь;Элем: ЭлемспискаendВставка элемента.
Вставка элемента в список похожа на вставку элемента в строку-цепочку: сначала с помощью процедуры new надо породитьновое звено, затем значение, заданное первым фактическим параметром,надо занести в информационное поле порожденного звена, а в поля Преди След этого звена занести соответствующие ссылки. Кроме того, надоскорректировать ссылки в звеньях, между которыми должно находитьсявставляемое новое звено.Действия по вставке элемента зададим в виде описания процедурыс именем ВСПИСОК, которая имеет два формальных параметра: одиниз них (встэл) представляет вставляемый элемент (значение типа Элемсписка), а другой (элемент) — ссылку на звено, после которого необходимо вставить новый элемент.p r o c e d u r e ВСПИСОК ({вставить элемент} встэл:Элемсписка;{после звена} элемент: связь);v a r q:связь;begin{создание нового звена}new(q);{Формирование значений полей нового звена}q t.Элем:=встэл;q + .След:=элемент + .След; q t.Пред:"элемент + .След+.Пред;{корректировка ссылок у соседних звеньев}элемент+.След+.Пред:=q;элемент*.След:=qend(Читателю предлагается следующий контрольный вопрос: можно ли двапоследних оператора присваивания в теле процедуры поменять местами,а если нет, то почему?)Для вставки нового элемента в нач?по списка в качестве второго фактического параметра оператора процедуры с именем ВСПИСОК надо задатьссылку на заглавное звено списка, т.е.
значение указателя на этот список.Удаление элемента. Из схемы двунаправленного кольцевого спискавидно, что для исключения из него какого-либо элемента достаточно изме272нить ссылку в поле След у предшествующего ему звена и ссылку в полеПред у звена, следующего за исключаемым. Возможность двигаться поссылкам в любом направлении позволяет задавать исключаемое звеноссылкой непосредственно на само это звено. Для более экономного расходования памяти удаленное из списка звено можно уничтожить с помощьюстандартной процедуры dispose.Процедура удаления имеет единственный параметр, представляющийссылку на удаляемое звено:procedure ИЗСПИСКА(удзвено:связь);begin {изменение поля пред у следующего звена}удзвено*.СледПред:=удзвено+.Пред;{изменение поля След у предыдущего звена}удзвено+.Предt.След:=удзвено!.След;{уничтожение удаленного звена}di гроге(удзвено)endПоиск элемента.
Процедура поиска заданного элемента в списке практически не отличается от аналогичной процедуры для строки-цепочки. Дляреализации этой операции главным является умение перебирать все элементы списка, а этот перебор осуществляется с помощью ссылок, содержащихся в каждом звене — как и в строке-цепочке.
В случае двунаправленного списка этот перебор можно реализовать различными способами:двигаясь от первого элемента к последнему, от последнего к первому,двигаясь попеременно от начала списка к концу и от конца к началу и т.д.Читателю можно предложить в качестве упражнения самому дать описания различных вариантов этой процедуры. Как и в случае строки эту процедуру естественно описать в виде логической функции, которая в качествепобочного эффекта вырабатывает ссылку на звено списка, в которомнаходится искомый элемент.Следует заметить, что искомый элемент можно задавать различнымиспособами, а не только путем совпадения с заданным элементом.
Впрочем,это замечание справедливо и для строки — там искомый элемент такжеможно задавать путем определения некоторых его свойств: первая по порядку четная (нечетная) цифра, гласная буква и т.п.Если двунаправленный список кольцевой, то надо учитывать ту особенность, что у такого списка формально нет последнего элемента, посколькуфактический последний элемент также имеет ссылку на "следующий"элемент, каковым является заглавное или первое звено списка (в зависимости от способа его реализации). Для принятого нами способа логическая функция поиска заданного (в явном виде) элемента будет использовать три параметра. Формальный параметр Список представляет значениеуказателя на список (ссылку на заглавное звено), параметр Искэл представляет значение искомого элемента и параметр Место представляет ссылочную переменную, которой в качестве побочного эффекта функцииприсваивается ссылка на первое по порядку звено, содержащее заданныйэлемент.18.
В.Г. Абрамов273Такую функцию можно описать следующим образом:•function ПОИСК (Список: связь; Искэ/i: Элемсписка;var Место: связь): boolean;var p,q: связь; b: boolean;beginb:=false; р:=Список; MecTo:=nil; д:=р+.След;while (p#q)and(not b)dobegin if qt.Элем=Искзл thenbegin b:=true; Место: "=q end;q:=q t.Следend; ПОИСК:=bendЕще раз обратим внимание читателя на тот факт, что единообразие обработки всех звеньев (включая первое и последнее звенья списка) достигаетсяза счет введения в употребление заглавного звена.
Все приведенные вышеописания процедур используют факт наличия в списке заглавного звена.Теперь рассмотрим пример использования списков при решении конкретной задачи.П р и м е р 14.1. Во внешнем текстовом файле input задана строкалитер, признаком конца которой является первая по порядку точка. Требуется удалить из строки все цифры, непосредственно предшествующиекаждому вхождению буквы f, и напечатать результирующую строку. Например, если задана последовательность литер rtui234fiwe45hj987f34r, тов результате должна получиться последовательность rtuifiwe45hjf34r.Конечно, можно предложить много разных алгоритмов решения этойзадачи. Поскольку наша цель - продемонстрировать работу с такой динамической структурой данных, как двунаправленный кольцевой список,то мы выберем алгоритм, использующий эту структуру данных, хотя онможет и не быть достаточно эффективным.Итак, предлагается следующий метод решения задачи.
Сначала создадимдвунаправленный кольцевой список, элементами которого будут литерызаданной строки, а затем обработаем элементы этой структуры в соответствии с требованиями задачи, т.е. исключим все звенья, содержащие цифры,непосредственно предшествующие каждому звену с буквой f. Полученнуюпоследовательность литер выведем на печать.
Обработку элементов будемосуществлять при их последовательном переборе от первого звена к последнему.{Пример 14.1. Руденко Т.В. Ф-т ВМиК МГУ 25.4.87гИсключение всех цифр, непосредственнопредшествующих вхождениям буквы f в строке литервнешнего текстового Файла input}{Использование двунаправленного кольцевого списка}program исклцифр < i nput,output);274typeэлемспиока=сЬаг;связь=!звено;звено= recordслед: связь;пред: связь;элем: элемспискаend;кольцо=связь;varring: кольцо; rl,r: связь; sym: char;{}procedure ВСПИСОК({вставить элемент} встэл: элемсписка;{после звена} элемент: связь);var q: связь;begin{создание нового звена}new(q);{формирование значений полей нового звена}q t.элем:=встзл;q !.след:=элемент!.
след; q t.пред:=элемент !.след!,пред;{корректировка ссылок у соседних звеньев}элемент!.след!,пред:=q;элемент!.след:=qend;>{-procedure ИЗСПИСКА (удзвено:связь);begin {изменение поля пред у следующего звена}удзвено!.след!.пред:=удзвено!.пред;{изменение поля след у предыдущего звена}удзвено!.предt.след:=удзвено!.след;{уничтожение удаленного звена}di spose(удзвено)end;{>begin {создание двунаправленного кольцевого списка}{создание заглавного звена списочной структуры}new(r); г!.след:=г; г!.пред:=г; г !.
элем: «=' а ' ; ring:=r;{чтение первой литеры из внешнего Файла input}read(sym);{последовательное чтение литер и включение ихв список ring}18"275w h i l e sym*'.'dob e g i n ВСПИСОК(sym,ringt.пред); read(sym) e n d ;{установка указателя г на первое звено)г:=ri ng t.след;{последовательная обработка элементов списка)w h i l e r*ring dob e g i n {поиск очередного звена с буквой 'f ">w h i l e (гt.элем*'f')and(r*ring)do г=г+„след;i f r*ring t h e n {удаление предшествующихЦИФР)beginw h i l e rt.предt.элем in C ' O ' . . ' 9 ' ЗdoИЗСПИСКА(r +.пред);r: =r t.следendend;{печать результата}rs=ringf.след; writeln;w h i l e r*ring dobeginw r i t e ( r э л е м ) ; г:-г+.олед e n d ;wri teln;end.«Реализованный здесь алгоритм существенно использует тот факт, чтов заглавном звене в поле с именем элем находится литера-буква.
Действительно, возможен случай, когда строка представляет собой, например,следующую последовательность литер: 232443f...s678; т.е. начинаетсяи заканчивается любым числом литер-цифр. В случае, если в заглавномзвене нет литеры-буквы, алгоритм не даст правильного результата. Анализпричины, почему это произойдет, мы оставляем читателю. Кроме этого,в качестве упражнения предложите и реализуйте алгоритм, лишенныйэтого неудобства.14.2. Очереди и стекиПонятие очереди всем хорошо известно из повседневной жизни.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
