Главная » Просмотр файлов » Алгоритмы - построение и анализ

Алгоритмы - построение и анализ (1021735), страница 52

Файл №1021735 Алгоритмы - построение и анализ (Алгоритмы - построение и анализ) 52 страницаАлгоритмы - построение и анализ (1021735) страница 522017-07-10СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 52)

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а.птп в таком списке. Покажите также, как можно обратить порядок элементов в таком списке за время О (1).

10.3 Реализация указателей и объектов Как реализовать указатели и объекты в таких языках, как Рог1гап, где их просто нет? В данном разделе мы ознакомимся с двумя путями реализации связанных структур данных, в которых такой тип данных, как указатель, в явном виде не используется. Объекты и указатели будут созданы на основе массивов и индексов.

Представление объектов с помощью нескольких массивов Набор обьектов с одинаковыми полями можно представить с помощью массивов. Каждому полю в таком представлении будет соответствовать свой массив. В качестве примера рассмотрим рис. 10.5, где проиллюстрирована реализация с помощью трех массивов связанного списка, представленного на рис. 10.3а. В каждом столбце элементов на рисунке представлен отдельный объект. В массиве Йеу содержатся значения ключей элементов, входящих в данный момент в динамическое множество, а указатели хранятся в массивах пехг и ртев. Для заданного индекса массива х элементы Йеу [х), пех~ [х) и ртее [х) представляют объект в связанном списке. В такой интерпретации указатель х — это просто общий индекс в массивах Йеу, пех1 и ртев.

Указатели при таком способе хранения представляют собой просто индексы объектов, на которые они указывают. На рис. 10.3а объект с ключом 4 в связанном списке следует после объекта с ключом 16. Соответственно, на рис. 10.5 ключ 4 является значением элемента йеу[2), а ключ 16 — значением элемента бреу [5), поэтому пех1 [5] = 2 и ртее [2] = 5. В качестве значения нй. обычно используется целое число (например, 0 или — 1), которое не может быть индексом массива.

В переменной Ь содержится индекс головного элемента списка. 270 Часть 1П. Структуры данных 7 агу неГ Рис. 10.5. Связанный список, прел- ставленный массивами Йеу, нехс н угее В нашем псевдокоде квадратные скобки используются как для обозначения индекса массива, так и для выбора поля (атрибута) объекта. В любом случае значение выражений Йеу [х], пех1 [х] и ргеи [х] согласуется с практической реализацией.

Представление объектов с помощью одного массива Обычно слова в памяти компьютера адресуются с помощью целых чисел от 0 до М вЂ” 1, где М вЂ” это достаточно большое целое число. Во многих языках программирования объект занимает непрерывную область памяти компьютера. Указатель — это просто адрес первой ячейки памяти, где находится начало обьекта. Другие ячейки памяти, занимаемые объектом, можно индексировать путем добавления к указателю величины соответствующего смещения.

Этой же стратегией можно воспользоваться при реализации обьектов в средах программирования, в которых отсутствуют указатели. Например, на рис. 10.6 показано, как можно реализовать связанный список, знакомый нам из рис. 10.3а и 10.5, с помощью одного массива А.

Объект занимает подмассив смежных элементов А [2..1с]. Каждое поле объекта соответствует смещению, величина которого принимает значения от 0 до lс — з, а указателем на объект является индекс ~. Каждый элемент списка — это объект, занимающий по три расположенных рядом элемента массива. Указатель на объект — это индекс его первого элемента. Объекты, в которых содержатся элементы списка, на рисунке отмечены светло-серым цветом.

На рис. 10.6 сдвиги, отвечающие полям кеу, пех1 и ргеи, равны О, 1 и 2 соответственно. Чтобы считать значение поля ргее [г] для данного указателя г, к значению указателя добавляется величина сдвига 2, в результате чего получается А[г+ 2]. Представление в виде единственного массива можно считать более гибким в том плане, что с его помощью в одном и том же массиве можно хранить объекты различной длины. Задача управления такими неоднородными наборами обьектов сложнее, чем аналогичная задача для однородного набора объектов, где все объекты состоят из одинаковых полей. Поскольку большинство структур данных, Глава 10. Элементарные структуры данных 271 ь ' з,~ ы н ~з ы ы 1' н; ~з ~ь ~з зл з: 'з -1 4 , з ( 13 ~;, ' ' 4 . ' . ~ь ~ ь ! !з 9 ~п~/ / Йсо Рис.

Характеристики

Тип файла
DJVU-файл
Размер
18,3 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6518
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее