Списки и деревья

Задание на курсовую работу Работа со списками.

Каждый вариант задания состоит из общей и индивидуальной частей. В состав общей части входит реализация следующих действий.

1. Создание пустого списка.

2. Подсчет количества элементов списка.

3. Вывод на экран содержимого списка в виде таблицы.

4. Вставка элемента в начало или в конец списка (оба варианта).

5. Исключение элемента из начала или конца списка (оба варианта).

6. Сохранение списка в файле.

7. Восстановление списка из файла.

8. Уничтожение списка с освобождением памяти.

Примечания.

1. Каждый элемент списка имеет ключевой признак и информационное поле. Ключ — целое без знака с произвольным значением. Содержание информационного поля произвольно (может быть числовым, символьным или строковым).

2. Управление выбором функций организовать с помощью иерархических меню.

3. Вывод списка на экран должен иметь вид:

Список

N п/п Ключ Информация

Всего в списке ____ элементов.

4. Вид организации списка: двунаправленный циклический.

Индивидуальные задания:

1. Включить новый элемент вместо i-го по номеру элемента.

2. Поменять местами элемент с заданным ключом и следующий.

3. Поменять местами два элемента с заданными ключами.

Работа с деревьями.

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

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

Стандартные действия.

1. Создание бинарного дерева (дерева поиска):

а) из элементов списка;

б) из файла;

в) в диалоге с пользователем.

Способ формирования дерева: с учетом значений ключа.

2. Обход бинарного дерева каждым из трех способов с выдачей на экран содержимого информационных полей.

3. Включение элемента в бинарное дерево (согласно алгоритму формирования дерева).

4. Удаление заданного узла из дерева (без поддерева).

5. Удаление дерева с освобождением памяти

6. Вывод дерева на экран с показом структуры.

Список дополнительных действий с бинарным деревом.

1. Определить количество листьев на каждом уровне дерева.

2. Удалить все листья дерева.

3. Вывести содержимое всех узлов, лежащих на пути между двумя узлами, заданными своими ключевыми признаками.

4. Определить количество узлов (не листьев) бинарного дерева, находящихся на одном уровне с узлом, заданным значением ключевого признака.

Примечания.

1. Каждый элемент дерева имеет ключевой признак (числовое поле — целое без знака) с произвольным значением. Содержание информационного поля произвольно (символьное, числовое или строковое поле).

2. Управление выбором функций организовать с помощью иерархических меню.

3. Дерево выводить в виде таблицы с указанием вида обхода.