1.3. Нелинейные структуры данных

1.3.1. Мультисписки

Мультисписок - это структура данных, состоящая из элементов, со­держащих такое число указателей, которое позволяет организовать их одновременно в виде нескольких различных списков (рис. 11).

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

Указатель на список 1

Список 1

♦

						nil
A		B		C		D

Список 2

Указатель на список 2

♦

				nil
D		B		C

Мультисписок

Указатель на список 2

Указатель на список 1

♦

								nil
nil					nil
A		B			C			D

Рис. 11. Мультисписок

При использовании традиционных списков для представления повто­ряющихся данных происходит нерациональное использование памяти за счет дублирования динамических элементов, хранящих повторяющиеся дан­ные. Использование мультисписков позволяет устранить этот недостаток.

Поиск в мультисписке происходит аналогично поиску в линейном списке, но при этом используется только один указатель, соответству­ющий списку, в котором осуществляется поиск.

49

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

1.3.2. Слоеные списки

Слоеные (skip), или разделенные, списки – это связные списки, ко­торые позволяют перескакивать через некоторое количество элементов (рис. 12). Это позволяет преодолеть ограничения последовательного по­иска, являющейся основной причиной низкой эффективности поиска в линейных списках. В то же время вставка и удаление остаются сравни­тельно эффективными.

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

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

Указатель на линейный Линейный список

список

f

										nil
Александр		Алексей		Андрей		Борис		Павел		Петр

Указатель

на слоеный Слоеный список

список

•		nil		nil	Ч			nil		nil
										nil
Александр		Алексей		Андрей		Борис		Павел		Петр

Рис. 12. Слоеный список и его организация 50

следующая группа отсутствует или элемент не является первым в груп­пе, то этот дополнительный указатель принимает значение nil.

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

Если реализован только один уровень, то это, фактически, обычный список и время поиска пропорционально O(n). Однако если имеется достаточное число уровней, то разделенный список можно считать де­ревом с корнем на высшем уровне, а для дерева время поиска, как будет показано ниже, пропорционально O(log n).