 |
Добавление элемента в конец списка
|
|
|
|
Удаление первого элемента
Вставка элемента в начало списка
Формирование списка с одновременным упорядочением его элементов по заданному признаку
Двунаправленные списки
По однонаправленному списку можно двигаться только в одну сторону - от первого элемента к последнему. Между тем нередко необходимо произвести обработку элементов, предшествующих элементу с заданным свойством. Для устранения этого неудобства в каждый элемент добавляется еще одно поле prev - указатель на предшествующий элемент:
type pointer = ^element;
element = record
info:TValue;
prev:pointer;
next:pointer;
end;
dlist = pointer;
Динамическая структура состоящая из звеньев такого типа называется двунаправленным списком. Наличие ссылки на предыдущий элемент списка позволяет двигаться в любом направлении по списку. В поле prev заглавного звена стоит ссылка NIL, так как у заглавного звена нет предыдущего. Иногда значением поля next последнего звена ставят ссылку на заглавное звено, а в поле prev заглавного звена - ссылку на последнее звено. Список замыкается в "кольцо". Списки такого вида называют кольцевыми.
Стеки
Стек - структура данных, в которой можно добавлять и удалять элементы данных, при этом непосредственно доступен только последний добавленный элемент. Как и очередь стек в Паскале можно организовать в виде линейного списка:
type pointer = ^elem;
elem = record
info:TValue;
sled:pointer;
end;
Stask = pointer;
или отображения на массив:
const N=10;
type Stask = record
tp:integer;
body:array [1..N] of TValue;
end;
Надо заметить, что стек - одна из наиболее используемых структур данных, которая оказывается весьма удобной при решении различных задач.
Для работы со стеком реализуются процедуры:
|
|
|
Init(S) - процедура создания стека S.
Empty(S) - логическая функция, выдающая true если стек пуст и false если в нем есть элементы.
Push(S,v) - процедура вставляющая новый элемент v в стек.
Pop(S) - процедура выталкивающая верхний элемент из стека.
Top(S) - функция, возвращающая значение верхнего элемента стека.
Size(S) - функция,возвращающая число элементов стека.
Display(S) - процедура, распечатывающая содержимое стека.
Имея эти базовые процедуры довольно просто реализовать процедуры: вставки элемента в стек под каким-то номером (Insert(S,v,n)) и удаления элемента из стека по значению (Remove(S)).
Формирование стека
Включение нового узла в стек
Удаление узла из стека
Очереди
Обработка элементов списка сводится к корректировке соответствующих ссылок. Списки также активно используются для организации еще более сложных структур данных, например очереди.
Очередь - упорядоченный, одномерный, динамически изменяемый набор компонент, в котором включение новых компонент производится с одного конца очереди, а доступ и исключение с другого.
Длинной очереди называется количество ее компонент. Очередь является динамическим объектом и длинна ее не фиксируется. Так как в Паскале нет структурного типа очередь, его можно отобразить на уже имеющиеся структуры: файл и массив. Отображение очереди из целых чисел на массив можно реализовать так:
const N=10;
type Qel:integer;
Queue: record
first,last:integer;
body: array [1..N] of Qel;
end;
где first и last - указатели на первый и последний элемент очереди соответственно, а N - максимальное число компонент очереди. Отображение на массив накладывает ограничение на длину очереди, кроме того программист сам запрещает себе прямой доступ к элементам массива.
В Паскале очередь может быть организована и как двунаправленный список:
type T = Qel;
pointer = ^T;
Queue = record
info:T;
pred,sled:pointer;
end;
где pred и sled - указатели на предыдущий и следующий элемент очереди. Операции над очередью при такой организации определяются аналогично.
|
|
|
Для работы с очередью реализуются следующие процедуры:
Init(Q) - процедура создания очереди Q.
Empty(Q) - логическая функция, если очередь пуста Empty выдает значение true, если нет - false.
Pop(Q) - процедура, выталкивающая первый элемент очереди Q.
Top(Q) - функция, выдающая значение первого элемента очереди.
Push(Q,v) - процедура, добавляющая новый элемент v типа Qel в конец очереди Q.
Print(Q) - процедура, распечатывающая содержимое очереди.
Size(Q) - функция, выдающая число компонент (длину) очереди.
Отображение очереди на файл выглядит так:
type T = Qel;
Queue = file of T;
Операции над очередью определяются также как и при отображении на массив, а обработка элементов ведется с использованием буферной переменной. При таком отображении время на операции тратится больше, так как файл приходится все время "перематывать".
Дек
Deque (double-ended queue) - двухсторонняя очередь, структура данных, где элементы могут добавляться и удаляться с обоих концов. Дек является и стеком и очередью одновременно. При реализации должны быть определены операции: вставка нового элемента в начало дека, вставка нового элемента в конец дека, удаление (или просмотр) элемента из начала дека, удаление элемента из конца дека.
Граф
Множество объектов соединенных произвольным образом, но не более чем одной линией связи между двумя объектами - называется графом.Связный граф - когда имеется путь между двумя вершинами, ориентированный граф - в котором линии связи имеют определенное направление.При использовании графов часто возникает проблема поиска пути между двумя вершинами.
В Паскале удобно для этой цели представлять граф в виде матрицы смежности, в которой хранится информация о связях между вершинами графа.Если граф содержит N вершин, то матрица смежности - квадратная булевская матрица N*N, в которой М(i,j)=true, если есть связь между i-ой и j-ой вершинами и М(i,j)=false в противном случае. Для неориентированных графов матрица смежности симметрична.
Граф с К вершинами можно также представить в виде К списков, соответствующих вершинам и содержащих номера вершин с которыми у данной есть связь.Если граф меняется в процессе обработки, т.е. добавляются и удаляются вершины и линии связи, то удобнее использовать списки.
|
|
|
Графы применяются в задачах машинного проектирования и в создании систем искусственного интеллекта.
Деревья
Дерево - частный случай графа. Структура определяется рекурсивно,образованная данным элементом, называемым корнем дерева, и конечным списком с переменным числом элементов - деревьев того же типа, называемых поддеревьями. Двоичным или бинарным деревом называется дерево состоящее из корня, правого и левого поддеревьев.
В Паскале двоичное дерево можно определить так:
type BTree = ^BNode;
BNode = record
info:TValue;
left,right:BTree;
end;
При анализе структур данных, заданных в виде дерева, применяются различные способы просмотра и перебора узлов. Основная особенность каждого обхода заключается в том, что просматриваются все узлы дерева в некотором порядке, причем каждый узел обрабатывается ровно один раз.
Для бинарного дерева определены три способа обхода: прямой или префиксный (корень - левое поддерево - правое поддерево),обратный или инфиксный (левое поддерево - корень - правое поддерево) и концевой или постфиксный (левое поддерево - правое поддерево - корень).
При обходе дерева используются рекурсивные процедуры или стек. В прошитых деревьях используются дополнительные указатели на наличие поддеревьев (LTAG и RTAG). Введение дополнительных указателей не приводит к большому увеличению затрат памяти, но позволяет при обходе отказаться от стека.
Надо отметить,что любое дерево общего вида можно представить в виде двоичного, надо в исходном дереве у каждого узла соединить его сыновей от старшего к младшему и убрать все связи узла с сыновьями, оставив только связь со старшим сыном.
Над деревьями удобно определить операции: чтение информационной части из узла дерева, создание дерева, присоединение к узлу нового поддерева, удаление поддерева.
Особенно полезны деревья при сортировке. Алгоритм состоит в том, что при просмотре данных очередной элемент помещается в двоичное дерево. Ключ нового элемента сравнивается с ключом текущего узла.Если указатель текущего узла NIL, то указатель на новый узел добавляется в то место откуда был извлечен NIL. Если ключ нового узла меньше ключа текущего узла, то поиск места для нового узла продолжается в левом поддереве, если больше - в правом. После того как все данные занесены в двоичное дерево сортировки, выполняется обратный обход дерева с выводом.
Деревья применяются также при интерпритации и вычислении как арифметических, так и логических функций.
|
|
|
A - Вера в «Ахира» (конец света)
I л конец, окончание
I.XIV. «Элементарная сердечно-легочная реанимация»
III. Внутренний фотоэффект и его виды. Устройство и принцип работы селенового фотоэлемента.
INSERT: Добавление информации в таблицу
RS – триггеры на логических элементах
void CMenu::p_menu_ins()// добавление
Америке может прийти конец?
В которой наконец-то мы должны попрощаться
Взаимодействие между элементами симметрии в кристалле
