Реализация комбинированной структуры данных на основе статического списка упорядоченных двунаправленных динамических списков

Министерство образования и науки Российской Федерации

 

КНИТУ-КАИ

имени А.Н.Туполева

==============================================================

Институт Технической кибернетики и информатики

Кафедра ПМИ им. Ю. В. Кожевникова

 

 

 

 

 

 

 

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к

курсовой работе

по  дисциплине

«Алгоритмы и структуры данных»

на тему: «Реализация комбинированной структуры данных на основе статического списка упорядоченных двунаправленных динамических списков»

 

 

 

 

 

 

 

 

 

 

 

 

Выполнил: Студент группы 4217.

Валиев И. И.

Проверил: Сотников С.В.

 

 

 

 

 

 

 

 

 

КАЗАНЬ 2013.

Оглавление

Введение.

Типизация данных является одним из фундаментальных понятий современного программирования. Отнесение переменных к тому или иному типу позволяет установить внутренний формат хранения значений этой переменной и набор допустимых операций. Все распространенные языки программирования имеют набор базовых простейших типов данных (целочисленные, вещественные, символьные, логические) и возможность объединения их в составные наборы – массивы, записи, файлы. Понятие структуры данных определяется двумя моментами:

• способом объединения отдельных компонент в единую структуру

• способами обработки как отдельных компонент структуры, так и всей структуры в целом.

Большинство дополнительных структур данных можно реализовать двумя способами:

• статически на основе массива

• динамически с помощью специальных переменных-указателей.

Каждый из этих способов имеет свои преимущества и недостатки.

 

 

 

 

 

 

 

 

 

 

1. Постановка задачи

Общая постановка задачи: реализовать комбинированную структуру данных на основе структурного подхода.

Общие требования:

1. Реализация всех необходимых операций (добавление и удаление в основной и присоединенной структурах).

2. Возможность сохранения всей структуры во внешнем файле (текстовом или XML) с обратной загрузкой

3. Реализация структуры для хранения и обработки данных конкретной информационной задачи

4. Именование типов, структур и их полей в соответствии с конкретной

информационной задачей.

 

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

Информационное наполнение: Железная дорога (название) - композиция депо (номер). Депо - композиция электровозов(марка, регистрационный номер) .

Выбранный язык реализации: C++.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Теоретическое описание используемых структур данных с алгоритмами реализации основных операций.

Используемые структуры данных:

1. Статический список.
2. Упорядоченный двунаправленный динамический список.

1. Структура данных типа «Список».

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

Стандартный набор операций со списком включает:

• добавление нового элемента с поиском необходимого места для него с проверкой возможности добавления элемента
• удаление заданного элемента
• проход по списку от первого элемента к последнему с выполнением заданных действий
• поиск в списке заданного элемента

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

2. Статическая реализация списка.

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

Этот способ реализации списка на основе массива использует принцип указателей (но БЕЗ динамического распределения памяти). В этом случае каждый элемент списка (кроме последнего) должен содержать номер ячейки массива, в которой находится следующий за ним элемент. Это позволяет РАЗЛИЧАТЬ физический и логический порядок следования элементов в списке.

Проход по списку:

• ввести вспомогательную переменную Current для отслеживания текущего элемента списка и установить Current := StatList [ 0 ].Next;
• организовать цикл по условию  Current = 0, внутри которого обработать текущий элемент StatList [ Current ].Inf  и изменить указатель  Current  на следующий элемент:  Current := StatList [ Current ].Next

Алгоритм добавления элемента перед заданным включает следующие шаги:

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

Удаление элемента списка включает в себя:

• определение каким-то образом удаляемого элемента
• поиск удаляемого элемента в списке с одновременным отслеживанием элемента-предшественника;
• изменение связующей части элемента-предшественника с индекса  i  на индекс-значение связующей части удаляемого элемента  i:
• обработка удаляемого элемента
• включение удаленного элемента во всп-ый список без его уничтожения или освобождение ячейки  i  с включением ее в список свободных ячеек

