Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 35
Текст из файла (страница 35)
В самом деле, рекурсивный тип, определяемый по схеме 1уре Т = — гесогс) И В Феп(уе: Тс', П Т) епс( 4.3. Линейные еннекн 199 Пусть тип Т описан, как показано в (4.11). Каждая переменная этого типа состоит из трех компонент: идентифицирующего ключа, ссылки иа следующий элемент и, возможно, другой информации, не указанной в (4.1!). 1уре Т = гесоге! 7сеу: йиепег; иехг: ( Т; (4.11) епд Список элементов типа Т показан на рис. 4.6. Переменная- ссылка р указывает на первую компоненту списка. По-видимому, самое простое действие, которос можно выполнить со Рис. 4.6 Ириыср списка.
списком, показанным на рис, 4.6,— вставить в его начало некоторый элемент. Прежде всего этот элемент типа Т размещается в памяти, ссылка на него присваивается вспомогательной ссылочиой переменной д. После этого ссылкам присванваются новые значения, как показано в (4.12): песа(д) д(.лех(:= р; р:= д (4.12) р 4=- в!1; (начало с пустого списка) Ии!с л > 0 до Ьея!влеж(д); д)лехГ:=- р; р;= д; д ! Аеу:== и; и;=- л — 1 епй (4.13) Это--самый простой способ построения списка. Но при этом полученныи порядок элементов обратен порядку их «постунлен14я» !а некоторых случаях это нежелательно; следовательно, новые элементы долакпы добавляться в конец списка. Заметим, что здесь важен порядок слсдования этих трех опсраторев.
Операция включения элемента в начало списка определяет, как можно построить такой список: начиная с пустого списка, последовательно добавлять элементы в его начало. Процесс формирования списка описан в (4.16); здесь число связываемых элементов равно и яоо 4. Динаминеские информанионные структуры Хотя конец легко найти проходом по списку, такой непосредственный подход потребовал бы затрат, которых просто избежать, используя вторую ссылку д, которая всегда указывает на последний элемент.
Такой метод применяется, например, в программе 4.4, формирующей перекрестные ссылки иа заданный текст. Недостаток такого метода состоит в том, что первый включаемый элемент приходится обрабатывать иначе, чем остальные. Явное использование ссылок намного упрощает некоторые операции, которые иначе были бы сложными и запутанными; среди элементарных действий со списками есть включение Рис. 4.7. Включсиие в список после р). и удаление элементов (выборочное изменение списка) и, ра.
зумсется, просмотр списка. Вначале мы рассмотрим включение в список. Предположим, что элемент, на который указывает ссылка д, нужно включить а список после элемента, на который указывает ссылка р. Необходимые присваивания значений ссылкам показаны в (4.14), а их результат изображен на рнс. 4,7. у).пех!:= р'~.пех1; р).пех1:= д (4.!4) Если требуется включение перед элементом, указанным рТ, а не после него, то кажется, что однонаправленная цепочка связей создает трудность, поскольку нет «прохода» к элементам, предшествующим данному. Однако простой «трюк» позволяет решить эту. проблему; ои показан в (4,1б) и на рис. 4.8. Допустим, что ключ нового элемента есть й=й.
песо(д); д1;= рТ; р)йеу:= й; р1.пех1:.=- у (4.15) «Трюк» состоит в том, что новая компонента в действительности вставляется после р1, по затем происходит обмен значениями между новым элементом и рТ. Теперь мы рассмотрим процесс удаления пз списка. Удаление элемента, следующего за рТ, очевидно. В (4.1б) оно показано в комбинации с одновременным добавлением уда- 4.3. Линейные списки 201 ляемого элемента в начало другого списка (иа которое указывает г)), причем т — вспомогательная переменная типа Т1.
т:= р).пехг; ф.пех1:= т('.ггехг; т).пеку:= д; д:= т Рггс. 4.9 иллюстрирует процесс (4.16) и показывает, что он состоит из циклического обмена значениями трех ссылок, (4, 16) Рнс. 4.8. Включение в список перед р). Труднее удалить сам указанный элемент (а не следующгф за ннм), поскольку мы сталкиваемся с той же проблемой, что и при вклгочеиии перед рТ; возврат к элементу, который Рнс.
49. Удаление нз списка н включение в другой спнсок. предшествует указанному, невозможен. Но можно удалить последующий элемент, предварительно переслав его значение ближе к началу списка. Это довольно очевидный и простой прием, но его можно применить только в случае, когда у р~~ есть последующий элемент, т, е. ои не является последним элементом списка, Теперь мы перейдем к основной операции прохода по списку. Предположим, что операция Р(х) должна выполняться с каждым элементом списка, первый элемент которого есть р). Эту задачу можно выразить следующим образом: иг)г11е список, на который' указвгвает р, непует до Ьей(п выполнить операцию Р; перейти к следуюи(елгу элементу спи 202 Е Лииамииеакие инфармаиианине ггрркгдрн Подробнее это действие описывается оператором (4.17): тгЫ!е рчь пВ Йо Ьея(п Р(р!); р:= р(.пех1 епд (4.17) ((р =ай) ~/ — Ь) 4.й.й Упорядоченные списки н реорганизация списков Ллгоритм (4,20) сильно напоминает подпрограммы поиска при просмотре массива нли файла.
В самом деле, файл — это в сущности линейный список, в котором техника Из определения оператора цикла с предусловием и списковой структуры следует, что Р будет выполнено для всех элементов списка и ии для каких других. Очень частая операция — поиск в списке элемента с заданным ключом х. Так же как в случае файлов, поиск ведется строго последовательно. Он заканчивается, либо когда элемент найден, либо когда достигнут конец списка.
Снова предположим, что начало списка обозначено ссылкой р. Первая попытка сформулировать задачу такого поиска приводит к следующему: чг!б!е (РФп11) Л (р(,йеуФх) с!о р:=р1.пех1 (4,18) Однако следует заметить, что при р = пН ие существует рт. Следовательно, вычисление условия окончания может потре бовать обращения к несуществующей переменной (в отлична от переменной с неопределенным значением) н может привести к ошибке при выполнении программы.
Это можно исправить, используя либо явный выход из цикла, выраженный оператором безусловного перехода (4.19), либо вспомогательную булевскую переменную, отмечающую, найден или нет нужный ключ (4.20). пв!1ер ~ в!!ее !Т р).Феу х йея йо!о Раипй 14, 19) е)зе р:,=- р!.пехг Использование оператора безусловного перехода требует присутствия в каком-то месте метки для перехода; несовместимость этого оператора с оператором цикла видна из того факта, что условие вЫ)е при этом вводит в заблуждение: тело цикла не обязательно выполняется, пока р чь пВ. Ь:= 1гие; пййе (р Фп)1) Л Ь де Ы р!.Ьеу = х йеп Б;= Хиве (и 20) е1зе р: =- р(.пехг 4.8.
Линейные списки связи с последующим элементом остается неопределенной или неявной. Поскольку элементарные операции над файлами не допускают включение новых элементов (разве что в конец) п.,п удзлсние (разве что уничтожение всех элементов), у разработчика есть болщпая возможность выбора способов представления, и он может использовать также последовательное расположение, помещая стедующие одна за другой компоненты в смежные области памяти. Линейные списки с явпымн ссылками обеспечивают ббльшую еибкость н поэтому нх следует использовать, ко~да требуется такая дополнительная гибкость.
В качестве примера мы рассмотрим теперь задачу, к котороп будем постоянно обращаться в этой главе, чтобы продемонстрировать па ней работу различных методов. Она состоит в чтении некоторого текста, выборе из него всех остальных слов и подсчете частоты их появления, т. е. в состапленни частотного словаря. Очевидно, что для этого нужно составить список слов, найденных в тексте.
Каждое очередное слово, прочитанное в тексте, щцется в списке. Если слово найдено, счетчик его частоты увеличивается, в противном случае слово добавляется к списку. Мы будем называть этот процесс просто поиском, хотя ясно, что в него входит также н включение. Чтобы сосредоточить внимание на основной задаче обработки списка, мы предположим, что слова уже выделены из исследуемого текста, закодированы целыми числами и находятся во входном файле.
Формулировка этой процедуры, называемой зеагсй (поиск), непосредственно следует из (4.20). Переменная гоо! указывает па начало списка, в который вставляются новые слова, это действие определено в (4.!2). Полный алгоритм описан в программе 4.1; здесь есть подпрограмма для распечатки полученного списка слов в виде таблицы. Печать таблицы служит примером действия, выполняемого с каждым элементом списка одни раз, схема этого процесса уже была приведена в (4.17). Длгоритм линейного просмотра в программе 4.1 напомянает процедуру поиска в массивах и файлах, где, в частности, используется простой способ упрощения условия окончания цикла; использование барьера. При поиске по списку также можно пользоваться барьером, он представляется фиктивным элементом в конце списка.
Новая процедура (4.21), заменяющая процедуру поиска в программе 4.1, предполагает, что добавлена глобальная переменная зеп11пе! и что инициация переменной гоо! заменена операторами пете(еепйпе1); гоо1:=- вепре!; 4. Йинамакескае анформационние сгрукгари аиоага4п 1!еа (ЬгриЪоигриг) ! )простое включение в список) Фуре ген" =-- ')иоЫ; !рагс! =- тесака йеу: !пгееег; Саине! !г!1ерег; пехг! ге~" еаза; пах 1с: !п!скег! гоо1: пЯ ргаеейпге эеагсЬ (х: тгеяег; чае гоо!! геД1 ъаг !о; гег; Ь; Ьоо!сап; ,Ъеа!и пг:= гор!; Ь:=- йие1" ъЫ)е (4рФп!1) гк, Ь йо !к эг),ассу:= х реп Ь:=,~аЪе е1ае эг !-= ъ !.пех1; И Ь !Ъеп Ъеа!и (новый' элемент) !р != гоо1; гге!р (гоог); п1!Ъ гоп!! ао Ъеа!и Ъеу:=-= х; соапг:=- 1; пехг !нн 4р епд еп41 е!ие 44Г1,СО!ГП$:=и 4Г1,СОиПГ + 1 еаза (гаагсЬ); ргоееаиге рггпйхГ (н ! гол! Ъеа)п пЫ1е !о Ф и!1 «)в Ъеа!п и! !ге7г! (!р 1,Ъеу, !р ~,гонг!г); )р !=- !г! гпсхг спй епа (рпийкг)," Ъеа!и гоог:=- и!1; гечгаЯ: пЪ!1е lс ~ 0 до Ъеа!и ееагсП (4; гоо!); !сиаЯ епа; р!фги!1н(гоог) епй .
Программа 4.!. Внгаочеиие в список, зов 43.,гтииейиые списки создающими элемент, который будет использоваться в качестве барьера (зете)гпе(): ргоседиге таите)г(кг г)гассет; тат гоо/: тЯ; тат ич теД. )геа(п и;=. ггюг; есггггггс1 г,йеу:.-и л; ъй(1е гг'1.)геу сп гс йв гг:= ж1глехт; 1Г и че зегггггге1 1)геп гг',.согггг1:= жг.сщгаг -1- г е1 Ъей)п (новыйэлелгеилг4 ж:= тост; легс(тест,; (4.21) тт1Й гчюг, ао 1гей(п кеу:=- сс) соггггг;= 1," ггехс: = и епй епй епй (теаг ей~ Разумеется, в этом примере плохо используется мощность н гибкость связанного списка; при поиске можно допустить линейный просмотр всего списка только в том случае, если число элементов ограниченно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
