Структуры и алгоритмы обработки данных

Постановка задачи. 3
Основные идеи и характеристики применяемых методов 4
Дерево и поиск по дереву 4
Особенности реализации алгоритмов 5
Описание программы 8
Основные переменные и структуры 8
Описание подпрограмм 9
Листинг программы 12
Результаты работы программы 20

author);//вставляем данные в деревоtnode = Insert(tnode, &data[index], key);}//удаление временных массивовdelete[] weights;delete[] used;returntnode;}//*************************************************************************//рекурсивнаяочисткадерева//*************************************************************************voidTreeClearNext(stree *tnode){if(tnode != NULL){TreeClearNext(tnode->left);TreeClearNext(tnode->right);delete[] tnode->key;deletetnode;}}//*************************************************************************//поиск данных в дереве//*************************************************************************stree* TreeSearch(stree *tnode, unsignedchar* search_key){//если ключ не найден и узлы кончилисьif (tnode == NULL)return NULL;int result = StrCompare(search_key, tnode->key, KEY_LENGTH);//если ключ найден, возвращаем узел//если ключ меньше, ищем данные левее рекурсивно//если ключ больше, ищем данные правее рекурсивноif (result == 0)returntnode;elseif (result < 0)returnTreeSearch(tnode->left, search_key);elsereturnTreeSearch(tnode->right, search_key);}//*************************************************************************//рекурсивноевычислениедлиныочереди//*************************************************************************intQueueNext(squeue *qnode){if(qnode == NULL)return 0;returnQueueNext(qnode->next)+1;}//*************************************************************************//рекурсивнаяочисткаочередипоиска//*************************************************************************voidQueueClearNext(squeue *qnode){if(qnode != NULL){QueueClearNext(qnode->next);deleteqnode;qnode = NULL;}}//*************************************************************************//создание очереди поиска//*************************************************************************squeue* QueueFindNext(squeue *qnode, stree *tnode, unsignedchar* search_key){squeue *qnode_new;//ищем запись в дереве по ключуtnode = TreeSearch(tnode, search_key);//если найдена, записываем данные//и ищем дальше с обеих сторон от данного узла//так как ключи не уникальныif (tnode != NULL){qnode = QueueFindNext(qnode, tnode->left, search_key);//создаем новый элемент очередиqnode_new = newsqueue;qnode_new->data = tnode->data;qnode_new->next = NULL;if(qroot == NULL)qroot = qnode_new;elseqnode->next = qnode_new;qnode = qnode_new;qnode = QueueFindNext(qnode, tnode->right, search_key);}returnqnode;}//*************************************************************************//вывод члена очереди поиска//*************************************************************************voidPrintNext(squeue *queue){if (queue != NULL){//кодировкаDOS(866)setlocale(LC_CTYPE, ".866");//вывод с форматированием длины полей//с помощью замены (*) на указанное числоprintf("%.*s | %.*s | %.*s | %*d | %*d\r\n", AUTHOR_LENGTH, queue->data->author,TITLE_LENGTH, queue->data->title,PUBLISH_LENGTH, queue->data->publish,YEAR_LENGTH, queue->data->year,PAGES_LENGTH, queue->data->pages);PrintNext(queue->next);}}//*************************************************************************//вывод очереди поиска//*************************************************************************voidPrintQueue(squeue *qroot, unsignedchar *search_key){if (qroot != NULL) {//кодировкаWIN(1251)setlocale(LC_CTYPE, "");printf("Поключу ");//кодировкаDOS(866)setlocale(LC_CTYPE, ".866");printf("'%s'", search_key);//кодировкаWIN(1251)setlocale(LC_CTYPE, "");printf(" найдено %d авторов:\r\n\r\n", QueueNext(qroot));printf("%*s | %*s| %*s | %*s | %*s\r\n", AUTHOR_LENGTH, "Автор",TITLE_LENGTH, "Название",PUBLISH_LENGTH, "Издатель",YEAR_LENGTH, "год",PAGES_LENGTH, "стр.");PrintNext(qroot);}else{//кодировкаWIN(1251)setlocale(LC_CTYPE, "");printf("По ключу ");//кодировка DOS(866)setlocale(LC_CTYPE, ".866");printf("'%s'", search_key);//кодировкаWIN(1251)setlocale(LC_CTYPE, "");printf(" авторы не найдены\r\n");}}//*************************************************************************//загрузка базы данных в память//*************************************************************************intLoadDatabase(sBDRec *&recs){FILE *f;intfsize, fcount;errno_t err;//кодошибкифайловойоперации//открываем файл БД на чтение в бинарном видеerr = fopen_s(&f, filename, "rb");if( err != 0 )return 0;//получаем длину файла в байтахfseek(f, 0, SEEK_END);fsize = ftell(f);fseek(f, 0, SEEK_SET);//вычисление количества записей в базеfcount = fsize/sizeof(sBDRec);//создаем массив записейrecs = newsBDRec[fcount];//считывание базыfor (inti = 0; i < fcount; i++)fread(&recs[i], sizeof(sBDRec), 1, f);fclose(f);returnfcount;}//*************************************************************************//основная//*************************************************************************void main(){intrec_count;//числозаписейвБДsBDRec *recs;//массивзаписейБДstree *troot = NULL;//корень дерева поиска//загрузкабазыданныхrec_count = LoadDatabase(recs);if(rec_count == 0){printf("Ошибка открытия базы данных.");return;}//создание дереваtroot = TreeBuild_A1(troot, recs, rec_count);//кодировкa WIN(1251)setlocale(LC_CTYPE, "");//вывод количества записейprintf("База данных '%s' загружена. Числозаписей %d\r\n", filename, rec_count);//выполняем поиск записей по ключу //формируем и выводим очередьqroot = NULL;QueueFindNext(qroot, troot, SearchKey);PrintQueue(qroot, SearchKey);//очистка очереди для нового поискаQueueClearNext(qroot);qroot = NULL;//так как первый поиск ничего не нашел//то выполним поиск по первому ключу//в дереве для примера выводаSearchKey[0] = troot->key[0];SearchKey[1] = troot->key[1];SearchKey[2] = troot->key[2];QueueFindNext(qroot, troot, SearchKey);PrintQueue(qroot, SearchKey);//очистка очереди, дерева и данныхQueueClearNext(qroot);TreeClearNext(troot);delete[] recs;printf("\r\n");//паузаsystem("pause");}Результаты работы программы