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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Курсовая работа

по дисциплине: "Программирование"

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

Студентка: Попова Т.О.

Преподаватель: Васюткина.И.А.

НОВОСИБИРСК 2015

Оглавление

1. Описание задания

1.1 Требования к структуре данных

1.2 Содержание объекта данных

1.3 Вид структуры данных

2. Структурное описание разработки

2.1 Описание используемой структуры данных

2.2 Описание используемых форматов данных

2.3 Описание основных алгоритмов и их особенностей

2.3.1 Добавление в список списка верхнего уровня

2.3.2 Добавление в список списка верхнего уровня по номеру

2.3.3 Удаление из списка верхнего уровня по номеру

2.3.4 Удаление из списка списка верхнего уровня

2.3.5 Сортировка списков

2.3.6 Чтение структуры из бинарного файла

2.3.7 Запись структуры в бинарный файл

2.3.8 Балансировка списков списка верхнего уровня

2.3.9 Вывод структуры на экран

3. Функциональное описание разработки

3.1 Описание класса element

3.2 Описание класса list

3.3 Описание класса master_list

4. Описание пользовательского интерфейса

5. Контрольные примеры и временные характеристики

6. Выводы

6.1 Проведённая работа

6.2 Ошибки и неточности

Список литературы

1. Описание задания

1.1 Требования к структуре данных

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

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

1.2 Содержание объекта данных

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

структура база список односвязный

1.3 Вид структуры данных

Рис. 1. Односвязный список структур

2. Структурное описание разработки

2.1 Описание используемой структуры данных

Для решения поставленной задачи реализован шаблонный класс master_list, который представляет собой набор полей и методов для работы с односвязным списком списков (его еще называют списком верхнего уровня). Также реализован шаблонный класс list, который представляет собой набор полей и методов для работы со списками, заголовки которых содержатся в классе master_list. Также реализован шаблонный класс element, который представляет собой набор полей для работы с элементами списка.

Шаблонный класс element имеет указатель на объект шаблонного класса (T* obj), указатель на следующий элемент списка (element<T>* next), и конструктор без параметров, конструктор с параметрами, который получает параметром указатель на объект шаблонного класса (element<T> (T *obj)). Также в шаблонном классе element имеется метод print (), отвечающий за вывод элемента списка на экран.

Шаблонный класс list содержит указатель на начало списка (element<T>* begin), указатель на конец списка (element<T>* end), конструктор без параметров (list ()) и набор методов, позволяющих работать со списком через систему меню.

Шаблонный класс master_list включает в себя конструктор с параметрами (master_list (int value)), а также набор полей, методов и переопределённых операций, необходимых для работы с объектом данного класса.

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

Так как для записи в файл у хранящегося объекта должны быть переопределены операции ввода и вывода, то был создан класс Int ("обёртка") специально для работы с целочисленными значениями стандартного типа int, а именно для записи в файл посредством перегруженной операции ввода в поток или для чтения из файла посредством перегруженной операции вывода из потока.

Вся структура имеет вид, показанный на рис. 1.

Рис. 2

2.2 Описание используемых форматов данных

В классе master_list содержится пять общедоступных полей, два из которых являются динамическими типа list<T>* (поле list<T>* begin и list<T>*end), три других - нединамическими типа int.

В классе list содержится четыре поля: одно поле типа int и два поля типа element<T> (поле *begin - указатель на начальный элемент списка, *end - указатель на конечный элемент списка) и одно поле типа list (*next - указатель на следующий элемент в списке).

В классе element содержится два общедоступных поля: типа T (поле *obj - указатель на объект класса) и типа element<T> (поле *next - указатель на следующий элемент списка).

В пользовательском классе man содержится три общедоступных поля: два типа int и одно поле типа char*.

В "обертке", в классе Int содержится одно общедоступное поле типа int.

2.3 Описание основных алгоритмов и их особенностей

2.3.1 Добавление в список списка верхнего уровня

За добавление нового списка в список верхнего уровня отвечает функция void master_list<T>:: push (T* obj). Данная функция объявляется в шаблонном классе master_list и получает параметром указатель на объект нашего шаблонного класса. Новый список добавляется в конец списка верхнего уровня. Функция имеет следующий алгоритм:

Если список верхнего уровня пуст (рис. 3.1):

.        Объявляется указатель на начальный список в списке верхнего уровня.

2.      Он является и началом списка верхнего уровня и концом.

.        Вызов функции добавления элементов в список из класса list (заполнение списка элементами, число которых не превышает рекомендованного размера списка - заданного заранее значения):

3.1.   Создается новый элемент.

3.2.   Если список был пуст - он становится первым и последним элементом.

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

Если список верхнего уровня не пуст:

.        Объявляется указатель новый список в списке верхнего уровня.

2.      Он становится последним в списке верхнего уровня.

3.1.   Объявляется указатель на новый элемент.

3.2.   Если список был пуст - он становится первым и последним элементом.

.3.     Если список не был пуст - он становится последним элементом.

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

Данный алгоритм изображен на системе рисунков 3.

Рис. 3

Рис. 4

2.3.2 Добавление в список списка верхнего уровня по номеру

За добавление в список верхнего уровня отвечает функция void insert (int number_master_list, int number_list, T* obj). Данная функция объявлена в классе master_list. Элемент из списка списка верхнего уровня добавляется по логическому номеру. Функция имеет следующий алгоритм:

.        Осуществляется проход по списку верхнего уровня, при заполнении элементами простого списка;

