Лабораторная работа 10 динамические структуры данных

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

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

1. Создать двунаправленный список. Вставлять новые узлы в начало списка. Распечатать список.

2. Создать двунаправленный список. Вставлять новые узлы в середину списка. Распечатать список.

3. Создать двунаправленный список. Вставлять новые узлы в конец списка. Распечатать список.

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

5*. На базе двунаправленного списка организовать в программе работу стека. (добавлять и удалять узлы с конца списка). Распеча-тывать список.

6. Создать двунаправленный список. Удалять узлы из начала списка. Распечатать список.

7. Создать двунаправленный список. Удалять узлы из середины списка. Распечатать список.

8. Создать двунаправленный список. Удалять узлы с конца списка. Распечатать список.

9. Создать циклический список и организовать вставку в него узлов. Распечатать список.

10**. Создать двунаправленный список. Добавлять в него узлы в отсортированном порядке.

11*. Организовать в программе работу очереди (добавление узлов в конец списка, удаление с начала списка).

12*. Создать двунаправленный список (название страны, название города, население). Подсчитать население городов заданной страны.

13*. Отыскать заданный узел в двунаправленном списке и модифицировать его содержимое.

Примечание: Задания повышенной трудности отмечены символом *.

2. Содержание отчета

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

3. Вопросы по лабораторной работе

1. Что такое узел списка?

2. Что такое однонаправленный список?

3. Что такое двунаправленный список?

4. Как создается каждый узел списка?

5. Как вставить узел в список(в начало, в середину, в конец)?

6. Как удалить узел из списка(из начала, из середины, из конеца)?

7. Что такое стек? Принцип работы стека.

8. Что такое очередь? Принцип работы очереди.

9. Что такое циклический список? Принцип организации цикличес-кого списка.

10. Бинарные деревья. Понятие корня дерева. Поддерева. Вершины дерева.

11. Принцип организации бинарного дерева.

12. Обход бинарного дерева (прямой, обратный, концевой).

Приложение

1. Однонаправленные связные списки

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

struct TelNum {

TelNum * next; //указатель на следующий элемент

long telephon; // данные

char name[30]; // данные

};

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

Указатель на

заголовок

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