Рабочее задание

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

Варианты

1. двунаправленный дек, преобразовать в стек;

2. циклический список, преобразовать в двунаправленный дек;

3. двунаправленный циклический список, преобразовать в стек;

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

5. циклический список с тремя связями, указывающими на предыдущий, последующий и через один элемент;

6. трехмерный список;

7. двумерный список;

8. двумерный список, строки представлены в виде стека;

9. двумерный список, строки представлены в виде дека;

10. двумерный список, строки представлены в виде двунаправленного дека;

11. двумерный список, строки представлены в виде очереди;

12. двумерный список, строки представлены в виде циклического списка;

13. двумерный список, строки представлены в виде двунаправленного циклического списка;

14. двумерный список, столбцы представлены в виде очереди;

15. двумерный список, столбцы представлены в виде стека;

16. двумерный список, столбцы представлены в виде дека;

17. двумерный список, столбцы представлены в виде двунаправленного дека;

18. двумерный список, столбцы представлены в виде очереди;

19. двумерный список, столбцы представлены в виде циклического списка;

20. двумерный список, столбцы представлены в виде двунаправленного циклического списка;

Лабораторная работа №4

Третья лабораторная работа посвящена методам обработки иерархических структур (деревьев)

Теоретический материал.

1. ОБЩИЕ ПОНЯТИЯ.

Линейные структуры отражают только последовательность элементов, однако, при отражении многих объектов реального мира помимо перечня элементов необходимо установить их иерархию. Поэтому для отображения таких объектов в БД необходимы иерархические структуры данных.

2.БИНАРНЫЕ ДЕРЕВЬЯ.

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

Таким образом, бинарное дерево - это дерево, в котором каждый элемент имеет не более 2 поддеревьев.

Существует 3 основных порядка обхода бинарного дерева:

1. Прямой.

- пройти корень;

- пройти левое поддерево;

- пройти правое поддерево.

2. Обратный

- пройти корень;

- пройти правое поддерево;

- пройти левое поддерево.

3. Концевой

- пройти левое поддерево;

- пройти правое поддерево;

- пройти корень.

ФОРМАТ ЭЛЕМЕНТА ДЕРЕВА

Inf –поле информации, L –адрес левого поддерева, К –адрес правого поддерева.

ПРОШИТЫЕ ДЕРЕВЬЯ.

Такие деревья позволяют избавляться от вышеперечисленных недостатков. В адресные поля концевых элементов вместо пустого адреса nill вписывается адрес вышестоящего элемента. Таким образом, мы получаем возможность двигаться не только вниз по дереву, но и вверх. Однако, новых связей, приведенных нами, нет в реальном объекте, который отражает данное дерево. Следовательно, мы должны отличать реальные связи, которые описывает объект, от мнимых связей, играющих служебную роль в БД. Поэтому формат элемента следует несколько изменить, добавив в него признаки мнимости связи.

ПРЕОБРАЗОВАНИЕ ПРОИЗВОЛЬНЫХ ИЕРАРХИЧЕСКИХ СТРУКТУР В БИНАРНЫЕ ДЕРЕВЬЯ.

Среди объектов, описываемых в БД, существуют такие, у которых каждый корень может иметь один и более поддеревьев. Надо уметь преобразовывать их в бинарные для удобства работы.

АЛГОРИТМ ПРЕОБРАЗОВАНИЯ

1. Удалить все вертикальные связи, кроме связей от корня к его первому поддереву;

2. Добавить горизонтальные связи между элементами - поддеревьями одного корня;

3. Если лес состоит из нескольких деревьев, связать их корни

горизонтальной связью.

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

ДЕРЕВО ПОИСКА.

Д ерево поиска - это бинарное дерево, в котором для каждого элемента все значения в левом поддереве меньше корня, а в правом больше корня.

Подобная структура наилучшим образом отвечает поиску методом половинного деления.

Пусть требуется найти элемент х. Сравним его значение с корнем дерева поиска. Если х больше корня дерева поиска, то х находится в правом поддереве корня (либо отсутствует). Далее х сравнивается с элементом корня поддерева и т.д.

ВКЛЮЧЕНИЕ ЭЛЕМЕНТА

Д ано дерево поиска, вставить элемент "5"

Н а первом этапе выполняется поиск места для нового элемента. Для этого необходимо пройти по соответствующей ветви дерева от корня до пустого адреса. На место этого пустого адреса вписывается адрес включаемого элемента.

УДАЛЕНИЕ ЭЛЕМЕНТА

При удаление элемента возможны 3 ситуации:

1. Удаление концевого элемента. Для этого необходимо:

- найти этот элемент;

- найти его корень и заменить ссылку на nill;

- вернуть памяти освободившуюся ячейку.

2. Удаление элемента, имеющего одно поддерево

- переправить ссылку его корня на поддерево удаляемого элемента

3. Удаление элемента, имеющего два поддерева.

- удаляемый элемент следует заменить на самый правый элемент его левого поддерева или самый левый элемент правого поддерева.