6.4.Реализация списков

В этом разделе речь пойдет о нескольких структурах данных, которые можно использовать для представления списков. Мы рассмотрим реализации списков с помощью массивов, указателей и курсоров. Каждая их этих реализаций осуществляет определенные операторы, выполняемые над списками, более эффективно, чем другая.

Реализация списков посредством массивов

При реализации списков с помощью массивов элементы списка располагаются в смежных ячейках массива. На рис 6.1 представлена одна из возможных реализаций. В данном случае список представлен записью LIST, состоящей из поля last, указывающей на последний элемент списка и массива elements, в котором располагаются элементы списка. Поскольку элементы массива elements нумеруются с единицы, то значение last равно числу элементов списка. Длина массива elements храниться в константе maxlen.

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

Алгоритмы операторов INSERT, DELETE и LOCATE списка, реализованного на массиве, представлены блок-схемами на рис.6.2, 6.3 и 6.4 соответственно.

Реализацию остальных операторов списка сделайте самостоятельно.

Реализация списков с помощью указателей

Реализация списков с помощью указателей освобождает от использования непрерывной области памяти для хранения списка. Это позволяет избавиться от перемещения элементов списка при вставке или удалении элементов. Однако ценой за это удобство становится дополнительная память для хранения указателей. Структура списка, реализованного с помощью указателей, представлена на рис.6.5. Список представлен записью LIST, состоящей из двух полей: last и elements. В поле last хранится число элементов списка, а в поле elements - указатель на первый элемент списка. Элемент списка хранится в записи, состоящей из двух полей: element и next. Поле element содержит значение элемента списка, а поле next - указатель на следующий элемент списка.

Реализация операторов INSERT и DELETE представлена блок-схемами на рис.6.6 и 6.7 соответственно.

Реализацию остальных операторов списка сделайте самостоятельно.

Реализация списков с помощью курсоров

Некоторые языки программирования Fortran, Algol не имеют указателей. В этом случае указатели можно моделировать с помощью курсоров.

На рис. 6.8 показаны два списка M=a,b,c и L=d,e, вложенные в один массив SPACE длиной 10. Ячейки массива не занятые элементами списков образуют свободный список.

Реализация оператора INSERT списка, представленного с помощью указателей показана на рис.6.9.

Реализацию остальных операторов списка сделайте самостоятельно.