Комбинированные структуры данных: массивы и списки списков

Более сложным случаем является использование массива списков или списка списков. Здесь каждый элемент массива или основного списка является началом вспомогательного списка, причем эти вспомогательные списки могут содержать разное число элементов (но, конечно, одного типа).

	next nil		next адрес		nil адрес

адрес вспом. списка

адрес вспом. списка

. . . . .

адрес вспом. списка

В обоих случаях в первую очередь вводится тип данных, описывающий структуру элементов вспомогательного списка:

Type pSubList = ^ TSubList;

TSubList = record

<описание информационных полей>;

next : pSubList;

end;

После этого описывается либо основной массив указателей, либо структура элементов основного списка:

Type TMainArray = array [ 1 . . N ] of pSubList;

pMainList = ^ TMainList;

TMainList = record

NextMain : pMainList;

FirstSub : pSubList;

end;

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

pCurrentMain := “адрес первого элемента основного списка”;

while pCurrentMain <> nil do

Begin

pCurrentSub := pCurrentMain^.FirstSub;

while pCurrentSub <> nil do pCurrentSub := pCurrentSub^.next;

end;

pCurrentMain := pCurrentMain^.NextMain;

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

Иногда удобно в элементах основного списка хранить не только адрес первого элемента вспомогательного списка, но и адрес последнего элемента. Естественно, что при необходимости как основной, так и вспомогательные списки могут быть двунаправленными.

Кроме того, поскольку стеки и очереди можно рассматривать как частные случаи списков, легко можно реализовать такие структуры как массив или список стеков, массив или список очередей и.т.д.

4.4. Практические задания.

Задание 1. Реализовать линейный динамический двунаправленный список со следующим набором операций:

· просмотр списка в прямом и обратном направлениях

· поиск заданного элемента в прямом и обратном направлениях

· добавление элемента перед или после заданного

· удаление заданного элемента

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

Задание 2.Реализовать набор подпрограмм для выполнения основных операций с массивом списков. Каждый элемент массива хранит только указатель на начало связанного списка. Сам базовый массив работает на основе сдвиговых операций. Основные операции:

· полный проход по всей структуре

· поиск заданного элемента

· добавление нового элемента в массив с пустым связанным списком

· добавление нового элемента в связанный список

· удаление элемента из связанного списка

· удаление элемента из базового массива

Задание 3.Реализовать набор подпрограмм для выполнения основных операций со списком списков. Требования аналогичны предыдущему заданию.

4.5. Контрольные вопросы по теме

1. Какие преимущества и недостатки имеют двунаправленные списки?

2. Какую структуру имеют элементы двунаправленных списков?

3. Почему двунаправленные списки чаще всего делают кольцевыми?

4. Как используются ссылочные поля заголовка двунаправленного списка?

5. Какие описания необходимы для динамической реализации двунаправленных списков?

6. Какие переменные используются при реализации операций с динамическими двунаправленными списками?

7. Как создается пустой динамический двунаправленный список?

8. Как реализуется проход в прямом направлении по динамическому двунаправленному списку?

9. Как реализуется проход в обратном направлении по динамическому двунаправленному списку?

10. Как реализуется поиск в прямом направлении по динамическому двунаправленному списку?

11. Как реализуется поиск в обратном направлении по динамическому двунаправленному списку?

12. Как реализуется удаление элемента в динамическом двунаправленном списке?

13. Как реализуется добавление элемента после заданного в динамическом двунаправленном списке?

14. Как реализуется добавление элемента перед заданным в динамическом двунаправленном списке?

15. Как выполняется перестановка элементов в массиве указателей?

16. Какие описания необходимы для реализации списка указателей?

17. Как выполняется добавление элемента в список указателей?

18. Как выполняется удаление элемента из списка указателей?

19. Как выполняется перестановка элементов в списке указателей?

20. Что такое массив списков и как он описывается?

21. Что такое список списков и как он описывается?

22. Как выполняется полный проход по массиву списков?

23. Как выполняется полный проход по списку списков?

24. Как выполняется поиск элемента в массиве списков?

25. Как выполняется поиск элемента в списке списков?

26. Как выполняется удаление элемента из массива списков?

27. Как выполняется удаление элемента из списка списков?

28. Какие особенности имеет операция добавление элемента в массив или список списков?

Тема 5. Основные понятия о древовидных структурах