Краткая теория. «Реализация динамических структур «Список», «Кольцевой список»,

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

«Реализация динамических структур «Список», «Кольцевой список»,

Двусвязный список», «Двусвязный кольцевой список»».

Цель работы: исследовать и изучить динамические структуры «Список», «Кольцевой список»,

Задача работы: овладеть навыками составления структур АТД «дерево» и написания программ по исследованию АТД «дерево» на любом языке программирования.

Порядок работы:

1. изучить описание лабораторной работы;

2. по заданию, данному преподавателем, разработать структуру АТД «дерево»;

3. написать программу на языке ПАСКАЛЬ;

4. отладить программу;

5. решить задачу;

6. оформить отчет.

Краткая теория

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

В поле указателя последнего элемента списка находится специальный признак null, свидетельствующий о конце списка.

Рис. - Структура односвязного списка

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

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

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

Операции, производимые над односвязными списками:

· добавление элемента в начало списка;

· удаление элемента из начала списка;

· добавление элемента в произвольное место списка, отличное от начала

· удаление элемента из произвольного места списка, отличного от начала

· проверка, списка на пустоту;

· перестановка элементов списка;

· слияние двух списков;

· очистка списка;

· печать списка.

· Обработка односвязного списка не всегда удобна, так как отсутствует возможность продвижения в противоположную сторону.

· Такую возможность обеспечивает двухсвязный список, каждый элемент которого содержит два указателя: на следующий и предыдущий элементы списка. (рис. 15)

·

·

· рис. - Структура линейного двухсвязного списка

·

· Поле NEXT - указатель на следующий элемент, поле PREV - указатель на предыдущий элемент. В крайних элементах соответствующие указатели должны содержать nil

· Для удобства обработки списка добавляют еще один особый элемент - указатель конца списка.

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

· В двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются,

Рис. - Структура кольцевого двухсвязного списка

Операции над двусвязными списками:

· создание элемента списка;

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

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

· удаление из списка заданного элемента