Задание курсового проекта

I. Теоретический раздел

Достоинства динамических структур данных

 

Динамические структуры по определению характеризуются отсутствием физической смежности элементов структуры в памяти непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки. В этом разделе рассмотрены особенности динамических структур, определяемые их первым характерным свойством.

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

Элемент динамической структуры состоит из двух полей:

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

- поле связок, в котором содержатся один или несколько указателей, связывающий данный элемент с другими элементами структуры;

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

Достоинства связного представления данных:

- в возможности обеспечения значительной изменчивости структур;

- размер структуры ограничивается только доступным объемом машинной памяти;

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

Вместе с тем связное представление не лишено и недостатков, основные из которых:

- работа с указателями требует, как правило, более высокой квалификации от программиста;

- на поля связок расходуется дополнительная память;

- доступ к элементам связной структуры может быть менее эффективным по времени.

 

Применение динамических структур

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

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

Задание курсового проекта

Необходимо реализовать класс для работы с динамической структурой. Тип структуры – двусвязный список с полем data.

 

В классе следует реализовать методы которые будут обеспечивать выполнение следующих операций:

- добавление первого элемента в список;

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

- добавление элемента в середину списка;

- удаление последнего элемента;

- удаление n-го элемента списка;

- удаление головного элемента списка;

- удаление всего списка;

- замена n-го элемента списка;

- вывод списка на экран;

 

1.4 Описание структуры данных "двусвязный список"

Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Если ограничения на длину списка не допускаются, то список представляется в памяти в виде связной структуры. Линейные связные списки являются простейшими динамическими структурами данных.

Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем – 0 (или null).

На рис. 1 приведена структура односвязного списка. На нем белое поле - информационное поле (данные), NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой (HEAD) списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак NULL, свидетельствующий о конце списка.

+---------+ +---------+ +---------+ | данные | | данные | | данные | +---------+ +---------+ +---------+ |указатель|--->|указатель|--->| 0 | +---------+ +---------+ +---------+

 

 

Рис. 1.

 

Однако в данной работе используются двусвязные списки. Поэтому у каждого элемента списка есть два указателя: next - на следующий элемент списка, pred – на предыдущий элемент. Пример такого двусвязного списка изображен на рисунке 2.

Рис. 2.

+-------+ +-------+ +-------+ |данные | .->|данные | .->|данные | +---+---+ | +---+---+ | +---+---+ | 0 | |-' | | |-' | | 0 | | | |<---| | |<---| | | +---+---+ +---+---+ +---+---+