 |
Программная реализация дерева поиска
|
|
|
|
Лабораторная работа №1
МЕТОДЫ СОРТИРОВКИ И ПОИСКА ДАННЫХ
Первая лабораторная работа посвящена методам сортировки данных в списке. Цель работы: изучение основных методов сортировки списка и поиск методом половинного деления.
Теоретический материал.
МЕТОД «ПУЗЫРЬКА»
Сортировка производится попарным сравнением элементов. Если элементы стоят в нужном порядке, то сравнивают следующую пару, иначе меняют местами. Когда пройдет весь список, начинаем 2-ой проход по этому же списку и так до тех пор, пока за весь проход не будет ни одной перестановки.
For i:=1 to n-1 do
Begin
For j:=1 to n-1 do
If M[j]>M[j+1] then
Begin
D:=M[j];
M[j]:=M[j+1];
M[j+1]:=D;
End;
End;
Что бы ускорить процесс сортировки в программу надо ввести переменную-флаг, которая покажет, была ли в цикле хотя бы одна перестановка, если перестановок не было, то массив отсортирован.
МЕТОД «ЭКСТРЕМУМОВ».
При сортировке по убыванию мы находим максимальный элемент, ставим его в новый отсортированный массив. Из оставленных элементов снова выбираем максимальный и т.д. пока из исходного массива не будут выбраны все элементы.
For j:=1 to n-1 do
Begin
D:=M[j];
For i:=j+1 to n do
If (D<M[i]) then
Begin
D:=M[i];
M[i]:=M[j];
M[j]:=D;
End;
End;
Сортировка по возрастанию аналогична.
МЕТОД ПРОСТОЙ ВСТАВКИ.
В базах данных часто встречается ситуация когда информация уже отсортирована и в нее вносится новая запись, в этом случае быстрее всего сработает метод простой вставки. Он не требует полной сортировки, а позволяет раздвинуть уже отсортированный массив и вставить новый элемент на нужное место.
1) Пусть дан пустой массив. Вставим в него число.
2) Вставим второе число, если оно меньше первого, то первое сдвинем и т.д.
|
|
|
3) Вставляем все необходимые числа, при необходимости сдвигая и раздвигая массив.
ПОИСК МЕТОДОМ ПОЛОВИННОГО ДЕЛЕНИЯ.
Допустим, существует линейный список, отсортированный по возрастанию. Для того чтобы найти нужное нам число, сравним его с серединой диапазона. Если искомое число больше стоящего в середине, продолжаем поиск справа от середины, если меньше - слева. В любом случае, отбрасываем половину диапазона, в оставшемся опять ищем середину и так, постепенно сужая поиск, мы находим искомое число, или убеждаемся, что его нет.
Рабочее задание
Разработать и отладить программу реализующую:
1) Ввод исходного списка (размерность массива задается пользователем).
2) Сортировку списка методом «пузырька», ввести переменную-флаг, подсчитать количество перестановок.
3) Сортировку массива с помощью метода «экстремумов», подсчитать количество сравнений.
4) Сортировку массива методом «простой вставки», применяя поиск методом половинного деления.
5) Меню для выбора варианта сортировки
Варианты
Если номер студента в списке группы четный, то массив сортируется по возрастанию, нечетный по убыванию.
Лабораторная работа №2
ЛИНЕЙНЫЕ СПИСКИ.
Вторая лабораторная работа посвящена методам обработки данных в распространенных видах линейных списков: стек, очередь, дек. Цель работы: изучение распространенных частных случаев линейных списков и получение навыков использования динамического определения памяти и единого адресного пространства при последовательном распределении памяти.
Теоретический материал.
Линейный список - это структура данных, в которой структурные свойства любого элемента сводятся к его положению между двумя соседними элементами.
Так, на рисунке, элемент «2» расположен между элементами «3» и «4».
|
|
|
ОПЕРАЦИИ НАД ЛИНЕЙНЫМИ СПИСКАМИ (ОБЩИЙ СЛУЧАЙ).
1. Включение элемента в список
2. Удаление элемента из списка
3. Поиск элемента в списке
4. Сортировка
5. Соединение двух и более списков в один
6. Разделение одного линейного списка на два и более линейных списков.
ПОСЛЕДОВАТЕЛЬНОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ.
При последовательном распределении в памяти список размещается в смежных ячейках памяти.
Достоинства последовательного размещения:
1. Возможность непосредственной адресации нужной ячейки, так как номер ячейки легко вычисляется.
2. Экономия памяти: элемент содержит только информационное поле.
Недостатки последовательного размещения:
1. Сложность вставки и удаления элемента.
2. Необходимость заранее объявлять размер списка, это приводит к не экономному использованию памяти.
3. Фрагментация памяти.
1) 2)
СВЯЗАННОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ.
При связанном распределении памяти каждый элемент списка содержит адрес следующего или предыдущего элемента.
Формат элемента inf- поле информации
S - поле ссылки на следующий элемент.
Достоинства связанного размещения:
1. Произвольное размещение элементов в памяти (отсутствует проблема фрагментации).
2. Легко произвести вставку/удаление из списка.
3. нет необходимости заранее резервировать память, когда вставляется новый элемент, под него выделяется любая свободная ячейка, когда элемент удаляется, ячейка освобождается.
Недостатки связанного размещения:
1. Больше занимаемый объем памяти в связи с необходимостью хранить адреса.
2. Невозможность прямого доступа к любому элементу.
Виды линейных списков.
СТЕК.
Стек-это линейный список, доступ к которому для включения/удаления элементов производится с одного конца списка.
ОЧЕРЕДЬ.
Очередь-это линейный список, в котором включение элемента происходит с одного конца (хвост очереди), а удаление из другого (голова очереди).
При удалении элемента из очереди (из головы) и включении элемента в очередь (в хвост) возникает эффект "погони головы за хвостом". При этом пространство освобожденной "головой" очереди остается неиспользованным. Чтобы избежать этого необходимо периодически сдвигать очередь в сторону начала.
|
|
|
|
|
неиспользуемое пространство
Другой способ избавиться от неиспользованного пространства использование связанного распределения очереди.
ДЕК.
Дек - это линейный список, у которого включение/удаление элементов производится с любого конца списка. Аналогом дека является колода карт.
Примеры программ.
1) Работа со стеком при последовательном распределении памяти.
Пусть требуется вставить в стек элемент x, заведем для стека одномерный массив.
St: array [1..10] of integer;
V: integer; // {вершина стека}
V:=1;
St[V]:=x;
V:=V+1;
St[V]:=x1;
…
Считаем значение
из стека в переменную Y
Y:=St[V];
V:=V-1;
…
2) Работа со стеком при связанном распределении памяти.
Пусть требуется вставить в стек элементы х1, х2, хЗ. Затем их удалить.
Формат элемента
Type Rec=^St;
St:=record
inf:integer;
S:Rec;
end:
Var
Stack, v:Rec;
x1:integer:
Begin:
1) //вставим в стек х1
new(Stack);
Stack.^inf:=x1;
Stack.^S:=nil;
v:=Stack;
2) //чтобы внести следующий элемент повторим этот же цикл
new(Stack);
Stack.^inf:=x2;
Stack.^S:=v;
v:=Stack;
//аналогично вставляем х3;
…
//удалим х3
Stack:=Stack.^S;
dispose(v);
v:=Stack;
//теперь можно удалять х2.
3) Пример расположения линейных списков в едином адресном пространстве при последовательном распределении памяти.
Рабочее задание
Задание 1
Разработать и отладить программу, выполняющую обработку нескольких линейных списков в едином адресном пространстве при последовательном распределении памяти. Предусмотреть возможность вставки, удаления и просмотра элементов, используя меню выбора. Виды линейных списков и дополнительные операции над ними различаются по вариантам.
Задание 2
Разработать и отладить программу, выполняющую обработку нескольких линейных списков при связанном распределении памяти. Предусмотреть возможность вставки, удаления и просмотра элементов, используя меню выбора. Виды линейных списков и дополнительные операции над ними различаются по вариантам.
|
|
|
Варианты
| № | Списки | Дополнительные операции |
| три стека | Объединить в один стек | |
| два стека и очередь | - | |
| две очереди и стек | - | |
| стек, очередь, дек | - | |
| два стека и дек | - | |
| два дека и стек | - | |
| два стека | Преобразовать в очередь | |
| стек и очередь | Преобразовать в дек | |
| стек и дек | Преобразовать в очередь | |
| три очереди | Объединить в одну очередь | |
| две очереди и дек | - | |
| два дека и очередь | - | |
| две очереди | Преобразовать в стек | |
| очередь и дек | Преобразовать в стек | |
| три дека | Объединить в один дек | |
| два дека | Преобразовать в стек | |
| две очереди | Преобразовать в дек | |
| очередь и дек | Преобразовать в стек | |
| стек и дек | Преобразовать в дек | |
| два стека | Преобразовать в дек |
Лабораторная работа №3
Третья лабораторная работа посвящена методам обработки циклических, многомерных и двунаправленных списков
Теоретический материал.
ЦИКЛИЧЕСКИЕ СПИСКИ.
Циклический список - это линейный список, в котором последний элемент указывает на первый.
 |
