Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 53
Текст из файла (страница 53)
Этот объект может также содержать другие сопутствующие данные. Для заданного элемента списка х указатель пехЬ [х] указывает на следующий элемент связанного списка, а указатель ргее [х] — на предыдущий. Если ртеи [х] = и!!., у элемента х нет предшественника, и, следовательно, он является первым, т.е.
головным в списке. Если пех! [х] = мп., то у элемента х нет последующего, поэтому он является последним, т.е. хвостовым в списке. Атрибут Ьеаа [з ] указывает на первый элемент списка. Если йеаа [з ] = = мп., то список пуст. Списки могут быть разных видов. Список может быть однократно или дважды связанным, отсортированным или неотсортированным, кольцевым или некольцевым.
Если список однократно связанный (однонаправленный) (з!пя1у 1ш1сед), то указатель ргео в его элементах отсутствует. Если список отсортирован (зог!ед), то его линейный порядок соответствует линейному порядку его ключей; в этом случае минимальный элемент находится в голове списка, а максимальный — в его хвосте. Если же список не отсортирован, то его элементы могут располагаться в произвольном порядке.
Если список кольцевой (с1гсп1аг !!з!), то указатель Глава 10. Элементарные структуры данных 265 р«г«ге ««««! "": ~-" ---.'Л:.~: =-:-~"": ----.] 4 [:=':--"-ЯУЕ[ 61 кя1 (е.| -- — — [««]з. Г т,,:... г Т91 3 '~~~6Г' [::.: ']ч [ ~„, . '~~. Г],';] Ы 6«а,! К~ -- — ~м/'~25[ ~« * ! 9] :',. «"'.~~16Г~~ .~~-Д~~Я Рис. 10.3.
Вставка в дважды связанный список и удаление из него ргет«его головного элемента указывает на его хвост, а указатель ггехг хвостового элемента — на головной элемент. такой список можно рассматривать как замкнутый в виде кольца набор элементов. В оставшейся части раздела предполагается, что списки, с которыми нам придется работать, — неотсортироваиные и дважды связанные. Поиск в связанном списке Процедура 1лзт ЯнАксн(Ыс) позволяет найти в списке Ь первый элемент с ключом Й путем линейного поиска, и возвращает указатель на найденный элемент. Если элемент с ключом Й в списке отсутствует, возвращается значение м~. Процедура Ьвт Звлксн(Ь, 4), вызванная для связанного списка, изображенного на рис.
10.3а, возвращает указатель на третий элемент, а процедура 1лзт ЗвАксн(Ь, 7) — значение нп.: Ь|зт Бнлксн(Ыг) 1 х - аеад[Ц 2 ттЫ1е х „-6 Нп. и кеу[х] ф й 3 Йо х — ггехг[х] 4 гетнгп х Поиск с помощью процедуры Ь1зт БвАксн в списке, состоящем из и элементов, в наихудшем случае выполняется в течение времени 6 (и), поскольку может понадобиться просмотреть весь список. Вставка в связанный список Если имеется элемент х, полю 1геу которого предварительно присвоено значение, то процедура Ь1зт 1мзвкт вставляет элемент х в переднюю часть списка (рис. 10.3б): Часть 1П.
Структуры данных 266 1ЛЯТ 1ХБЕКТ(Ь,х) 1 пех1[х] — Ьеаг1[Ц 2 Н ЬЕаИ[Ь] ф МЬ 3 гпеп ргею[леаа[1]] — х 4 аеас[А] — х 5 ргео [х] — 1ЧП. Время работы процедуры 1лзт 11чзект равно О (1). Удаление из связанного списка Представленная ниже процедура 1лзт Реьете удаляет элемент х из связанного списка Ь. В процедуру необходимо передать указатель на элемент х, после чего она удаляет х из списка путем обновления указателей.
Чтобы удалить элемент с заданным ключом, необходимо сначала вызвать процедуру 1лзт БеАксн для получения указателя на элемент: 1ЛЗТ 13ЕЬЕТЕ(Ь,х) 1 Н ргес[х] ~ 1Ч1Ь 2 Феп пех1 [ргеи[х]] — пех1[х] 3 ене аеас[А] — пех1[х] 4 Н пех1[х] ф %1 5 Феп ртес[пех1[х]] — ргеи[х] Удаление элемента из связанного списка проиллюстрировано на рис. 10.3в.
Время работы процедуры 11зт Веьете равно 0(1), но если нужно удалить элемент с заданным ключом, то в наихудшем случае понадобится время 6 (и), поскольку сначала необходимо вызвать процедуру 1лзт БеАксн. Ограничители Код процедуры 1лзт Реьете мог бы быть проще, если бы можно было игнорировать граничные условия в голове и хвосте списка; 1ЛЯТ РЕЬЕТЕ'(Ь, х) 1 пех8[ргес[х]] — пех1[х] 2 ртео[пех1[х]] — ргео[х] Огравичивюель (зепбпе!) — это фиктивный объект, упрощающий учет граничных условий.
Например, предположим, что в списке Ь предусмотрен объект пг1 [Ц представляющий значение МЬ, но при этом содержащий все поля, которые имеются у других элементов. Когда в коде происходит обращение к значению н1ь, оио заменяется обращением к ограничителю п11 [Ь]. Из рис. 10.4 видно, что наличие ограничителя преобразует обычный дважды связанный список в циклический Глава 10. Элементарные структуры данных 267 дважды связанный список с ограничителем (с1гсп!аг, бопЫу 11пкед 11з1 тч1бз а зепбле1).
В таком списке ограничитель пт1 [Ь] расположен между головой н хвостом. Поле пех1 [п11[Ь]] указывает на голову списка, а поле ртее [п11[Ь]) — на его хвост. Аналогично, поле пехг хвостового элемента и поле ртее головного элемента указывают на элемент п11 [Х]. Поскольку поле пех1 [п11 [Ц) указывает на голову списка, можно упразднить атрибут Беар [Х], заменив ссылки на него ссылками на поле пехг [п11[Ь]].
Пустой список содержит только ограничитель, поскольку и полю пехФ [пг1[Х)], и полю ртее [п11[Х]] можно присвоить значение п11 [Ц Код процедуры 1.1зт Белксн остается тем же, что и раньше, однако ссылки на значения 1чп. и Беата [Ц заменяются так, как описано выше: 1лзт БеАксн'(Ц 1с) 1 х ~ — пех$[п11[Ь]] 2 тчЫ!е х ф п11[Ц и Иеу[х] ф й 3 до х — пехг[х) 4 гетпгп х Удаление элемента из списка производится с помощью уже описанной процедуры 1лзт Редеете', состоящей всего из двух строк. Для вставки элемента в список используется приведенная ниже процедура: 1.1зт 11чзект'(Х, х) 1 пех1[х] +- пех1 [п11 [Ь]] 2 ртее[пех1[пг1[Ц]] ~ — х 3 пех1[п11[Ц] — х 4 рте е [х) — п11 [Ь] Действие процедур 11зт 1нзект' и 11зт 13н.ете' проиллюстрировано на рис.
10.4. В части а этого рисунка приведен пустой список. В части б изображен связанный список, уже знакомый нам по рис. 10.3а, в голове которого находится ключ 9, а в хвосте — ключ 1. В части в изображен этот же список после выполнения процедуры 1лзт 1ызпкт'(Х,, х), где еер [х] = 25. Новый объект становится в голову списка.
В части г рассматриваемый список представлен после удаления в нем обьекта с ключом 1. Новым хвостовым обьектом становится обьект с ключом 4. Применение ограничителей редко приводит к улучшению асимптотической зависимости времени обработки структур данных, однаю оно может уменьшить величину постоянных множителей. Благодаря использованию ограничителей в циклах обычно не столько увеличивается скорость работы кода, сюлько повышается его ясность.
Например, представленный выше код, предназначенный для обработки связанного списка, упрощается в результате применения ограничителей, но сэкономленное в процедурах Ь1зт 11чзект' и 1.1зт Редеете' время равно всего лишь О (1). Однаю в других ситуациях применение ограничителей позволяет сделать код в циклах компактнее, а иногда даже уменьшить время работы в и или пз раз. Часть 111.
Структуры данных в) в41Д вЂ” -в) а1 вдп — -' ' в~~~- 'ыГ -$ [в [ ) ".-]= К( в) г) Рис. 10.4. Циклический дважды связанный список с ограничителями Ограничители не стоит применять необдуманно. Если в программе обрабатывается большое количество маленьких списков, то дополнительное пространство, занимаемое ограничителями, может стать причиной значительного перерасхода памяти. В этой книге ограничители применяются лишь тогда, когда они действительно упрощают код. Упражнения 10.2-1. Можно ли реализовать операцию 11чзект над динамическим множеством в однократно связанном списке так, чтобы время ее работы было равно О (1)? А операцию 13и.ЕТЕ? 10.2-2.
Реализуйте стек с помощью однократно связанного списка Х,. Операции Ризн и Рог должны по-прежнему выполняться в течение времени О (1). 10.2-3. Реализуйте очередь с помощью однократно связанного списка Ь. Операции Ен00епе и Ое0иепе должны выполняться в течение времени 0 (1). 10.2-4. В каждой итерации цикла, входящего в состав процедуры 1лзт Белксн', необходимо выполнить две проверки: х ~ пи [Ь] и абер [х] ф 1г. Покажите, как избежать проверки х ф ггв1 [Ь] в каждой итерации. 10.2-5.
Реализуйте базовые словарные операции 1ызект, Реьете н ЗеАксн с помощью однократно связанного циклического списка. Определите время работы этих процедур. 10.2-6. Операция Ыч|оы (обьединение) над динамическим множеством принимает в качестве входных данных два отдельных множества 81 и Яз и возвращает множество Я = Я1 О Яз, состоящее из всех элементов множеств Яз и Яз. В результате выполнения этой операции множества Яг и Яз обычно разрушаются. Покажите, как организовать поддержку операции 11ьлом со временем работы 0(1) с помощью подходящей списочной структуры данных.
Глава 10. Элементарные структуры данных 269 10.2-7. Разработайте нерекурсивную процедуру со временем работы 9 (и), обращающую порядок расположения элементов в однократно связанном списке. Процедура должна использовать некоторый постоянный объем памяти помимо памяти, необходимой для хранения самого списка. * 10.2-8. Объясните, как можно реализовать дважды связанный список, используя при этом всего лишь один указатель пр [х] в каждом элементе вместо обычных двух (пехг и ртев).
Предполагается, что значения всех указателей могут рассматриваться как й-битовые целые чисел, а величина пр [х) определяется как пр [х] = пех1 [х] ХОК ртеи [х), т.е. как 1с-битовое "исключающее или" значений пехг [х] и ртее [х]. (Значение нй. представляется нулем.) Не забудьте указать, какая информация нужна для доступа к голове списка. Покажите, как реализовать операции БпАксн, 1нзект и 13а.птп в таком списке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
