Разработка программы для создания и работы с двусвязным списком, состоящим из структур (сортировка списка по фамилии, т,е, по возрастанию), страница 2

·  Создание списка.

·  Просмотр списка.

·  Добавление в конец списка.

·  Корректировка списка (в данном пункте – должна происходить сортировка по фамилии, т.е. по возрастанию).

·  Выход.

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

Задача должна быть разбита на две подзадачи:

·  Реализация интерфейса для работы с пользователем.

·  Реализация класса двусвязного списка.

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

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

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

·  LPDOUBLEITEM     *Next;                    // адрес следующего элемента

·  LPDOUBLEITEM     *Prev;                    // адрес предыдущего элемента

·  LPSTR                        Name;                    // фамилия

·  int                                          Birthday;     // год рождения

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

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

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

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

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

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

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

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

·  Метод быстрой вставки.

·  Метод двоичной сортировки.

·  Пузырьковый метод.

 Мы остановимся на методе, который называется – «пузырьковый метод». Данный метод заключается в том, что «самый легкий» элемент, подымается вверх. Данный метод – прост в реализации, но очень ресурсоемкий, но для данного задания и для понимания принципов сортировки, является самым оптимальным.

Проектный раздел

          Программа реализована на языке программирования С++ и реализована в среде разработки Microsoft Visual Studio 2008.

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

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

Список, который использован в программе – является реализацией двусвязного шаблонного списка, подобный эквивалент которого реализован в стандартной библиотеке шаблонов – STL. Список был реализован с помощью Объектно-ориентированного программирования, т.е. реализован с помощью класса СDoubleList.

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

Далее описаны методы класса и их подробное назначение.

1.  DOUBLEITEM (LPDOUBLEITEM) – структура описывающая элемент двусвязного списка и содержащая указатели на предыдущий и последующие элементы двусвязного списка, а также содержащая специализирующую структуру.

2.  CDoubleList::CDoubleList() – конструктор по умолчанию, используется для создания объекта класса и для инициализации полей-членов класса в при его создании. Вызывается автоматически при создании объекта класса.

3.  CDoubleList::~CDoubleList() – деструктор по умолчанию, используется для разрушения объекта класса и для обнуления и удаления элементов, полей-членов класса, которые были созданы или проинициализированы в процессе работы объекта. Вызывается автоматически при удалении объекта (может быть вызван явно).

4.  bool CDoubleList::AddBegin( LPDOUBLEITEM Item ) – метод класса реализующий добавление элемента в начало списка. В качестве входного аргумента, принимает адрес нового элемента, который необходимо добавить в начало двусвязного списка. Возвращает значение типа BOOL, которое указывает на успешное добавление элемента в список, если результат равен TRUE и FALSE – если добавление не прошло.