Двусвязный циклический список
ФГБОУ ВПО Кубанский государственный технологический университет
(ФГБОУ ВПО «КубГТУ»)
Кафедра информационных систем и программирования
Институт компьютерных систем и информационной безопасности
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту
по дисциплине Алгоритмы и структуры данных
(наименование дисциплины)
на тему Двусвязные циклические списки (тема курсовой работы)
Выполнила студентка группы 14-3КБс-122
Корчагина Татьяна Владимировна
(Ф.И.О.)
Допущен к защите
Руководитель (нормоконтроллер) проекта (работы) А.Г. Волик
(подпись, дата, расшифровка подписи)
Защищен ________________________ Оценка _
(дата)
Члены комиссии А.Г. Волик
А.Г. Мурлин
М.В. Янаева
(подпись, дата, расшифровка подписи)
2015 г.
ФГБОУ ВПО Кубанский Государственный Технологический Университет
(ФГБОУ ВПО «КубГТУ»)
Кафедра информационных систем и программирования
Институт компьютерных систем и информационной безопасности
| УТВЕРЖДАЮ Зав. кафедрой Л.А. Видовский _ «___» __________________ 2015 г. |
ЗАДАНИЕ
на курсовое проектирование
Студенту(ке): Корчагиной Татьяне Владимировне группы 14-ЗКБс-ПИ1
института МИППС
направления 090303 Прикладная информатика
Тема проекта: Двусвязные циклические списки
Содержание задания: реализовать двусвязный циклический список
Объем работы:
а) пояснительная записка к проекту с.
б) программа
Рекомендуемая литература:
Срок выполнения проекта: с " 02 " февраля по " 07 " июня 2015 г.
Срок защиты: " 14 " июня 2015 г.
Дата выдачи задания: " 02 " февраля 2015 г.
Дата сдачи проекта (работы) на кафедру: " 08 " июня 2015 г.
Руководитель проекта (работы) ст. преп. А.Г. Волик
(подпись, Ф.И.О., звание, степень)
Задание принял студент ___________
(подпись)
РЕФЕРАТ
Пояснительная записка курсовой работы содержит 24 с., 9 рис., 4 источника, 1 приложение.
СПИСКИ, ДВУСВЯЗНЫЕ ЦИКЛИЧЕСКИЕ СПИСКИ,СТРУКТУРА ДАННЫХ, УЗЛЫ ЦИКЛИЧЕСКОГО СПИСКА.
В данной курсовой работе рассмотрены двусвязные циклические списки, основные действия, производимые над узлами двусвязного циклического списка, а также стандартные функции для двусвязного списка.
Объектом исследования являются двусвязные циклические списки.
Цель работы состоит в изучении работы двусвязных циклических списков и реализация их програмно.
К полученным результатам относится класс, реализующий двусвязный циклический список и програма, демонстрирующая его работу.
Содержание
Введение.......................................................................................................... 5
1 Постановка задачи....................................................................................... 6
2 Описание методов решения......................................................................... 6
2.1 Двусвязный циклический список........................................................... 6
2.2 Основные действия, производимые над узлами двусвязного циклического списка (ДЦС)............................................................................................................ 7
2.3 Стандартные функции для двусвязного списка.................................. 13
3 Описание реализации программы............................................................. 15
4 Тестирование и результаты работы.......................................................... 18
Заключение.................................................................................................... 20
Список использованных источников............................................................ 21
Приложение А. Исходный код программы................................................. 22
Введение
Двусвязный циклический список – список, при котором первый элемент является следующим для последнего элемента списка.
Исследование двусвязного циклического списка является актуальным, потому что имеет ряд преимуществ и во многом упрощает работу программы. Такими преимуществами являются:
· добавление нового узла в определённую позицию,
· удаление i-того элемента из последовательности,
· просмотр списка в обоих направлениях.
В результате проведения данного исследования, будут рассмотрены двусвязные циклические списки, основные действия, производимые над узлами двусвязного циклического списка, стандартные функции для двусвязного списка, а также построена программа, использующая пинцип двусвязных циклических списков.
Постановка задачи
Выполнить программную реализацию двусвязного циклического списка. Необходимо организовать заданную структуру данных. Определить структуру элемента и написать подпрограммы добавления, удаления и чтения элемента. Написать тестовую программу.
Описание методов решения
Двусвязный циклический список
Связный список (англ. List) — структура данных, состоящая из элементов, содержащих помимо собственных данных ссылки на следующий и/или предыдущий элемент списка. С помощью списков можно реализовать такие структуры данных как стек и очередь.
Каждый узел двунаправленного (двусвязного) циклического списка (ДЦС) содержит два поля указателей - на следующий и на предыдущий узлы. Указатель на предыдущий узел корня списка содержит адрес последнего узла. Указатель на следующий узел последнего узла содержит адрес корня списка.
Рисунок1 – Узлы ДЦС и поля указателей
Узел ДЦС можно представить в виде структуры, аналогичной двусвязному линейному списку:
struct list {
int field; // поле данных
struct list *next; // указатель на следующий элемент
struct list *prev; // указатель на предыдущий элемент
};