Динамические структуры данных очереди стеки деревья

Работа с динамической памятью

Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память следует распределять во время выполнения программы по мере необходимости отдельными блоками. Блоки связываются друг с другом с помощью указателей. Такой способ организации данных называется динамической структурой данных, поскольку она размещается в динамической памяти и ее размер изменяется во время выполнения программы.

Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями. Динамическая структура, в отличие от массива или записи, может занимать несмежные участки оперативной памяти.

Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы. Например, если в процессе выполнения программы требуется многократно упорядочивать большой массив данных, имеет смысл организовать его в виде линейного списка. При решении задач поиска элемента в тех случаях, когда важна скорость, данные лучше всего представить в виде бинарного дерева.

Элемент динамической структуры состоит из двух частей: информационной, ради хранения которой и создается структура, и указателей, обеспечивающих связь элементов друг с другом. Элемент описывается в виде записи, например:

type pnode = ^node; node = record d : word; < информационная >s : string; < часть >p : pnode; < указатель на следующий элемент >end;

ПРИМЕЧАНИЕ Обратите внимание, что тип указателя pnode на запись node определен раньше, чем сама запись. Это не противоречит принципу «использование только после описания», поскольку для описания переменной типа pnode информации вполне достаточно.

Рассмотрим принципы работы с основными динамическими структурами.

Стеки

Стек является простейшей динамической структурой. Добавление элементов в стек и выборка из него выполняются из одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека.

Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым обслужен). Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Для работы со стеком используются две статические переменные: указатель на вершину стека и вспомогательный указатель.

Тип указателей должен соответствовать типу элементов стека.

В пример 5.1 приведена программа, которая формирует стек из пяти целых чисел и их текстового представления и выводит его на экран. Функция занесения в стек по традиции называется push , а функция выборки — pop .

program stack; const n = 5; type pnode = ^node; node = record < элемент стека >d : word; s : string; p : pnode; end; var top : pnode; < указатель на вершину стека >i : word; s : string; const text : array [1 .. n] of string = ('one', 'two', 'three', 'four', 'five'); < ------------------------------ занесение в стек --------------------------- >function push(top : pnode; d : word; const s : string) : pnode; var p : pnode; begin new(p); p^.d := d; p^.s := s; p^.p := top; push := p; end; < ------------------------------ выборка из стека --------------------------- >function pop(top : pnode; var d : word; var s : string) : pnode; var p : pnode; begin d := top^.d; s := top^.s; pop := top^.p; dispose(top); end; < ------------------------------- главная программа ----------------------------- >begin top := nil; for i := 1 to n do top := push(top, i, text[i]); < занесение в стек: >while top <> nil do begin < выборка из стека: >top := pop(top, i, s); writeln(i:2, s); end; end.

Очереди

Очередь — это динамическая структура данных, добавление элементов в которую выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым обслужен). В программировании очереди применяются очень широко — например, при моделировании, буферизованном вводе-выводе или диспетчеризации задач в операционной системе.

Для работы с очередью используются указатели на ее начало и конец, а также вспомогательный указатель:

Тип указателей должен соответствовать типу элементов, из которых состоит очередь.

В пример 5.2 приведена программа, которая формирует очередь из пяти целых чисел и их текстового представления и выводит еe на экран. Для разнообразия операции с очередью оформлены в виде процедур. Процедура начального формирования называется first , помещения в конец очереди — add , а выборки — get .

program queue; const n = 5; type pnode = ^node; node = record < элемент очереди >d : word; s : string; p : pnode; end; var beg, fin : pnode; < указатели на начало и конец очереди >i : word; s : string; const text : array [1 .. n] of string = ('one', 'two', 'three', 'four', 'five'); < ------------------ начальное формирование очереди --------------------------- >procedure first(var beg, fin : pnode; d : word; const s : string); begin new(beg); beg^.d := d; beg^.s := s; beg^.p := nil; fin := beg; end; < --------------------- добавление элемента в конец --------------------------- >procedure add(var fin : pnode; d : word; const s : string); var p : pnode; begin new(p); p^.d := d; p^.s := s; p^.p := nil; fin^.p := p; fin := p; end; < ---------------------- выборка элемента из начала --------------------------- >procedure get(var beg : pnode; var d : word; var s : string); var p : pnode; begin d := beg^.d; s := beg^.s; p := beg; beg := beg^.p; dispose(p); end; < ------------------------------- главная программа --------------------------- >begin < занесение в очередь: >first(beg, fin, 1, text[1]); for i := 2 to 5 do add(fin, i, text[i]); < выборка из очереди: >while beg <> nil do begin get(beg, i, s); writeln(i:2, s); end; end.

Источник

Динамические структуры данных.

Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память выделяется по мере необходимости отдельными блоками, связанными друг с другом с помощью указателей. Такой способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы. Из динамических структур в программах чаще всего используются линейные списки, стеки, очереди и бинарные деревья. Они различаются спо-