2.      Для каждого элемента списка верхнего уровня вызывается функция добавления по логическому номеру в список void insert (int number, T* obj):

2.1.   Если добавление происходит в конец списка, то вызывается функция добавления элементов списка в конец списка (объявлена в классе list)

2.2.   Выделяем память под новый элемент, увеличиваем длину списка:

2.2.1. Если добавление происходит в начало списка, то следующий за новым элементом - бывшее начало списка, новым началом становится новый элемент.

2.2.2. Если добавление происходит не в начало списка и не в конец, то добавляем элемент по логическому номеру, совершаем сдвиг элементов после него по списку вправо, помня, что длина списка уже увеличена на 1.

2.3.3 Удаление из списка верхнего уровня по номеру

За удаление из списка верхнего уровня по логическому номеру отвечает функция void erase (int number_master_list, int number_list). Данная функция объявлена в классе master_list. Элемент из списка списка верхнего уровня удаляется по логическому номеру. Функция имеет следующий алгоритм:

.        Проверяется, пуст ли список верхнего уровня. Если пуст, то на экран выводится запись "empty" и происходит выход из функции;

4.      Если список верхнего уровня не пуст, то объявляется указатель на список списка верхнего уровня и указатель на предыдущий список списка верхнего уровня:

4.1.   Если удаление происходит с начала списка верхнего уровня, то для этого начального списка вызывается функция удаления элементов списка (объявлена в классе list). Если этот начальный список единственный в списке верхнего уровня, то при удалении всех элементов из него, произойдет его удаление (и уменьшение поля count_list с типом int, объявленного в классе master_list и отвечающего за подсчет количества списков в списке верхнего уровня). Если не единственный, то данный список получает значения элементов списка, следующего за начальным и удаляется начальный элемент списка, новый начальный список получает значения элементов сохраненного ранее списка:

При удалении не с конца и не с начала:

.1.1.  Как только нашли нужную позицию для удаления, сохраняем значение следующего элемента

4.1.2. Элемент, который следовал за удаляемым получает его позицию, сохраняя свое значение

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

.1.4.  Значение поля count, объявленного в классе list, имеющего тип int и отвечающего за подсчет элементов в списке, уменьшается на 1, так же как и значение поля count_all_element, имеющего тип int, объявленного в классе master_list и отвечающего за подсчет всех элементов во всех списках.

При удалении с конца:

.1.5.  Сохраняем значение предыдущего элемента от конца

4.1.6. Удаляется конец списка

.1.7.  Тот, что был предыдущим становится последним элементом списка

.1.8.  Значение поля count, объявленного в классе list, имеющего тип int и отвечающего за подсчет элементов в списке, уменьшается на 1, так же как и значение поля count_all_element, имеющего тип int, объявленного в классе master_list и отвечающего за подсчет всех элементов во всех списках.

4.2.   При удалении списка не с начала списка верхнего уровня, проходим по списку верхнего уровня в поисках заданного логического номера списка верхнего уровня. Уже для заданного логического номера вызываем функцию удаления элементов списка по номеру (объявлена в классе list)

.2.1.  Как только нашли нужную позицию для удаления, сохраняем значение следующего элемента

4.2.2. Элемент, который следовал за удаляемым получает его позицию, сохраняя свое значение

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

.2.4.  Значение поля count, объявленного в классе list, имеющего тип int и отвечающего за подсчет элементов в списке, уменьшается на 1, так же как и значение поля count_all_element, имеющего тип int, объявленного в классе master_list и отвечающего за подсчет всех элементов во всех списках.

При удалении с конца:

.2.5.  Сохраняем значение предыдущего элемента от конца

4.2.6. Удаляется конец списка

.2.7.  Тот, что был предыдущим становится последним элементом списка

.2.8.  Значение поля count, объявленного в классе list, имеющего тип int и отвечающего за подсчет элементов в списке, уменьшается на 1, так же как и значение поля count_all_element, имеющего тип int, объявленного в классе master_list и отвечающего за подсчет всех элементов во всех списках.

2.3.4 Удаление из списка списка верхнего уровня

За удаление из списка верхнего уровня отвечает функция void erase (int number_master_list, int number_list). Данная функция объявлена в классе master_list. Элемент из списка верхнего уровня удаляется с начала. Функция имеет следующий алгоритм:

.        Если количество всех элементов в списках равно нулю, то ограничимся тем, что удалим указатель на начало списка верхнего уровня.

2.      Если отсчет начала списка верхнего уровня идет с 0, то рассматриваем следующие частные случаи (предварительно уменьшив количество списков в списке верхнего уровня на 1):

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

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

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

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

2.      Если в списке есть только один элемент, то удаляем его и обнуляем ссылки.

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

2.3.5 Сортировка списков

За сортировку элементов в списках отвечает функция void sort (). Данная функция объявлена в классе master_list. Элементы сортируются по возрастанию. Функция имеет следующий алгоритм:

1.      Для каждого из списков в списке верхнего уровня вызывается функция сортировки void sort (), описанная в классе list.

.1.     Если список пуст или в нём есть всего лишь один элемент, то не предпринимаем никаких действий, так как это не имеет смысла.

1.2.   Если в списке больше одного элемента, то применяем известный метод сортировки - пузырьковая сортировка:

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

1.2.2. Сравниваем значения двух соседних элементов, при необходимости (если нарушается правило возрастания элементов списка на данном участке) производим обмен ссылок, меняя элементы местами.