Введение в информационные системы. Брюхомицкий Ю.А. - 80 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

80
PAGE PTR – указатель на следующую страницу.
На рис. 5.32 показана структура хранения фрагмента предметного ука-
зателя, представляющая собой многосвязный список с переменным числом ука-
зателей.
Рис. 5.32. Структура хранения фрагмента предметного указателя
Многосвязные списки с переменным числом указателей отображают
также в памяти ЭВМ произвольные несбалансированные деревья.
Списковые структуры. Во всех
ранее рассмотренных структурах дан-
ных каждый элемент структуры представляет собой отдельную запись об объ-
екте. Такой элемент структуры является неделимым и называется атомарным.
В ряде приложений элементы структуры данных сами могут быть
структурированы и представлены в виде списка. Примером является список,
отображающий процесс разборки автомобиля. Сначала он разбирается на ос-
новные
агрегаты, последние разбираются на узлы, которые в свою очередь
можно разобрать на отдельные детали.
Структура данных, в которой любой элемент может сам являться спи-
ском, называется списковой. В литературе встречаются также термины: ветвя-
щиеся списки, мультисписковые файлы, ветвящиеся файлы.
Списковую структуру можно изобразить в виде последовательностей, в
которых списки заключаются
в круглые скобки, а их элементы разделяются за-
пятыми:
(a, b, c, d); (a, (b, c, d), e, (f, g)).
Первая является линейным списком, так как каждый ее элемент являет-
ся атомарным. Вторая описывает списковую структуру: здесь a,e – атомарные
элементы (b,c,d), (f,g) – списки, являющиеся элементами списковой структуры.
Саму последовательность можно рассматривать как список, а элементы (
b,c,d),
(f,g) – как подсписки основного списка.
Списковую структуру можно изобразить в виде графа. Для второй из
приведенных выше списковых структур соответствующий граф будет иметь
вид, показанный на рис. 5.33.
Дерево Доступ
Двоичное Упорядоченное
32 44 112 Q
33 45 35 QQ

Страницы