Основы программирования для автоматизированного проектирования и решения творческих задач. Романенко А.В - 30 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

other->last->next = other->next;
free(other);
Очистка памяти при окончании работы программы осуществляется аналогично удалению однонаправленного линейно-
го списка из памяти ЭВМ.
12.3 Буфер
Динамическая структура типа буфер (очередь) является распространенным динамическим типом данных, моделирую-
щим поведение реальных очередей в различных процессах. Иногда их называют структурами типа FIFO (от англ. "first in –
first out", т.е. первый пришел – первый ушел). Базой ее построения может выступать как однонаправленный, так и двуна-
правленный список. Главным ограничением при работе с буфером является то, что добавление нового элемента всегда осу-
ществляется в конец списка, а удаляется всегда первый элемент в списке.
12.4 Стек
Другой распространенной динамической структурой данных является стек. Иначе он называется структурой типа LIFO
(от англ. "last in – first out", т.е. последний пришел – первый ушел). Стеки часто используются для организации правильного
функционирования операционных систем и системных процессов. Базой его построения также может выступать однона-
правленный или двунаправленный список. Главным ограничением при работе со стеком является то, что добавление нового
элемента всегда осуществляется в конец списка. Удаляется всегда также последний элемент в списке.
12.5 Бинарное дерево
Бинарное дерево является одной из немногих динамических структур, внутренняя организация которых определяется
хранимой информацией. Внутренняя организация бинарного дерева решает задачу удобного хранения в оперативной памяти
ЭВМ больших объемов информации с учетом возможности быстрого доступа к требуемым данным. При этом данные хра-
нятся упорядоченно по ключевому полю.
Рис. 12 Устройство бинарного дерева
Организовать дерево можно на основе структурного типа, подобного двунаправленным спискам:
struct Tree
{
struct Tree *left, *right;
int key;
};
Каждый элемент дерева имеет в своем составе два указателя. Однако эти указатели связывают его не с предыдущим и после-
дующим элементами списка, а определяют две ветви с элементами следующего уровня (см. рис. 12). При этом в левой ветви
хранятся все данные с ключевым полем меньшим, чем у текущего элемента, а в правой – все данные с ключевым полем
большим, чем у текущего элемента. Элемент первого уровня называется корнем дерева. Порядок расположения элементов
определяется при вставке новых данных в структуру дерева.
Вставка элементов в бинарное дерево. Если дерево пустое (указатель на первый элемент равен NULL), то необходимо
создать корневой элемент дерева. Оба его указателя в момент создания не связаны с ветвями, поэтому оба указателя должны
быть пустыми (NULL). В противном случае необходимо обойти все элементы дерева, начиная с корневого элемента до тех
пор, пока не будет обнаружено место для вставки новых данных. Если у текущего элемента ключевое поле меньше, чем у
вставляемых данных, то нужно продолжить обход дерева в направлении правой ветви от текущего элемента. В противном
случае обход продолжается в направлении левой ветви. Необходимо продолжать обход до тех пор, пока не будет обнаружен
элемент, у которого указатель на ветвь в направлении перехода содержит константу NULL. Это и будет место для вставки
нового элемента в структуру дерева (создания новой его ветви).
П р и м е р 34
Последовательность действий, необходимая для вставки нового элемента в бинарное дерево.
struct Tree *first = NULL, *tree;
int key;
…

Страницы