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

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

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

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

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

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

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

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

НОВОСИБИРСК 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. Сравниваем значения двух соседних элементов, при необходимости (если нарушается правило возрастания элементов списка на данном участке) производим обмен ссылок, меняя элементы местами.

 

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

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

.        Открываем бинарный файл, в котором записана структура.

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

.        Для первого созданного списка вызываем функцию чтения из бинарного файла void load (), описанную в классе list, которая имеет следующий алгоритм:

3.1.   Создаем массив элементов (наш список) известной длины.

3.2.   Первый элемент создаем и считываем с бинарного файла "вручную" с помощью перегруженной операции чтения с бинарного файла (для типов Int и man).

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

.4.     Заметим, что началом списка является самый первый созданный элемент, концом - самый последний.

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

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

 

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

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

.        Создаем (если еще не создан) новый бинарный файл или открываем старый с учетом того, что для новой записи туда, старые данные удаляются.

2.      В цикле вызываем для каждого списка из списка верхнего уровня функцию записи в бинарный файл void save (), описанную в классе list.

2.1.   В цикле записываем в файл каждый элемент списка.

.        Закрываем файл после записи.

 

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

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

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

.        Осуществляется проход по списку верхнего уровня в два этапа (аналогично пузырьковой сортировки).

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

 

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

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

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

2.      Если список не пуст, то в цикле будет выводится:

2.1.   Для каждого списка из списка верхнего уровня длина списка, двоеточие.

2.2.   Затем для каждого списка вызываемся метод void print (), описанный в классе list: через пробел выведутся все элементы этого списка.

Рис. 5

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

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

Данный класс не имеет ни одного приватного поля.

Зато имеются два общедоступных поля:

.        Указатель на объект шаблонного класса элемента списка element<T> (T* obj)

2.      Указатель на следующий элемент списка шаблонного класса element<T> (element<T>* next)

Реализовано два конструктора:

.        Конструктор без параметров, то есть конструктор по умолчанию (element<T> ())

2.      Конструктор с параметрами (element<T> (T* obj))

Методы данного класса:

.        Метод вывода элемента на консоль (void print ())

 

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

Данный класс имеет одно приватное поле:

1.      Поле count - размер списка (int count;)

Также имеются три общедоступных поля:

.        Указатель на начало списка шаблонного класса element<T> (element<T> *begin)

2.      Указатель на конец списка шаблонного класса element<T> (element<T> *end)

.        Указатель на следующий элемент списка шаблонного класса list<T> (list<T>* next)

Реализован один конструктор:

.        Конструктор без параметров, то есть конструктор по умолчанию (list ())

Методы данного класса:

.        Метод вывода объекта класса (void print ());

2.      Метод добавления элемента в список в список верхнего уровня (с конца) (void push (T* obj)

3.      Метод добавления элемента в список по логическому номеру (void insert (int number, T* obj))

.        Метод добавления элементов в список с сохранением упорядоченности (void add (T* obj))

.        Метод удаления элементов списка (с начала) (void pop ())

.        Метод удаления элементов списка по логическому номеру (void erase (int number))

.        Метод сортировки элементов списка (void sort ())

.        Метод записи элементов списка в бинарный файл (void save (fstream& f))

.        Метод чтения элементов списка из бинарного файла (void load (fstream& f))

.        Метод, возвращающий число элементов в списке (int get_count ())

Описание действия этих методов по сути представлены в предыдущей главе.

 

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

Данный класс имеет три приватных поля:

.        Поле recommend_size_of_list - рекомендуемый размер списка (int recomend_size_of_list)

.        Поле count_list - количество списков (или количество элементов в списке верхнего уровня) (int count_list)

3.      Поле сount_all_element - общее количество всех элементов по всем спискам (int count_all_element)

Также имеются два общедоступных поля:

.        Указатель на начало списка верхнего уровня шаблонного класса master_list<T> (list<T>* begin)

.        Указатель на конец списка верхнего уровня шаблонного класса master_list<T> (list<T>* end)

Реализован один конструктор:

1.         Конструктор с параметрами (master_list (int value))

Методы данного класса:

1.         Метод вывода объекта класса (void print ());

2.         Метод добавления списка в список верхнего уровня (с конца) (void push (T* obj)

3.         Метод добавления списка по логическому номеру (void insert (int number_master_list, int number_list, T* obj))

4.         Метод добавления списка с сохранением упорядоченности в списке (void add (T*obj))

5.         Метод удаления списка (с начала) (void pop ())

6.         Метод удаления списка по логическому номеру (void erase (int number_master_list, int number_list))

7.         Метод сортировки списков (void sort ())

8.         Метод балансировки списков (void balansing ())

9.         Метод записи списков в бинарный файл (void save ())

10.       Метод чтения списков из бинарного файла (void load ())

11.       Перегруженный оператор записи в бинарный файл (friend fstream& operator>> (fstream& f, int& mas))

12.       Перегруженный оператор чтения из бинарного файла (friend fstream& operator<< (fstream& f, int* mas))

Описание действия этих методов по сути представлены в предыдущей главе.

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

Пользовательский интерфейс представлен системой меню. Само меню представляет собой оператор выбора switch ().

При запуске программы пользователь видит следующее меню:

Для вызова пункта меню нужно ввести его номер.

Пример добавления элементов списка:

Пример вывода на экран:

Пример удаления элемента по логическому номеру:

Пример удаления элемента (с начала):

Пример балансировки:

Так было:

Так стало:

Пример записи структуры в бинарный файл:

Пример чтения структуры из бинарного файла:

Пример сортировки списков:

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

Для проверки скорости выполнения операции сортировки была выполнен эксперимент с количеством элементов 20 штук. Время сортировки такого количества элементов списка составило 10 524 миллисекунд.

Таким образом, сортировка списка с большим количеством элементов выполняется за длительный промежуток времени. Это связано с тем, что сложность алгоритма пузырьковой сортировки вычисляется по формуле . Следовательно, на больших объемах данных данный вид сортировки неэффективен.

6. Выводы

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

Была разработана структура данных односвязный список верхнего уровня для хранения в нем элементов. Для этого было реализовано три класса: класс master_list, класс list, класс element.

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

Для комфортной работы с программой была создана система меню на базе оператора выбора switch.

Также были разработаны дополнительные классы, позволяющие работать с собственными типами данных (пользовательский класс man) и с типом данных int (класс Int).

 

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

При работе с программой могут возникнуть следующие ошибки:

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

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

1.      Подбельский В.В. Язык С++ - М.: Финансы и статистика, 2004 г.

2.      Павловская Т.А. С/С++. Программирование на языке высокого уровня. - СПб.: Питер, 2003. - 461с., ил.

.        Ильдар Ш Хабибуллин. Программирование на языке высокого уровня C/C++: [учебное пособие для вузов по направлению 654600 "Информатика и вычислительная техника"] - СПб: БХВ-Петербург, 2006, 485 с., ил.

4.      www.intuit.ru <http://www.intuit.ru/> - Фридман А.Л. Язык программирования  <http://www.intuit.ru/shop/catalog/product.xhtml?id=2459324>Си++ <http://www.intuit.ru/shop/catalog/product.xhtml?id=2459324>