3. Динамическая реализация упорядоченного двунаправленного списка.

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

Для удобства реализации будем считать, что список ВСЕГДА содержит хотя бы один элемент-заголовок с адресом первого реального элемента списка. Это позволяет унифицировать процедуры добавления и удаления крайних элементов и устранить некоторые проверки. Адрес элемента-заголовка задается переменной-указателем  Head. Эта переменная устанавливается при первоначальном создании списка и в дальнейшем НЕ изменяется. Для реализации основных действий используются вспомогательные ссылочные переменные.

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

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

 

Аналогично обычным спискам, удобно ввести фиктивный заголовочный элемент, а поскольку двунаправленные списки являются симметричными, удобно сделать их замкнутыми, кольцевыми: правая ссылка последнего элемента указывает на заголовок, а левая ссылка заголовка – на последний элемент. Адрес заголовка определяется указателем  pHead.

 

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

Двунаправленный список можно реализовать как на основе массива (причем – обеими способами), так и динамически.

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

type   pDin2Item = ^ TDin2Item;       {ссылочный тип}

                        TDin2Item = record          {базовый тип}

                                   inf :   <тип информационной части>;       

                         left, right : pDin2Item;          {адреса соседних элементов} 

                                end;

Если  pHead  есть указатель на заголовок, то пустой список создается так:

• выделяется память под заголовок, адресуемая указателем  pHead
• оба ссылочных поля заголовка устанавливаются в адрес самого заголовка:  pHead^.left := pHead;  pHead^.right := pHead;

(при этом пустая ссылка  nil  нигде НЕ используется!)

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

• устанавливаем начальное значение указателя текущего элемента на последний элемент списка:  pCurrent := pHead^.left;
• организуем цикл прохода до достижения заголовка

while  pCurrent <> pHead  do  pCurrent := pCurrent^.left;

 

Удаление заданного элемента требует изменения большего числа ссылочных полей. Надо изменить правый указатель у левого соседа удаляемого элемента и левый указатель у правого соседа.

 

Если удаляемый элемент адресуется указателем  pCurrent, то  pCurrent^.left  определяет адрес левого соседа, а  pCurrent^.right – адрес правого соседа. Тогда необходимые изменения реализуются так:

pCurrent^.left^.right := pCurrent^.right;

pCurrent^.right^.left := pCurrent^.left;

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

 

Необходимые присваивания (порядок следования важен!):

pTemp^.right := pCurrent^.right;

pTemp^.left := pCurrent;

pCurrent^.right^.left := pTemp;

pCurrent^.right := pTemp;

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

 

 

 

 

 

 

3. Комбинированная структура данных «Статический список динамических упорядоченных двунаправленных списков»

Статический список динамических упорядоченных двунаправленных списков – комбинированная структура данных, реализованная на основе статического списка и динамических упорядоченных двунаправленных списков. Статический список является основной структурой, динамическая упорядоченный двунаправленный список – присоединенной.

Основной набор операций:

• добавление элемента в основную структуру;
• удаление элемента из основной структуры, при этом удаляются все элементы присоединенной структуры;
• добавление элемента в присоединенную структуру, упорядочивается при добавлении;
• удаление элемента из присоединенной структуры;
• проход по всей структуре;

1. Графическое представление комбинированной структуры данных.

4. Руководство для программиста.

1. Описание структуры проекта.

Для разработки проекта была использована следующая среда разработки программного обеспечения: Microsoft Visual Studio 2012.

Весь программный код, включая основную программу, хранится в файлах .cpp . Инструментарий Microsoft Visual Studio 2012 использует расширение .vcxproj и .sln. Никакие сторонние библиотеки для успешной компиляции проекта не требуются.

2. Описание разработанных структур.

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

#define SIZE 20

struct ZD                              //Структура железной дороги

{

string name;               //название железной дороги