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

.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>