|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[68] Рис. 11.6 Тот же список, что на рис. 11.3а и 11.5, реализованный на базе единственного массива А. Каждой записи соответствует тройка идущих подряд элементов массива. Полям key, next и prev соответствуют сдвиги 0, 1 и 2. Указатель на запись - индекс первого из отведённых для неё элементов. Светлосерые записи входят в список; стрелками изображено действие указателей. ментов, каждый из которых имеет несколько полей, то на каждый элемент отводится непрерывный участок памяти, в котором друг за другом размещаются значения полей. Указателем на элемент обычно считают адрес первой ячейки этого участка; адреса полей получаются сдвигом на определённые константы. При реализации записей на базе массива можно воспользоваться той же стратегией. Рассмотрим один-единственный массив А. Каждая запись будет занимать в нём непрерывный участок A[j .. к]. Указатель на запись - это индекс j; каждому полю записи соответствует число из интервала [0 .. к - j] - сдвиг. Например, при представлении всё того же списка, что и на рис. 11.3а и 11.5, можно решить, что полям key, next и prev соответствуют сдвиги 0, 1 и 2. Тогда значение prev[i], где г - указатель (= индекс в массиве А), есть не что иное, как А[г + 2] (см. рис. 11.6). Такое представление позволяет хранить в одном массиве записи разных типов (отводя под них участки разной длины), но для наших целей будет достаточно представления в виде нескольких массивов, поскольку большинство структур данных, с которыми мы будем иметь дело, состоят из однотипных записей. Выделение и освобождение памяти При добавлении нового элемента в список надо отвести под него место в памяти. Стало быть, необходимо вести учёт использования адресов. В некоторых системах этим ведает специальная подпрограмма - сборщик мусора (garbage collector), которая определяет, какие участки памяти более не используются, и возвращает их для повторного использования. Во многих случаях, однако, можно возложить обязанности по выделению и освобождению памяти на саму структуру данных. В этом разделе мы покажем, как это делается; в качестве примера рассмотрим двусторонне связанный список, представленный с помощью нескольких массивов. Пусть массивы, с помощью которых мы представляем наш спи- Рис. 11.7 Работа процедур allocate-object и Free-Object, (а) Тот же список, что на рис. 11.5 (светло-серый) и список свободных позиций (тёмно-серый). Структура списка свободных позиций изображена с помощью стрелок, (б) Вот что получится после вызова allocate-OBJECT0 (возвращает значение 4), присваивания &еу[4] <- 25 и вызова LlST-lNSERT(L, 4). Новый список свободных позиций начинается с 8 (таково было значение пеж£[4]). (в) Теперь мы вызвали LlST-delete(L, 5), а затем Free-Object(5). Позиция 5 - голова нового списка свободных позиций, за ней следует 8. сок, имеют длину то, и пусть в данный момент в списке содержится п то элементов. Остальные п - то мест (позиций) в массиве свободны (free). Мы будем хранить свободные позиции в односторонне связанном списке, называемом списком свободных позиций (free list). Этот список использует только массив next: именно, next[i] содержит индекс свободной позиции, следующей за свободной позицией г. Голова списка хранится в переменной free. Список свободных позиций хранится вперемежку со списком L (рис. 11.7). Обратите внимание, что каждому числу из отрезка [1;то] отвечает элемент либо списка L, либо списка свободных мест. Список свободных позиций ведёт себя как стек: из всех свободных участков памяти под новую запись выделяется тот, который был освобождён последним. Поэтому для выделения и освобождения памяти можно воспользоваться реализацией стековых операций Push и Pop на базе списка. В приводимых ниже процедурах Allocate-Object (выделить место) и Free-Object (освободить место) подразумевается, что в глобальной переменной free записан индекс первой (в списке) свободной позиции. Рис. 11.8 Списки L\ (светло-серый) и L2 (тёмно-серый), а также список свободных мест (черный) хранятся в одной тройке массивов. Free-0biect(2;) 1next[x] <- free 2free <- x Первоначально список свободных позиций содержит п элементов. Если свободного места не осталось, процедура Allocate-Obiect сообщает об ошибке. Часто один список свободных позиций обслуживает сразу несколько динамических множеств (рис. 11.8). Описанные процедуры выделения и освобождения памяти просты и удобны (работают за время 0(1)). Их можно приспособить для хранения однотипных записей любого вида, отведя одно из полей записи под хранение индекса next (в свободных позициях). Упражнения 11.3-1 Следуя образцу рис. 11.5, изобразите представление последовательности (13,4,8,19,5,11) в виде двусторонне связанного списка, реализованного с помощью трех массивов; по образцу рис. 11.6 изобразите тот же список, реализованный с помощью одного массива. 11.3-2 Напишите процедуры Allocate-Obiect и Free-Obiect для случая однотипных записей, хранящихся в одном массиве. 11.3-3 Почему в процедурах Allocate-Obiect и Free-Obiect никак не фигурирует поле prev? 11.3-4 Часто (например, при страничной организации виртуальной памяти) бывает полезно хранить элементы списка в непрерыв- Allocate-Obiect() 1 if free = nil |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||