Над циклическими списками выполняются практически те же операции, что и над линейными списками вообще (см п.2.1). Однако есть ряд операций специфичных для циклического списка: ввод/удаление элемента слева/справа от указателя;
сдвиг указателя на 1 элемент.
УДАЛЕНИЕ ЭЛЕМЕНТА СЛЕВА ОТ УКАЗАТЕЛЯ.
 |
Удалим элемент хЗ. Необходимо перенаправить ссылку с элемента х2 на х1
 |
p^.s:=b^.s;
dispose (b);
b:=p^ s;
Часто приходится иметь дело с информацией, имеющей начало и конец. В тоже время в циклических списках явного начала и конца нет. Существует два подхода к решению этой проблемы. Можно ввести особый элемент - голову списка - элемент, по формату такой же, как и остальные, однако его информационное поле содержит лишь служебную информацию о том, что это голова списка.
Другой вариант - использование дополнительных битов-признаков.
|
|
|
 |
Введем в каждый элемент дополнительное поле h, которое указывает, является ли этот элемент началом списка. Для этого достаточно одного бита.
ДВУНАПРАВЛЕННЫЕ СПИСКИ.
В двунаправленном списке используется два поля ссылки, таким образом каждый элемент хранит адрес последующего и предыдущего элемента
Формат элемента
Изобразим двусвязный дек:
 |
