Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 56
Текст из файла (страница 56)
10.1.4 Перепишите процедуры ЕН00ЕиЕ и 13ЕОНЕОЕ так, чтобы они корректно обнаруживали опустошение и переполнение очереди. 10.1.5 При работе со стеюм элементы можно добавлять в него и извлекать из него только с одного конца. Очередь позволяет добавлять элементы с одного конца, а извлекать — с другого. Очередь с двусторонним доступом, или дек (белие), предоставляет возможность производить вставку и удаление с обоих юнцов. Напишите четыре процедуры, выполняющиеся в течение времени 0(1) и позволяющие вставлять и удалять элементы с обоих концов дека, реализованного с помощью массива.
гбб Часть Дб Структуры данник 1О.1.б Покажите, как реализовать очередь с помощью двух стеков. Проанализируйте время работы операций, которые выполняются с ее элементами. 16! 1. 7 Покажите, как реализовать стек с помощью двух очередей. Проанализируйте время работы операций, которые выполюпотся с его элементами. 10.2. Связанные списки Связанный список (!пэ)(еб йз() — это структура данных, в которой обьекты расположены в линейном порядке. Однако, в отличие от массива, в котором этот порядок определяется индексамн, порядок в связанном списке определяется указателями на каждый объект.
Связанные списки обеспечивают простое и гибкое представление динамических множеств и поддерживают все операции (хотя и не всегда достаточно эффективно), перечисленные на с. 261. Как показано на рис. 10.3, каждый элемент г)аажды связанного списка (бопЫу 1пэ)(еб йз() Х, — это обьект с одним атрибутом )геу и двумя атрибутами-утщзателями: пехг (следующий) и ргеп (предыдущий).
Этот объект может также содержать другие сопутствующие данные. Для заданного элемента списка х указатель х. пех( указывает на следующий элемент связанного списка, а указатель х. рто†на предыдущий. Если х. ргеп = ы(~., у элемента х нет предшественника, и, следовательно, он является первым, т.е.
гпловиым в списке. Если х. пехг = )чп., то у элемента х нет последующего, а значит, он является последним„т.е. хаослговым в списке. Атрибут 1,. Ьеа(1 указывает на первый элемент списка. Если Ь. Ьеа(( = )41~., то список пуст. рть аеу леи l (а) ь.ьеад — — — -ь(хг19гт-':,"г:. "":~1Я',:,';=. ~',1:.4 ~':~ " (,'1-.1' ~,.Ф'.( (Е) Ь. бенд - — — — ~',Р~ДЙ~-';,.~.„..~. Г9~' "~. '. ) ьг)за~~ ',,) ~ь)4 ~")г) ~„. ~Л~~) (и и ь д (,кфГ~ . ~"Дъ~~ ' ""„:','"~)б~~- (' 1);:,(у!' Ряс. 19.3.
(в) Дввкды с ля залпы й список Ь, предсгавляющвй дл нам пчес кое мне тесгво (1,4,9, 16). Калспщ элемевт списка является обьектом с агрлбугамв, представляющими ключ я указатели (покаэаллые стрелками) на следующий в предьщущлй объекты. Атрибут пезе хвостового в атрвбуг ргее головного элементов равны нп„чго показано дпагопальпой косой чертой. Атрибут б. беата указывает па голову списка. (6) После выполвепвя $лзт-1нзякт(уьх), где х. ассу = 25, связанный сплсок в качестве головного элемента получает новый объекг с ключом 25.
Эгот новый обьекг указывает па старый головкой элемент с ключом 9. (в) Результат последующего вызова Ызт-пььятя(Ь, х), где х указывает па обьекг с ключом 4. 2б9 Глава !д Элементарные етрунтуры данные Списки могут быть разных видов. Список может быть однократно или дважды связанным, отсортированным или неотсортированным, кольцевым или некольцеяым. Если список однократно связанный (однонаправленный) (з(пя!у!1п)геб), то указатель ргес в его элементах отсутствует.
Если список отсортировав (яопе!1), то его линейный порядок соответствует линейному порядку его ключей; в этом случае минимальный элемент находится в голове списка, а максимальный — в его хвосте. Если же список не отсортирован, то его элементы могут располагаться в произвольном порядке. Если список тзаьцевой (с(гсц1аг 1Ы), то указатель рген его головного элемента указывает на его хвост, а указатель пех! хвостового элемента — на головной элемент. Такой список можно рассматривать как замкнутый в виде юльца набор элементов.
В оставшейся части раздела предполагается, что списки, с которыми нам придется работать, — неотсортированные дважды связанные. Поиск в связанном списке Вызов Ьгзт-Зелксп(Ь,Й) находит в списке Ь первый элемент с ключом Ь путем простого линейного поиска и возвращает указатель на найденный элемент. Если элемент с ключом Ь в списке отсутствует, возвращается значение нп.. Процедура Ьгят-Белксп(Ь,4), вызванная для связанного списка, изображенного на рис.10.3,(а), возвращает указатель на третий элемент, а вызов Ь|зт-Белцсп(Х„7) — значение !чп..
Ь!Бт-Белксн(Ыс) 1 х = Ь.Ьеав( 2 ия11е х зь !чп. и х. Ьеу ф Ь 3 х = х. пех! 4 гец!гп х Поиск с помощью процедуры Ьгзт-Белксп в списке, состоящем из п элементов, в наихудшем случае выполняется за время 9(п), посюльку может понадобиться просмотреть весь список.
Вставка в связанный список Если имеется элемент х, атрибут Ьеу которого предварительно установлен, то процедура Ьгзт-1!чзецт вставляет элемент х в начало списка (рис. 10.3, (6)). Ь!Бт-1мзект (л', х) 1 х.пех! = Ь.Ьеав( 2 ПЬ.Ьеав( ~ !чп. 3 Ь.Ьеав(.ргее = х 4 Ь.Ьеав( = х 5 х.ргее = ~а. Часть ДЕ Структуры даьтыь 270 (Вспомните, что наша запись атрибутов допускает каскадирование, так что Ь.Ьеаа'.ргее означает атрибут ргес объекта, на который указывает атрибут Ь.
Ьеаг).) Время работы Ь1зт-1ызект со списком из и элементов равно 0(1). Удаление из связанного списка Представленная ниже процедура 1.1БТ-)ЗЕВАЕТЕ удаляет элемент х из связанного списка Х,. В процедуру необходимо передать указатель на элемент х, после чего она удаляет х из списка путем обновления указателей. Чтобы удалить элемент с заданным ключом, необходимо сначала вызвать процедуру 1.1зт-белксн для получения указателя на элемент.
11зт-Рн.ете (1, х) 1 !1х.ргее ЗЬ 1ЧП. 2 х.ртсб.пех! = х.пех! 3 е!яе Ь,Ьеаа' = х.веха 4 !Гх.пех! ~ м~. 5 х.пех1.ртес = х.ргее На рис.10.3,(в) показано, как элемент удаляется из связанного списка. Время работы процедуры 11ЗТ-РЕЕЕТЕ равно 0(1), но если требуется удалить элемент с заданным ключом, то в наихудшем случае требуется время О(п), поскольку сначала нужно вызвать процедуру 11зт-Беяксн для поиска удаляемого элемента. Ограничители Код процедуры 11зт-Рн.ете мог бы быть проще, если бы можно было игнорировать граничные условия в голове н хвосте списка.
1.1БТ-1ЗЕЕЕТЕ'(ь', Х) 1 х.ргее,пех! = х.пех1 2 х.пех1.ргее = х.ргее Ограничигнель(зепг!пе!) — это фиктивный объект, упрощающий учет граничных условий. Например, предположим, что в списке 2 предусмотрен объект 2.п11, представляющий значение 1чн., но при этом содержаьций все атрибуты, которые имеются у других элементов. Когда в коде происходит обращение к значению мп., оно заменяется обращением к ограничителю 2. пй. Как показано на рис.
10.4, наличие ограничителя преобразует обычный дважды связанный список в циклический дважды связанный снисок с ограничителем. В таком списке ограничитель г . пй расположен между головой и хвостом. Атрибут 2. пй. пех! указывает на голову списка, а атрибут 2. пй.ргее — на его хвост. Аналогично атрибуты пех! хвостового элемента и ргес головного элемента указывают на элемент 1,. пй.
Поскольку атрибут 2. Ы, пех! указывает на голову списка„можно упразднить атрибут 2.Ьеаа, заменив ссылки на него ссылками на Ь.п11.пех1. Как видно на рис. 10.4,(а), пустой список содержит толью ограничитель, и как 2. пй. пех1, так и й. пй, ртее указывают на 2,.
п11. 271 Глава 1П Зяенентарныв структуры данных (а) 1,. ии— ьт)~:"--в~~~я: ьо. )) 1:.) ;.~е(."."~~~в:,=,.; )„:Твт,:.",.:;Ятй()„ ьз 1,. и — '-)=:;.ЯЖ':-т е:.',-'1.'~~3-~~-.'-'т)(ЕГ:: -$:-."Л4"Г'3 ) Рве. 1ЕА. Циклический дважды связанный список с отрвничвтедями. (лрвничитедь 1. пп находится мткду головой и хвостом. Атрибут Е.Леала больше не нужен, посюпьку доссуп к пшове шпека пояучттся с помошьш Ь.
пи. пея), (в) Пустой список. (6) Свшвиный список с рис. 10.3, (я), с ключом 9 в голове и кявчом 1 в хвосте списка. (в) Список после выполнения $лзт-1мзвкт'(Ь, к), где а.Лез = 25. Новый обьевт становится годовой списка. (г) Список после удаления обьектя с кмочом 1. Новым хвостом становится объект с ключом 4. Код 1.)зт-йедксн остается прежним, но обращения к нп. и Б.
Ьеао' изменены, квк указано выше. Б1БТ-БЕАКСН'(2, )с) 1 х = Ь.пт(.пех( 2 тчййе х ф Ь. пй и х. Ле)) ф й 3 х = х.пех( 4 ге(пгп х Удаление элемента нз списка производится с помощью уже описанной двустрочной процедуры 1.1Бт-()Бьете'. Для вставки элемента в список используется приведенная ниже процедура. (ЛБТ-1ХБЕКТ (А,х) 1 х. пех( = 1 . пй. пех( 2 Й.пй.пех(.ргеи = х 3 1..пй.пех( = х 4 х.ргеи = с . пй Действие процедур ьдзт-1хзект' н 1.(зт-1)ееете' на список-образец показано на рис. 10.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
