Кафедра вычислительной техники и прикладной математики
КУРСОВАЯ РАБОТА
по дисциплине «Структуры и модели данных»
на тему: «Создание библиотеки контейнерных классов для реализации динамической структуры списки»
Исполнитель: Молдачев С.О. студент гр. АВБ-11-1
Проверил: Торчинский В.Е.
Работа допущена к защите «_____» _______2013г. ______________
Работа защищена «_____» _______2013г. с оценкой ______________
Магнитогорск, 2013
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Магнитогорский государственный технический университет
им. Г.И.Носова»
Кафедра вычислительной техники и прикладной математики
ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ
Тема: «Списки(односвязный, односвязный циклический, двусвязный, двусвязный циклический)»
Студенту Молдачеву Сергею Олеговичу
Исполнитель: Молдачев С.О. студент гр. АВБ-11-1
Руководитель: Торчинский В.Е.
__________________________________________________________________
__________________________________________________________________
Срок сдачи «_____» _______2013г. ______________
Руководитель ______________/______________
Магнитогорск, 2013
СОДЕРЖАНИЕ
Введение. 4
1 Теоритическая часть. 5
1.1 Односвязный и односвязный циклический списки. 5
1.2 Двусвязный и двусвязный циклический списки. 9
2.Практическая часть. 12
2.1 Листинг заголовочного файла “List.h”. 12
2.2 Листинг файла “List.cpp”. 23
Заключение. 26
Список использованных источников и литературы.. 27
Приложение. 28
Введение
C++ — компилируемый язык программирования общего назначения, сочетает свойства как высокоуровневых, так и низкоуровневых языков программирования. В сравнении с его предшественником — языком программирования C, — наибольшее внимание уделено поддержке объектно-ориентированного и обобщённого программирования. Название «язык программирования C++» происходит от языка программирования C, в котором унарный оператор ++ обозначает инкремент переменной.
Не существует единственного самого лучшего способа создания программ. Для решения задач разного рода и уровня сложности требуется применять разные технологии программирования. Довольно часто можно встретить задачи, в которых количество элементов постоянно меняется, но при этом последовательность следования объектов должна оставаться неизменной. Но более жестким условием является непредсказуемость количества «объектов». В подобных случаях можно заказать массив размером, превышающий максимально возможный. Однако это неэффективно и могут возникнуть проблемы в других частях программы. Лучшим решением является организация списков. Организация односвязного, двусвязного, односвязного циклического и двусвязного циклического списков и является целью моей работы.
Теоритическая часть
Односвязный и односвязный циклический списки
Связный список – структура, элементы которой имеют один и тот же формат и связаны друг с другом с помощью указателей, хранящихся в самих элементах.
В односвязном списке каждый элемент состоит из двух различных по назначению полей: содержательного поля (поле данных) и служебного поля (поля указателя), где хранится адрес следующего элемента списка (рис.1). Поле указателя последнего элемента списка содержит нулевой указатель, свидетельствующий о конце списка.
Рис.1. Односвязный список. Логическая структура.
Линейность односвязного списка вытекает из линейной логической упорядоченности его элементов: для каждого элемента, за исключением первого и последнего, имеются единственный предыдущий и единственный последующий элементы. Односвязные списки всегда линейны, поэтому особое внимание следует уделить проблеме перестройки списка при его повреждении.
Логическая структура линейного односвязного списка:
Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель текущего элемента списка.
Логическая структура элемента линейного односвязного списка:
Данные или указатель на данные, указатель на следующий элемент списка.
Продвижение в линейном односвязном списке возможно только в одном направлении. Результаты выполнения операций включения элемента в линейный односвязный список и исключения элемента из линейного односвязного списка – линейный односвязный список.
Рис.2. Выполнение операции включения элемента в линейный односвязный список.
Рис.3. Выполнение операции исключения элемента из линейного односвязного списка.
Для ускорения операции доступа к элементам односвязного списка поле указателя последнего элемента односвязного списка содержит указатель на начало списка. Такая разновидность линейного односвязного списка называется кольцевой односвязный список (рис.4), причем первым элементом такого списка может быть любой из его элементов.
Рис.4. Кольцевой односвязный список. Логическая структура.