Главная » Просмотр файлов » Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)

Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 57

Файл №1162189 Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013)) 57 страницаТ. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189) страница 572019-09-19СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Применение ограничителей редко приводит к улучшению асимптотичесюго времени обрабопсн структур данных, однако может уменьшить величину постоянных множителей. Благодаря использованию ограничителей в циклах обычно не отолью увеличивается скорость работы юда, околыш повышается его ясность.

Например, представленный выше кпд, предназначенный для обработки связанного списка, упрощается в результате применения ограничителей, но сэюномленное в процедурах Ь)зт-1нзект' и 1.1зт-)3ееете' время составляет всего лишь Часть |П. Структуры данньи ггг 0(1). Однако в других ситуациях применение ограничителей позволяет сделать код в циклах компактнее, а иногда даже уменьшить время работы в п или пз раз. Ограничители не стоит применять необдуманно. Если в программе обрабатывается большое количество маленьких списков, то дополнительное пространство, занимаемое ограничителями, может стать причиной значительного перерасхода памяти.

В этой книге ограничители применяются лишь тогда, когда они действительно упрощают код. Упражнения 10.2.1 Можно ли реализовать операцию 1мзект над динамическим множеством в однократно связанном списке так, чтобы время ее работы было равно 0(1)? А операцию ПЕЬЕТЕ? 10.2.2 Реализуйте стек с помощью однократно связанного списка 1,. Операции Ризн и Рог должны по-прежнему выполняться за время 0(1). 10.2.5 Реализуйте очередь с помощью однократно связанного списка Е.

Операции Емг1иепе и ПеОиепе должны по-прежнему выполняться за время 0(1). 10.2.4 Как уже говорилось, в каждой итерации цикла, входящего в состав процедуры 11зт-Белксн', необходимо выполнить две проверки: х ~ Ь.пь( и х.)сеу ~ к. Покажите, как избежать проверки х ф 1.