Одесский колледж компьютерных технологий “СЕРВЕР” собами связи отдельных элементов и допустимыми операциями. Динамическая структура может занимать несмежные участки оперативной памяти. Динамические структуры широко применяют и для более эффективной работы с данными, размер которых известен, особенно для решения задач сортировки, поскольку упорядочивание динамических структур не требует перестановки элементов, а сводится к изменению указателей на эти элементы. Элемент любой динамической структуры данных представляет собой структуру (struct), содержащую по крайней мере два поля: для хранения данных и для указателя. Полей данных и указателей может быть несколько. Поля данных могут быть любого типа: основного, составного или типа указатель. Описание простейшего элемента (компоненты, узла) выглядит следующим образом: struct Node< Data d; Node *p; >;

Линейные списки

Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент содержал ссылку на следующий. Такой список называется однонаправленным (односвязным). Если добавить в каждый элемент вторую ссылку – и на предыдущий элемент, получится двунаправленный список (двусвязный), если последний элемент связать указателем с первым, получится кольцевой список. Каждый элемент списка содержит ключ, идентифицирующий этот элемент. Ключ обычно бывает либо целым числом, либо строкой и является частью поля данных. Над списками можно выполнять следующие операции: • начальное формирование списка (создание первого элемента); • добавление элемента в конец списка; • чтение элемента с заданным ключом; • вставка элемента в заданное место списка (до или после элемента с заданным ключом); • удаление элемента с заданным ключом; • упорядочивание списка по ключу.

Стеки

Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца,

Одесский колледж компьютерных технологий “СЕРВЕР” называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (last in – first out, последним пришёл – первым ушёл). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячи. Достать первый брошенный мяч можно только после того, как вынуты все остальные. Кстати, сегмент стека назван именно так потому, что память под локальные переменные выделяется по принципу LIFO. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах. Пример. Программа формирует стек из пяти целых чисел (1, 2, 3, 4, 5) и выводит его на экран. Функция помещения в стек называется push, а выборки – pop. Указатель для работы со стеком (top) всегда ссылается на его вершину. #include struct Node< int d; Node *p; >; Node *first(int d); void push(Node **top, int d); int pop(Node **top); //———————————————————— int main() < Node *top = first(1); for (int i=2; i//------------------------------------------------------------ //Начальное формирование стека Node * first(int d)< Node *pv = new Node; pv->d = d; pv->p = 0; return pv; > //———————————————————— //Занесение в стек void push(Node **top, int d)< Node *pv = new Node; pv->d = d;

Одесский колледж компьютерных технологий “СЕРВЕР” pv->p = *top; *top = pv; > //———————————————————— //Выборка из стека int pop(Node **top)< int temp = (*top)->d; Node *pv = *top; *top = (*top)->p; delete pv; return temp; > Результат работы программы: 5 4 3 2 1

Очереди

Очередь – это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in – first out, первым пришёл – первым ушёл). Очередь проще всего представить себе, постояв в ней час – другой. В программировании очереди применяются, например, в моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе. Пример. Программа формирует очередь из пяти целых чисел и выводит её на экран. Функция помещения в конец очереди add, а выборки – del. Указатель на начало очереди называется pbeg, указатель на конец – pend. #include struct Node< int d; Node *p; >; Node *first(int d); void add(Node **pend, int d); int del(Node **pbeg); //———————————————————— int main()< Node *pbeg = first(1); Node *pend = pbeg; for (int i=2; i

Источник

Указатели и динамические структуры данных: стеки, списки, очереди, деревья.

Указатель – тип данных, хранящих адрес в памяти других данных. В зависимости от типизации указатель может быть нетипизированным (содержать просто адрес в памяти) и типизированным (указывать только на элемент определенного типа).

Стек – хранилише данных однородного типа с дисциплиной “последним пришел-первым вышел” (LIFO).

Над стеком определены операции PUSH, POP (затолкнуть, извлечь).

При операции PUSH указатель стека SP увеличится на 1, при извлечении уменьшится на 1.

Природа стека делает необходимым соответствие операций PUSH и POP. Если его нет, то возможно 2 ситуации:

а) переполнение – SP вышел за пределы верхнего значения

б) антипереполнение –“- нижнего.

Очередь – структура данных с дисциплиной FIFO – “первым вошел, первым вышел”.

Здесь HP – указатель на последнее значение, tp – номер последнего выбранного элемента. Если HP=TP – очередь пуста.

ENQ x — добавляем в очередь

DEQ x — извлекаем из очереди

Особые ситуации — так же как и со стеком.

Для реализации динамических структур данных используют т.н. кучу (heap). Это объем памяти, в котором можно выделить участок для произвольного элемента данных. Для кучи есть 2 операции: выделения памяти ALLOCATE и освобождения FREE. Эти функции не делают никаких действий с собственно памятью. При выделении программист получает адрес, а при освобождении доступный объем кучи становится больше. Одного адреса для этих операций недостаточно, требуется еще и размер элемента данных.

Списки – сложные динамические структуры данных, представляющие собой структуры, содержащие указатели на другие подобные структуры. Если такой указатель в структуре 1 – односвязный список, если 2 – двусвязный, если много – многосвязный. Стек и очередь можно легко представить в виде одно- и двусвязного списка. Списки характеризуются тем, что для них легко реализуется любая дисциплина ввода-вывода за счет простого добавления и удаления элемента.

Для добавления элемента достаточно выделить под него память и присвоить адрес памяти нового элемента соответствующему предыдущему элементу. Для удаления элемента память из-под него освобождается, а указателям на него присваивается некоторое зарезервированное значение NULL – “указатель на ничто”.

Источник