Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 54
Текст из файла (страница 54)
Покажите также, как можно обратить порядок элементов в таком списке за время О (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 ~п~/ / Йсо Рис. 10.6. Связанный список, представленный единственным массивом которое нам предстоит рассмотреть, состоит из однородных элементов, для наших целей достаточно использовать представление объектов с помощью нескольких массивов. Выделение и освобождение памяти При добавлении нового элемента в список надо выделить для него место в памяти, что влечет за собой необходимость учета использования адресов. В некоторых системах функцию определения того, какой объект больше не используется, выполняет "сборщик мусора" (йагЬаде со11есгог).
Однако многие приложения достаточно просты и вполне способны самостоятельно возвращать неиспользованное объектами пространство модулю управления памятью. Давайте рассмотрим задачу выделения и освобождения памяти для однородных объектов на примере дважды связанного списка, представленного с помощью нескольких массивов. Предположим, что в таком представлении используются массивы длиной ти, и что в какой-то момент динамическое множество содержит и < т элементов.
В этом случае и объектов представляют элементы, которые находятся в данный момент времени в динамическом множестве, а т — и элементов свободны. Их можно использовать для представления элементов, которые будут вставляться в динамическое множество в будущем. Свободные объекты хранятся в однократно связанном списке, который мы назовем спискам свободных позиций (Ггее 11зг). Список свободных позиций использует только массив пех1, в котором хранятся указатели пех1 списка.
Головной элемент списка свободных позиций находится в глобальной переменной ггее. Когда динамическое множество, представленное связанным списком Ь, не является пустым, список свободных позиций используется вместе со списком Т,, как показано на рис. 10.7. Заметим, что каждый объект в таком представлении находится либо в списке Ь, либо в списке свободных позиций, но не в обоих списках одновременно. Список свободных позиций — это стек: очередной выделяемый объект является последним освобожденным. Таким образом, реализовать процедуры выделения и освобождения памяти для объектов можно с помощью стековых операций Ризн 272 Часть й1. Структуры данньп /атее 1Ц— т (4) ьэ ! з 3 т з 6 7 8 вел мР Рис.
10.7. Процедуры выделения н освобождения объекта и Рои Глобальная переменная ~тее, использующаяся в приведенных ниже проце- дурах, указывает на первый элемент списка свободных позиций: АН.ОСАТЕ ОВ1ЕСТО 1 11 /гее = ХИ. 2 1Ьеп еггог "Нехватка памяти" 3 е1ае х — аггее 4 атее +- пех1(х1 5 гетпгп х ркее Онзест(х) 1 пех1[х) — ~тес 2 1гее — х В начальный момент список свободных позиций содержит все и объектов, для которых не выделено место.
Когда в списке свободных позиций больше не остается элементов, процедура Аи.ОСАТЕ ОВ1ЕСТ выдает сообщение об ошибке. На рис. 10.7 показано, как изменяется исходный список свободных позиций (рис. 10.7а) при вызове процедуры Аи.оСАТЕ ОВ1ЕСТО, которая возвращает индекс 4, и вставке в эту позицию нового элемента (рис. 10.7б), а также после вызом 1Бт 1эееете(Ь, 5) с последующим вызовом Рнее ОВЗест(5) (рис. 10.7в). Часто один список свободных позиций обслуживает несколько связанных списков. На рис.
10.8 изображены два связанных списка и обслуживающий их список свободных позиций. Время выполнения обеих процедур равно О (1), что делает их весьма практичными. Эти процедуры можно модифицировать так, чтобы они работали с любым Глава 10. Элементарные структуры данных 273 Гч '(3) Хнг Рис. 10.8.
Связанные списки Х1 (светло-серый) и Х,з (темно-серый), и обслуживаюший их список свободных позиций (черный) набором однородных объектов, лишь бы одно из полей объекта работало в качестве поля пех1 списка свободных позиций. Упражнения 10.3-1. Изобразите последовательность (13, 4, 8, 19, 5, 11), хранящуюся в дважды связанном списке, представленном с помошью нескольких массивов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
