Паскаль
.pdf
Очередь – такая структура данных, при которой изъятие компонент происходит из начала цепочки, а запись – в конец цепочки.
В этом случае вводят два указателя: один на начало очереди, другой – на ее конец.
Запись новых компонент
вс, 10/03/2010 - 20:37 — tech
Пример. Пусть имеется цепочка динамических переменных:
Переменные имеют тип stackcomp:
type
…
stackcomp = record
I: integer; P: stackp
end;
Требуется вставить в цепочку новую компоненту “3” перед компонентой “4”, если известен указатель newp -> “3”.
Для записи этой новой компоненты достаточно выполнить операторы:
newp^.P := L^.P; L^.P := newp;
Первый оператор засылает в поле указателя новой компоненты
ссылку на компоненту “2”. Эта ссылка находится в поле указателя последней компоненты
т.е. получается следующий вид:
Второй оператор помещает в поле указателя компоненты “4” ссылку на компоненту “3”. Получается следующая картина:
Нелинейные структуры
ср, 10/06/2010 - 21:52 — tech
Введение в динамическую переменную двух и более полей указателей создает возможность получать нелинейные структуры.
Примеры нелинейных структур:
a) Текст
б) Двоичное дерево
можно представить так:
в) Направленный граф
можно представить так:
a) Текст – это связанная структура. Ее элементы представляют собой записи с тремя полями: первое поле содержит текстовую информацию (например, слово), второе поле либо указывает на первый элемент следующей строки, либо имеет значение Nil, третье – на следующий элемент данной строки.
б) Компонента двоичного дерева имеет также три поля: первое поле содержит основную информацию (число, символ, слово и т.д.), а второе и третье поля содержат ссылки на предыдущую и последующую компоненты дерева. Для некоторых компонентов дерева одно из этих полей либо оба имеют значение Nil.
в) Посредством ссылок можно выразить все связи в структуре, моделирующей направленный граф: вершинам графа соответствуют сами динамические переменные, а ребрам – ссылки.
Узлом называют переменную, содержащую два различных, отличных от Nil, значения указателя. Так, узловые элементы текста содержат ссылки на очередной элемент данной строки и на первый элемент следующей строки.
Нелинейные структуры удобны для задач поиска. Список упорядоченных элементов в виде двоичного дерева:
Узел 4 называется корнем дерева. Вход в дерево происходит только через корень. Для каждого узла различаются левое и правое поддеревья. Упорядоченность элементов следующая: элементы левого поддерева меньше узла и меньше элементов правого поддерева.
Время поиска в двоичном дереве сокращается по сравнению с линейной структурой с ~N до log2N, где N – число узлов в дереве. Компоненту двоичного дерева можно представить переменной типа
birec = record
I: integer; pred, succ: intp
end;
Каждая такая переменная содержит три поля: поле целого значения – поле I, поле указателя на предыдущий (в смысле упорядоченности)
элемент – поле pred и поле указателя на последующий элемент – поле succ.