Двусвязным можно выполнить любой линейный список, но именно для дека он наиболее выгоден. Есть сложности удаления из конца односвязного дека. Использование двусвязного дека позволяет удалять элементы так же как и из начала без прохода по всем элементам дека.
|
|
|
Двунаправленным может быть и циклический список.
 |
Все, что сказано выше о циклических списках справедливо и для двунаправленных циклических списках. Отличие в том, что над двунаправленным циклическим списком возможны такие операции как сдвиг указателя в обе стороны и т.д., а включение/удаление элемента одинаково легко производится и справа и слева от указателя.
МНОГОМЕРНЫЕ СПИСКИ.
Рассмотрим пример организации двумерного массива при связном и последовательном распределении памяти.
Последовательное распределение памяти:
| а11 | а12 | А13 | а21 | … | а33 |
Связное распределение памяти:
Формат элемента
| Inf | astr | ast |
Inf- поле информации;
Astr - адрес следующего элемента в данной строке;
Ast - адрес следующего элемента в данном столбце.
 |
Рабочее задание
Разработать и отладить программу реализующую обработку списков при связанном распределении. Организовать возможность вставки, удаления и поиска элементов, используя меню выбора. Вид списка и дополнительное задание различаются по вариантам.
Варианты
1. двунаправленный дек, преобразовать в стек;
2. циклический список, преобразовать в двунаправленный дек;
3. двунаправленный циклический список, преобразовать в стек;
4. дек с тремя связями, указывающими на предыдущий, последующий и через один элемент;
5. циклический список с тремя связями, указывающими на предыдущий, последующий и через один элемент;
6. трехмерный список;
7. двумерный список;
8. двумерный список, строки представлены в виде стека;
9. двумерный список, строки представлены в виде дека;
10. двумерный список, строки представлены в виде двунаправленного дека;
11. двумерный список, строки представлены в виде очереди;
12. двумерный список, строки представлены в виде циклического списка;
13. двумерный список, строки представлены в виде двунаправленного циклического списка;
14. двумерный список, столбцы представлены в виде очереди;
15. двумерный список, столбцы представлены в виде стека;
16. двумерный список, столбцы представлены в виде дека;
17. двумерный список, столбцы представлены в виде двунаправленного дека;
18. двумерный список, столбцы представлены в виде очереди;
19. двумерный список, столбцы представлены в виде циклического списка;
20. двумерный список, столбцы представлены в виде двунаправленного циклического списка;
Лабораторная работа №4
Третья лабораторная работа посвящена методам обработки иерархических структур (деревьев)
Теоретический материал.
ОБЩИЕ ПОНЯТИЯ.
Линейные структуры отражают только последовательность элементов, однако, при отражении многих объектов реального мира помимо перечня элементов необходимо установить их иерархию. Поэтому для отображения таких объектов в БД необходимы иерархические структуры данных.
БИНАРНЫЕ ДЕРЕВЬЯ.
Бинарное дерево - это множество элементов, каждый из которых состоит из корня и не более чем двух, непересекающихся множеств.
Таким образом, бинарное дерево - это дерево, в котором каждый элемент имеет не более 2 поддеревьев.
Существует 3 основных порядка обхода бинарного дерева:
1. Прямой.
- пройти корень;
- пройти левое поддерево;
- пройти правое поддерево.
2. Обратный
- пройти корень;
- пройти правое поддерево;
- пройти левое поддерево.
3. Концевой
- пройти левое поддерево;
- пройти правое поддерево;
- пройти корень.
ФОРМАТ ЭЛЕМЕНТА ДЕРЕВА
 |
