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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

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). В противном случае необходимо
обойти все элементы дерева, начиная с корневого элемента до тех пор, пока не будет обнаружено место
для вставки новых данных. Если у текущего элемента ключевое поле меньше, чем у вставляемых дан-
ных, то нужно продолжить обход дерева в направлении правой ветви от текущего элемента. В против-
ном случае обход продолжается в направлении левой ветви. Необходимо продолжать обход до тех пор,
right left
tree
first

Страницы