Информатика и выч. техника \ Программирование на языках высокого уровня

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

*====================================================================================*/

typedef void (*LL_ItemRemovingNotification)(const void* userData);

/*====================================================================================

* «Колбэк» для нотификации о сортировке элементов. См. LL_SubscribeOnSortNotification()

*=====================================================================================*/

typedef int (*LL_CompareItems_cb)(const void* data1, const void* data2);

#endif

«LList.h» – заголовочный файл (только для внешних модулей), предоставляет программный интерфейс двусвязного списка.

#ifndef __LLIST_H__

#define __LLIST_H__

#include "macro.h"

#include "LListcmn.h"

//такое объявление структуры данных LL_LinkedList позволяет закрыть доступ к

//членам структуры внешним модулям.

typedef void LL_LinkedList;

//программный интерфейс предоставляемый двусвязным списком

LL_Error LL_Create(LL_LinkedList **newList);

LL_Error LL_PushLast(LL_LinkedList *list, void *data);

LL_Error LL_PushInSortOrder(LL_LinkedList *list, LL_SortOreder order, void *data);

LL_Error LL_MoveToItem(LL_LinkedList *list, LL_MoveTo dir);

void* LL_GetData(LL_LinkedList *list);

void* LL_GetDataByID(LL_LinkedList *list, int id);

LL_Error LL_SortList(LL_LinkedList *list, LL_SortOreder order);

LL_Error LL_SubscribeOnItemRemovingNotification(LL_LinkedList *list, LL_ItemRemovingNotification callback);

LL_Error LL_SubscribeOnSortNotification(LL_LinkedList *list, LL_CompareItems_cb callback);

LL_Error LL_RemoveAll(LL_LinkedList **list, boolean disableWarning);

#endif

«macro.h» – утилитный файл, содержит макросы и объявление типов данных.

#ifndef __MACRO_H__

#define __MACRO_H__

#define _crtdbg_map_alloc

#include <stdlib.h>

#include <crtdbg.h>

typedef enum boolean

{

    FALSE,

    TRUE

} boolean;

//ожидание какой-либо клавиши

#define WaitAnyKey() puts("\nPress any key to return to main menu..."); \

                     getch()

#endif


5.  Тестирование

Изначально программа разрабатывалась в среде Visual Studio 2010 Express Edition. Среда разработки была выбрана по причине богатого инструментария и удобства разработки. Затем, код готовой программы был портирован в среду разработки Borland С под DOS. Поэтому процесс тестирования был разбит на два основных этапа:

1.  Тестирование программы в процессе разработки в среде Visual Studio и доведение программы до стадии релиза (стадия разработки вплоть до релиза).

2.  Тестирование портированной программы под DOS (стадия портирования).

5.1.  Тестирование на стадии разработки вплоть до релиза

На этой стадии выполнялись следующие виды тестирования:

1.  Тестирование стабильности – производилось с целью выявить утечки памяти. Для этого был использован стандартный модуль, предоставляемый Visual Studio – crtdbg. Проверка наличия утечки памяти производилась каждый раз после запуска программы.

2.  Юнит-тестирование – после написания каждой отдельной функции, она проверялась на корректность работы при помощи подаваемых на вход различных параметров (корректных и некорректных, лежащих на границах условия).

3.  Тестирование функциональности. Для проверки функциональности были составлены тест-кейсы, по которым проверялась корректность работы программы в целом, реакция программы на введение некорректных данных, данных на границах условия.

4.  Стресс-тестирование проводилось путем ввода с клавиатуры беспорядочных данных, получаемых нажатием случайных клавиш, попытки переполнения буфера.

5.2.  Тестирование на стадии портирования

Очень важно было проверить, что портированная программа работает под DOS точно также как разработанная в среде Windows.

Для этого активно применялось тестирование функциональности. В частности, таким образом, были выявлены проблемы с функцией strcmp. В среде Windows функция возвращала значения -1 или 1, если строки были не равны. В среде DOS функция дополнительно возвращала разность в длине строк, что первоначальный алгоритм не учитывал.


Заключение

Программа была выполнена в соответствии с заданием. Чтобы избежать противоречия, заложенного в задании (это касается пункта меню «добавить новый элемент в соответствии с сортировкой списка»), был добавлен еще один пункт меню «сортировать список», т.к. добавление нового элемента так, чтобы элементы списка были отсортированы невозможно в неотсортированном списке.

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

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

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

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

1.  Википедия – свободная энциклопедия [Электронный ресурс] / Wikipedia, the free encyclopedia – Режим доступа: http://ru.wikipedia.org/wiki, свободный. – Загл. с экрана.

2.  Объектно-ориентированное программирование в C++. Лафоре Р. — СПб.: Питер, 2007. ­– 928 с.

3.  Алгоритмы: построение и анализ, 2-е издание: Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Пер. с анг. — М.: Издательский дом «Вильямс», 2005. – 1296 с.

Скачать файл