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

UptoLike

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

Рубрика:

Рис. 5.33. Представление списковой структуры в виде графа

Для представления в памяти списковые структуры требуют связанного

представления. Оно обеспечивает динамическое размещение вершин, легкость

включения-исключения элементов, способность разделять подсписки, не требу-

ет предварительного резервирования памяти под массив.

Каждый элемент списковой структуры – это списковое слово. Списко-

вое слово

, соответствующее атомарной вершине, называется атомарным, а −

структурной вершине − структурным. Формат спискового слова показан на

рис. 5.34.

Рис. 5.34. Формат спискового слова

Поле DATA хранит информацию об объекте (имя подсписка, число

членов подсписка и т.п.).

В поле DPTR размещается указатель на первый элемент подсписка.

В поле RPTR размещается указатель на следующий

элемент основного

списка или на следующий элемент данного подсписка.

Атомарное слово индицируется пустым полем DPTR.

Представление в памяти ЭВМ списковой структуры, имеющей вид гра-

фа на рис. 5.33, будет иметь вид, показанный на рис. 5.35.

Рис. 5.35. Представление в памяти ЭВМ списковой структуры

RPTR DATA DPTR

fdb

Подсписок 1

DATA e a DATA Q

c d Qb f g Q

Вход в список Основной список

Подсписок 2