Управление памятью для списков

Использование параллельных массивов

Значения всех элементов списка можно хранить в одном массиве, а ссылки на следующий элемент - в другом массиве. Массивов нужно по количеству полей, если элемент списка состоит из нескольких полей. Разные поля каждого элемента располагаются в разных массивах с одним и тем же индексом. Количество элементов в этих массивах одинаково. Такие массивы на рисунках удобно изображать рядом ("параллельно") и их называют параллельными.

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

На рис. 15.9 приведен пример списка идентификаторов (рис. 15.2) в виде параллельных массивов id и uk.

	Индексы	Значения Массив id	Ссылки Массив uk
		Не используются
		TEXT

p		à		A1
Указатель списка
		SL
		SIMV
isv		à
Указатель списка
свободной памяти	...	…	…

	N

Рис. 15.9. Пример размещения списка идентификаторов в параллельных массивах (со списком свободной памяти)

Для таких списков можно, по аналогии с обозначениями для ссылочных переменных (пример 15.1), поместить в программу описания из примера 15.2.

Пример 15.2. Описание данных для списков с использованием параллельных массивов.

#define N 1000 /* Максимальное кол-во элементов списков */

#define NOL 0 /* Пустой указатель */

typedef int ukaz; /* Тип указателя */

char id [N+1] [8]; /* Значения элементов (идентификаторы) */

ukaz uk [N+1]; /* Указатели следующего элемента */

ukaz p; /* Указатель списка */

ukaz i, j; /* Указатели элементов списка */

char nov_id[8]; /* Новый идентификатор */

Эти описания позволяют использовать обозначения из таблицы 15.1. Элемент списка, на который указывает i, в комментариях будем обозначать *i, как при использовании ссылочных переменных, хотя по правилам языка C здесь это обозначение бессмысленно и в операторах его применять нельзя.

Для получения и освобождения памяти в куче, размещенной в параллельных массивах, требуется своя система управления памятью. Она должна учитывать свободные и занятые участки кучи, выделять по запросу программы свободный участок для создания нового элемента и освобождать его, когда он становится ненужным. Для этого сцепим свободные участки в виде списка свободной памяти (рис. 15.9).

Для управления памятью необходимы подпрограммы, аналогичные библиотечным функциям динамического распределения памяти malloc и free языка C. В примере 15.3 это - функции nov_el, osvob и inic_kuchi.

Подпрограмма inic_kuchi создает список свободной памяти, включающий все элементы кучи (кроме 0-го, т. к. 0 играет роль пустой ссылки). Функция nov_el выдает индекс свободной позиции (нулевой индекс обозначает отсутствие свободного места). Подпрограмма osvob вставляет элемент с заданным индексом в список свободной памяти.

Пример 15.3. Система управления памятью для списков примера 15.2

ukaz isv; /* Указатель списка свободной памяти */

/* Инициализация кучи - создание списка свободной памяти, */

/* охватывающего всю кучу (0-й элемент не используется) */

void inic_kuchi ()

{ for (isv=1; isv<N; isv++)

uk[isv] = isv + 1;

uk[N] = NOL; isv = 1;

}

/* Выделение памяти для нового элемента */

ukaz nov_el () /* Указатель (индекс) выделенной позиции */

{ukaz i;