Алгоритмы - построение и анализ (1021735), страница 53
Текст из файла (страница 53)
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), хранящуюся в дважды связанном списке, представленном с помошью нескольких массивов.
Выполните это же задание для представления с помощью одного массива. 10.3-2. Разработайте процедуры Аш)слте Овтест и Ркее Овзест для однород- ного набора объектов, реализованных с помошью одного массива. 10.3-3. Почему нет необходимости присваивать или вновь устанавливать значения полей ргеи при реализации процедур АЕЕОсАте Овшст и Ркее ОВ1ЕСТ? 10.3-4. Зачастую (например, при страничной организации виртуальной памяти) все элементы списка желательно располагать компактно, в непрерывном участке памяти. Разработайте такую реализацию процедур АееосАте Овшст и Ркее Овзест, чтобы элементы списка занимали позиции 1..т, где тп — количество элементов списка. (Указание: воспользуйтесь реализацией стека с помощью массива.) 10.3-5.
Пусть Х, — дважды связанный список длины тп, который хранится в массивах кер, ртеи и пех1 длины и. Предположим, что управление этими массивами осуществляется с помощью процедур Аы.Ослте Овтест и Ркее Овтест, использующих дважды связанный список свободных позиций г'. Предположим также, что ровно т из и элементов находятся в списке Х, а остальные и — т элементов — в списке свободных позиций. Разработайте процедуру Сомрлст~ет 1лзт(Х, Р), которая в качестве параметров получает список Х,и список свободных позиций Г; и перемешает элементы списка Х, таким образом, чтобы они занимали ячейки массива с индексами 1,2,..., пт, а также преобразует список свободных позиций Г так, что он остается корректным и содержит ячейки массива Часть П1.
Структуры данных 274 с индексами т + 1, т + 2,..., и. Время работы этой процедуры должно быть равным О (и), а объем использующейся ею дополнительной памяти не должен превышать некоторую фиксированную величину. Приведите тщательное обоснование корректности представленной процедуры. 10.4 Представление корневых деревьев Приведенные в предыдущем разделе методы представления списков подходят для любых однородных структур данных.
Данный раздел посвящен задаче представления корневых деревьев с помощью связанных структур данных. Мы начнем с рассмотрения бинарных деревьев, а затем рассмотрим представление деревьев с произвольным количеством дочерних элементов. Каждый узел дерева представляет собой отдельный обьект. Как и при изучении связанных списков, предполагается„ что в каждом узле содержится поле йеу. Остальные интересующие нас поля — это указатели на другие узлы, и их внд зависит от типа дерева. Бинарные деревья Как показано на рис.
10.9, для хранения указателей на родительский, дочерний левый и дочерний правый узлы бинарного дерева Т, используются поля р, 1ей и гзд61. Если р [ж] = ьа., то х — корень дерева. Если у узла х нет дочерних узлов, то 1еГг [х] = г1д1з1 [х] = ьл~.. Атрибут гио1 [Т] указывает на корневой узел дерева Т. Если тоо1 [Т] = ни., то дерево Т пустое.
Рис. 10.9. Представление бинарного дерева Т 1поле лисеу не показано) Глава 10. Элементарные структуры данных 275 Корневые деревья с произвольным ветвлением Схему представления бинарных деревьев можно обобщить для деревьев любого класса, в которых количество дочерних узлов не превышает некоторой константы й. При этом поля правый и левый заменяются полями сЬзЫы сйгЫз,..., с)гав. Если количество дочерних элементов узла не ограничено, то эта схема не работает, поскольку заранее не известно, место для какого количества полей (или массивов, при использовании представления с помощью нескольких массивов) нужно выделить. Кроме того, если количество дочерних элементов )г ограничено большой константой, но на самом деле у многих узлов потомков намного меньше, то значительный объем памяти расходуется напрасно. К счастью, существует остроумная схема представления деревьев с произвольным количеством дочерних узлов с помощью бинарных деревьев.
Преимущество этой схемы в том, что для любого корневого дерева с и дочерними узлами требуется объем памяти О (и). На рис. 10.10 проиллюстрировано представление с левым дочерним и прааьии сестринским узлами Пей-сЬ11б, пяЬг-з1Ь11ля гергезепгабоп). Как и в предыдущем представлении, в каждом узле этого представления содержится указатель р, а атрибут пюг 1Т] указывает на корень дерева Т. Однако вместо указателей на дочерние узлы каждый узел гс содержит всего два указателя: 1. в поле 1еф сйгЫ [х) хранится указатель на крайний левый дочерний узел узла х; «.о~:, Г) У-'.. -- .«-!, 1~'! Рис. 10.10. Представление дерева с левым дочерним и правым сестринским узлами 276 Часть 111. Структуры данных 2.
в поле г1дЫ з1Ыйтд [х] хранится указатель на узел, расположенный на одном уровне с узлом х справа от него. Если узел т не имеет потомков, то 1е71 сЬ|1а[х] = мь, а если узел х— крайний правый дочерний элемент какого-то родительского элемента, то гтдй1 иЫгпд [х] = мь. Другие представления деревьев Иногда встречаются и другие способы представления корневых деревьев. Например, в главе 6 описано представление пирамиды, основанной на полном бинарном дереве, в виде индексированного массива.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
