Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 6 )

Формирование двусвязного списка можно реализовать следующим образом:

//выделяется память для нового элемента списка
rex=new NDD;
//заполняем поле данных нового элемента
printf("Введите данные  ");
scanf("%f",&rex->val);
//если это будет первый элемент в списке,
//то на него должен указывать указатель beg
if (beg==NULL)  beg=rex;
// иначе, присоединяем элемент к существующему списку
  else end->next=rex;
rex->prev=end;
//т. к. элемент добавляется в конец списка, то на этот элемент
// должен указывать указатель end
end=rex;
//поле указателя элемента end должно содержать значение NULL
end->next=NULL;

Удаление элемента из двусвязного списка можно представить так:

float ad;
printf("

Введите значение элемента, который надо удалить: ");
scanf("%f",&ad);  i=1;
rex=beg;
while(rex!=NULL&&rex->val!=ad) rex=rex->next;
  if (rex->next==NULL) printf("Такого элемента нет

");
  else {rex->prev->next=rex->next;
  rex->next->prev=rex->prev;
  delete rex;
  }

Оператор

rex->prev->next=rex->next;

можно представить как

(rex->prev)->next=rex->next;

такой оператор означает, что в поле next элемента, стоящего перед удаляемым элементом, заносится адрес элемента, который находится после удаляемого элемента.

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

При этом нет необходимости в указателе конца списка end.

Лекция №6

Тема: Стеки. Очереди.

Цель: Ввести понятия стека и очереди, знать способы их реализации.

Стеки

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

Стеки иногда называют магазинами. Для обозначения стеков часто используется аббревиатура LIFO (last-in/first-out – «последний вошел – первый вышел»).

Стек используют для хранения элементов, доступных в вершине списка (top).

Структура стека аналогична стопке тарелок на полке буфета или стопке книг. В этих примерах можно взять только верхний предмет, а добавить новый предмет можно, только положив его сверху.

В структуре стека важное место занимают операции добавления и удаления элементов. Операция Push добавляет элемент в вершину стека. Операция Pop удаляет элемент из стека:

Стек может быть реализован двумя способами:

- на основе массивов;

- при помощи указателей.

При реализации стека на основе одномерного массива размер стека ограничен максимальным количеством элементов массива. При этом может возникнуть проблема переполнения.

При реализации стека с помощью указателей размер стека ограничен доступным объемом свободной памяти.

Графически структуру стека можно представить следующим образом:

Операции стека

1. Добавление элемента в стек:

2. Удаление элемента из стека (с выдачей значения удаляемого элемента):

3. Выдача значения верхнего элемента:

4. Очистка стека:

5. Печать количества элементов стека.

Стек применяется

при работе с памятью, например, работа функций printf и scanf основана на использовании стека; для того, чтобы определить, является ли предложение палиндромом (палиндром – это строка, которая читается одинаково в прямом и в обратном направлениях); для вывода данных с различными основаниями; при разработке электронных калькуляторов.

Очереди

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

При работе с очередью используются специальные указатели на начальную и конечную позиции. Эти указатели используются для вставки и удаления элементов из очереди. Начало очереди определяется первым элементом в очереди (front). Конец очереди – это место после его последнего элемента (rear).

Очередь может быть реализована двумя способами:

- на основе массивов;

- при помощи указателей.

Очередь, как и стек, не ограничивает количество элементов. Однако если для реализации очереди используется массив, может возникнуть условие полной очереди.

Реализовать очередь на основе массивов можно двумя способами – линейной очередью и кольцевой очередью.

· Простейшая линейная очередь на основе одномерного массива. При исключении элемента из очереди все оставшиеся элементы данных должны смещаться вперед на одну позицию;

Данная модель не является эффективной. Например, очередь содержит 1000 элементов. Если один элемент удаляется из начала, тогда 999 элементов должны сместиться влево.

· Кольцевая очередь является более эффективной. Элементы кольцевой очереди организованы логически в окружность. Переменная front всегда является местоположением первого элемента в очереди, и она продвигается вправо по кругу по мере выполнения удалений.

При реализации очереди с помощью указателей размер очереди ограничен доступным объемом свободной памяти.

Графически очередь можно представить следующим образом:

Операции над объектом «очередь»

1. Добавление элемента в очередь

2. Удаление элемента из очереди (с выдачей значения исключаемого элемента):

3. Выдача значения первого элемента:

4. Очистка очереди:

5. Выдача количества элементов очереди.

Очередь применяется:

- в компьютерном моделировании (например, моделирование очереди клиентов в банке);

- в многопользовательских операционных системах;

- для сортировки данных.

Очереди приоритетов

Очередь приоритетов – это модифицированная версия очереди, в которой из списка удаляется элемент с высшим приоритетом.

Элементы в очереди приоритетов рассматриваются как пара ключ-значение, в которой ключ определяет уровень приоритета. Приоритет оценивается по некоторому внешнему критерию.

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

Приоритет 0 определяется как высший (обычный приоритет имеет значение 20).

Рассмотрим следующий список элементов и их приоритетов:

Элементы из очереди будут удаляться в порядке 2, 1, 5, 4, 3.

Очередь приоритетов можно представить в виде нескольких очередей, где каждая очередь используется для своего приоритета:

Приоритет 1
R1	R2	...	Rn
Приоритет 2
O1	O2	...	On
Приоритет 3
B1	B2	...	Bn

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

Очереди приоритетов используются в операционной системе, которая записывает процессы в список и затем выполняет их в порядке приоритетов.

Лекция №7

Тема: Деревья . Основные определения. Двоичные (бинарные) деревья

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

Основные определения

Дерево – это совокупность элементов и отношений, которые образуют иерархическую структуру. Элементы дерева называются узлами.

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

Корень дерева - это такая вершина, которая не имеет предков (А). Каждое дерево может иметь только один корень.

Самые нижние узлы дерева называют листьями (E, G, H, I, J), они не имеют потомков.

Если элемент дерева не является листом, то его называют внутренним узлом дерева, или вершиной.

Пустое дерево – это дерево, не имеющее вершин.

Дочерняя (сыновья) вершина – это вершина, расположенная на дереве ниже своей родительской вершины и непосредственно соединенная с ней.

Например, если вершина I является дочерней по отношению к вершине F, то вершина F называется отцовской (материнской, родительской) по отношению к вершине I.

Дочерние узлы и их дочерние узлы называются потомками (узлы E, F, I, J – это потомки узла В).

Предки – это родители и прародители узла.

Каждый узел дерева является корнем поддерева, которое состоит из данного узла и всех его потомков.

Например, узел F – это корень поддерева, содержащего узлы F, I, J. Узел G – это корень поддерева без потомков. Узел А – это корень поддерева, которое само оказывается деревом.

Прохождение от любого узла к его потомкам осуществляется вдоль пути. Например, путь от корня А к узлу F проходит через вершины A, B, F. Существует единственный путь из любого узла к его потомкам.

Уровень узла – это длина пути от корня к этому узлу. Например, уровень корня равен 0. Каждый сын корня является узлом 1-го уровня, следующее поколение – узлами 2-го уровня и т. д. Например, узел F является узлом 2-го уровня с длиной пути 2.

Глубина дерева – это максимальный уровень любого его узла. Или глубина дерева – это длина самого длинного пути от корня до узла.

Способы изображения древовидной структуры

Существует четыре способа изображения деревьев. Это граф, вложенные скобки, вложенные множества, ломаная последовательность.

1. Граф

2. Вложенные скобки

(A(B(E, F(I, J)),C(G),D(H)))

3. Вложенные множества

4. Ломаная последовательность

A	B	E F	I J
C	G
D	H

Чаще всего для изображения деревьев используется граф.

Двоичные (бинарные) деревья

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

в двоичном дереве каждая вершина может иметь не более двух дочерних вершин; для любой вершины его дочерние вершины называются правой (дочерней) вершиной и левой (дочерней) вершиной (эти названия относятся к графическому представлению дерева).

Любое дерево можно представить соответствующим ему двоичным деревом.