пь( в каждой итерации. 10.2.5 Реализуйте базовые словарные операции 1мзект, Он.ете и Яелксн с помощью однократно связанного циклического списка. Определите время работы этих процедур. 10.2. 6 Операция Пмюн (объединение) над динамическим множеством принимает в качестве входных данных два непересекающихся множества Я1 и оз и возвращает множество о = о1 О Яз, состоящее из всех элементов множеств Я1 и Яз. В результате выполнения этой операции множества о1 и Яз обычно разрушаются.

Покажите, как организовать поддержку операции Пасюк со временем работы 0(1) с помощью подходящей списочной структуры данных. 10.2.? Разработайте нерекурсивиую процедуру со временем работы 9(п), обращающую порядок расположения элементов в однократно связанном списке. Процедура должна использовать некоторый постоянный обьем памяти, помимо памяти, необходимой для хранения самого списка.

гуг Глава 1а Элементарные струннрры данных иг.8 * Объясните„как можно реализовать дважды связанный список, используя при этом всего лишь один указатель х. пр в каждом элементе вместо обычных двух (пезт и реем). Предполагается, что значения всех указателей могут рассматриваться как к-битовые целые числа, а величина х. пр определяется как х. пр = х.пех( ХОК х.ргео, т.е. как Ьбитовое "исключающее или*' значений х. пехг и х.

ргео. (Значение нп. представляется нулем.) Не забудьте указать, какая информация нужна для доступа к голове списка. Покажите, как реализовать операции Белксн, 1нзект и Пееете в таком списке. Покажите также, как можно обратить порядок элементов в таком списке за время О(1). 1ОЗ. Реализация указателей и объектов Как реализовать указатели и объекты в языках, где их просто нет? В данном разделе мы ознакомимся с двумя путями реализации связанных структур данных, в которых такой тип данных, как указатель, в явном виде не используется.

Объекты и указатели будут созданы на основе массивов и индексов. Представление объектов с помощью нескольких массивов Набор объектов с одинаковыми атрибутами мвкно представить с помощью массивов. В качестве примера рассмотрим рис. 10.5, на котором проиллюстрирована реализация с помощью трех массивов связанного списка, представленного на рис. 10.3, (а).

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

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

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

Этой же стратегией можно воспользоваться при реализации объектов в средах программирования, в которых отсутствуют указатели. Например, на рнс. 10.6 показано, как можно реализовать связанный список, знакомый нам из рис. 10.3,(а) и 10.5, с помощью одного массива А. Объект занимает подмассив смежных элементов А[2 .. 24]. Каждый атрибут объекта соответствует смещению, величина которого принимает значения от 0 до 24-2, а указателем на объект является индекс 2. Каждый элемент списка — зго объект, занимающий по три расположенных рядом элемента массива.

Указатель на объект — зто индекс его первого элемента. Объекты, в которых содержатся элементы списка, на рисунке отмечены светло-серым цветом. На рис. 10.6 смещения, отвечающие атрибутам 2сеу, пея2 и ргео, равны О, 1 и 2 соответственно. Чтобы прочесть значение атрибута з.ргее для данного указателя з, к значению указателя добавляется величина смещения 2, в результате чего получается А[з + 2[. Представление в виде единственного массива можно считать более гибким в том плане, что с его помощью в одном и том же массиве можно хранить объекты различной длины. Задача управления такими неоднородными наборами объектов сложнее, чем аналогичная задача для однородного набора объектов, где все объекты имеют одинаковые атрибуты. Поскольку большинство структур данных, которое нам предстоит рассмотреть, состоит из однородных элементов, для наших целей достаточно использовать представление объектов с помощью несколъкнх массивов.

1 2 3 4 5 6 7 8 9 Ю 11 12 13 14 15 16 17 18 19 20 21 22 23 24 119— 1еу ргег ИИХФ Рис. 1О.б. Связанный список с рис.10.3,(а) и 10.5, представленный единственным массивом А. Каждый элемент списка является обьекгом, занимающим подмассив из трщ смежньпс ячеек массива. Атрибуты /сер, пеяг и ргес в каждом обьекге отвечают смещениям О, 1 и 2 соответственно. Указатель на объект представляет собст индекс первого элемента обьекга. Обьекты, содержащие элементы списка, выделены светлой пприиткой; стрелки показмвают порядок в списке.

Глава 20. Элемененарные сируненуры данных 275 Выделение и освобождение объектов При добавлении нового элемента в динамическое множество, представленное дважды связанным списком, необходимо получить указатель на не используемый в настоящее время объект в представлении связанного списка. Таким образом, было бы полезно управлять хранением объектов, не используемых в данный момент в представлении связного списка, чтобы можно было легко их получать при необходимости. В некоторых системах за выявление неиспользуемых объектов отвечают сборщики мусора (яагЬаяе со11есюг). Однако многие приложения достаточно просты и способны сами отвечать за возврат неиспользуемых объектов модулю управления памятью.

Давайте рассмотрим задачу выделения и освобождения однородных объектов на примере дважды связанного списка, представленного с помощью несюльких массивов. Предположим, что в таком представлении используются массивы длиной тп н что в какой-то момент динамическое множество содержит и < т элементов. В этом случае и объектов представляют элементы, которые находятся в данный момент в динамичесюм множестве, а т — и объектов свободны.

Их можно испольэовать для представления элементов, которые будут вставляться в динамичесюе множество в будущем. Свободные объекты хранятся в однократно связанном списке, который мы назовем снискал свободных позиций (Ггее 1Ы). Список свободных позиций использует только массив леха, в котором хранятся указатели пех1 списка. Голова списка свободных позиций находится в глобальной переменной атее. Если динамическое множество, представленное связанным списюм Ь, не является пустым, список свободных позиций оказывается "переплетенным" со списком Т,, как показано на рис. 10.7. Заметим, что каждый объект в таюм представлении находится либо в списке Ь, либо в списке свободных позиций, но не в обоих списках одновременно.

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

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

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