Inf –поле информации, L –адрес левого поддерева, К –адрес правого поддерева.
ПРОШИТЫЕ ДЕРЕВЬЯ.
Такие деревья позволяют избавляться от вышеперечисленных недостатков. В адресные поля концевых элементов вместо пустого адреса nill вписывается адрес вышестоящего элемента. Таким образом, мы получаем возможность двигаться не только вниз по дереву, но и вверх. Однако, новых связей, приведенных нами, нет в реальном объекте, который отражает данное дерево. Следовательно, мы должны отличать реальные связи, которые описывает объект, от мнимых связей, играющих служебную роль в БД. Поэтому формат элемента следует несколько изменить, добавив в него признаки мнимости связи.
ПРЕОБРАЗОВАНИЕ ПРОИЗВОЛЬНЫХ ИЕРАРХИЧЕСКИХ СТРУКТУР В БИНАРНЫЕ ДЕРЕВЬЯ.
Среди объектов, описываемых в БД, существуют такие, у которых каждый корень может иметь один и более поддеревьев. Надо уметь преобразовывать их в бинарные для удобства работы.
 |  | ||
АЛГОРИТМ ПРЕОБРАЗОВАНИЯ
1. Удалить все вертикальные связи, кроме связей от корня к его первому поддереву;
2. Добавить горизонтальные связи между элементами - поддеревьями одного корня;
3. Если лес состоит из нескольких деревьев, связать их корни
горизонтальной связью.
В результате получаем бинарное дерево, операции над которым эквивалентны операциям над исходным лесом.
 |
ДЕРЕВО ПОИСКА.
Дерево поиска - это бинарное дерево, в котором для каждого элемента все значения в левом поддереве меньше корня, а в правом больше корня.
Подобная структура наилучшим образом отвечает поиску методом половинного деления.
Пусть требуется найти элемент х. Сравним его значение с корнем дерева поиска. Если х больше корня дерева поиска, то х находится в правом поддереве корня (либо отсутствует). Далее х сравнивается с элементом корня поддерева и т.д.
ВКЛЮЧЕНИЕ ЭЛЕМЕНТА
Дано дерево поиска, вставить элемент "5"
На первом этапе выполняется поиск места для нового элемента. Для этого необходимо пройти по соответствующей ветви дерева от корня до пустого адреса. На место этого пустого адреса вписывается адрес включаемого элемента.
УДАЛЕНИЕ ЭЛЕМЕНТА
При удаление элемента возможны 3 ситуации:
1. Удаление концевого элемента. Для этого необходимо:
- найти этот элемент;
- найти его корень и заменить ссылку на nill;
- вернуть памяти освободившуюся ячейку.
2. Удаление элемента, имеющего одно поддерево
- переправить ссылку его корня на поддерево удаляемого элемента
3. Удаление элемента, имеющего два поддерева.
- удаляемый элемент следует заменить на самый правый элемент его левого поддерева или самый левый элемент правого поддерева.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ДЕРЕВА ПОИСКА
В разделе описания переменных зададим формат элемента дерева:
Type Tree=^T;
T=record;
Inf:integer;
L,R,:Tree;
End;
Для навигации по дереву используем рекурсивную процедуру:
Procedure find_tree(var P:Tree; x:integer);
Begin
If (P<>nil) then
Begin
If P^.inf=x then …{нашли элемент};
If (P^.inf>x) then find_tree(P^.L,x);
If (P^.inf<x) then find_tree(P^.R,x);
End;
End;
СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ.
Дерево является сбалансированным, если для каждого элемента высота левого и правого поддеревьев различаются не более чем на «I».
ПРИМЕР: Дано дерево поиска. Рассчитаем критерий сбалансированности для каждого элемента.
Ни в одном элементе разница в высоте левого и правого поддеревьев не превышает «I». Следовательно, дерево сбалансировано.
Критерий сбалансированности - это разница в высоте левого и правого поддеревьев.
|
|
|
