Разработка web-приложения. Задача. Загрузить в оперативную память компьютера и построить дерево поиска заданного типа для решения задачи по поиску записей
 Скачать 23.87 Kb.
|
|
Задача: Хранящуюся в файле базу данных, состоящую из 4000 записей (формат базы данных определяется вариантом) загрузить в оперативную память компьютера и построить дерево поиска заданного типа для решения задачи по поиску записей (задача определяется вариантом). Из найденных записей организовать список (очередь) и вывести их на экран. --- (файл base4.dat) База данных "Населенный пункт" Стpуктуpа записи: ФИО гражданина: текстовое поле 32 символа фоpмат <Фамилия>_<Имя>_<Отчество> Название улицы: текстовое поле 20 символов Номер дома: целое число Номер квартиры: целое число Дата поселения: текстовое поле 8 символов фоpмат дд-мм-гг Пpимеp записи из БД: Петpов_Иван_Федоpович___________ Ленина______________ 10 67 29-02-65 ---Вывести на экран количество и названия всех улиц из базы данных Вывести упорядоченный (по полю ФИО гражданина) список граждан проживающих на заданной улице не ранее, чем заданная дата поселения Название улицы и дату поселения вводить с клавиатуры ----Дерево поиска: Двоичное Б-дерево Текст программы: #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int numb; //номер пункта меню char s_street[21]; // заданное название улицы для сортировки char s_date[8]; // заданная дата для сортировки // Структура с данными "Населенный пункт" struct Data { char name[32]; // ФИО гражданина char street[20]; // название улицы short house; // номер дома short apartment; // номер квартиры char date[8]; // дата поселения }; Data records[4000]; // 4000 записей в ОЗУ //Структура содержащая элементы очереди struct List { Data* pData; // указатель на структуру с данными List* pNext; // указатель на следующий элемент в очереди }; List* pFirst; // указатель на 1-ый элемент в очереди List* pLast; // указатель на последний элемент в очереди //Вершины ДБ-дерева struct Vertex { Data* pData; Vertex* pLeft; //левый и правый "потомки" в дереве Vertex* pRight; int Balance; // параметр баланса }; Vertex* pRoot; // указатель на корень ДБ-дерева //Сравнение данных при добавлении вершин в ДБ-дерево int Compare(struct Vertex* pVert1, struct Vertex* pVert2) { //сравнение названий улиц if (strncmp(pVert1->pData->street, pVert2->pData->street, 20) < 0) { return 1; } if (strncmp(pVert1->pData->street, pVert2->pData->street, 20) > 0) { return 0; } //сравнение номера у домов if (pVert1->pData->house < pVert2->pData->house) { return 1; } if (pVert1->pData->house > pVert2->pData->house) { return 0; } //сравнение ФИО граждан if (strncmp(pVert1->pData->name, pVert2->pData->name, 32) < 0) { return 1; } if (strncmp(pVert1->pData->name, pVert2->pData->name, 32) > 0) { return 0; } //сравнение номеров квартир if (pVert1->pData->apartment < pVert2->pData->apartment) { return 1; } if (pVert1->pData->apartment > pVert2->pData->apartment) { return 0; } //сравнение дат if (strncmp(pVert1->pData->date, pVert2->pData->date, 8) < 0) { return 1; } if (strncmp(pVert1->pData->date, pVert2->pData->date, 8) > 0) { return 0; } } // Добавление новой вершины в Б-дерево void B_Tree(Vertex*& p, Vertex* pNew, int& VR, int& HR) // VR/HR-переменные, опр-щие вериткальный/горизонтальный рост дерева { if (p == NULL) { p = pNew; VR = 1; return; } if (Compare(pNew, p) == 1) { B_Tree(p->pLeft, pNew, VR, HR); if (VR) { if (p->Balance == 0) { Vertex* q = p->pLeft; p->pLeft = q->pRight; q->pRight = p; p = q; q->Balance = 1; VR = 0; HR = 1; } else { p->Balance = 0; HR = 1; } } else { HR = 0; } } else { B_Tree(p->pRight, pNew, VR, HR); if (VR) { p->Balance = 1; VR = 0; HR = 1; } else { if (HR) { if (p->Balance > 0) { Vertex* q = p->pRight; p->pRight = q->pLeft; p->Balance = 0; q->Balance = 0; q->pLeft = p; p = q; VR = 1; HR = 0; } else { HR = 0; } } } } } // Создание дерева void Create() { pRoot = NULL; Data* p = records; int VR, HR; for (int i = 0; i < 4000; i++) { VR = 1; HR = 1; Vertex* pNew = new Vertex; pNew->pData = p; pNew->pLeft = NULL; pNew->pRight = NULL; pNew->Balance = 0; B_Tree(pRoot, pNew, VR, HR); p++; } } // Добавление элемента в очередь void PushQueue(struct Data* pData) { struct List* p = new List; p->pData = pData; if (pFirst == NULL) { pFirst = p; } else { pLast->pNext = p; } pLast = p; pLast->pNext = NULL; } // Подсчет кол-ва элементов в очереди int Count_Queue() { int s = 0; for (List* p = pFirst; p != NULL; s++) { p = p->pNext; } return s; } // Сброс очереди void Reset_Queue() { List* p = pFirst; List* pNext2; for (; p != NULL; p = pNext2) { pNext2 = p->pNext; delete p; } pFirst = NULL; pLast = NULL; } // Отбор названий улиц void Selection_Street(struct Vertex *p) { if (p == NULL) { return; } Selection_Street(p->pLeft); if ((pLast == NULL) || (strncmp(pLast->pData->street, p->pData->street, 20) != 0)) { PushQueue(p->pData); } Selection_Street(p->pRight); } // Вывод на экран (построчно) void Print(int page) { List* p = pFirst; int i = 1, j; while (p != NULL) { j = i + page; if (j > Count_Queue()) { j = Count_Queue(); } printf("\n Всего записей: %i \n Записи с %i по %i", Count_Queue(), i, j); for (; (i <= j) && (p != NULL); i++) { printf("%.32s ул. %.20s д. %2i кв. %3i %.8s \n", p->pData->name, p->pData->street, p->pData->house, p->pData->apartment, p->pData->date); p = p->pNext; } rewind(stdin); system("pause"); break; } } // Чтение записей из файла в ОЗУ bool Read_to_RAM(char* name) { FILE* file = fopen(name, "rb"); if (file == NULL) { return false; } fread(records, sizeof(records), 1, file); fclose(file); return true; } //Основная функция int main() { setlocale(LC_ALL, "Russian"); // для вывода кириллицы в консоль Create(); pFirst = NULL; pLast = NULL; FILE* file; if ((file=fopen("BASE4.DAT", "rb"))==NULL) { printf("\n Ошибка! Файл base4.dat не найден."); system("pause"); return 0; } do { printf("\n---МЕНЮ---"); //организация меню printf("\n 1. Вывести названия улиц и подсчитать их количество."); printf("\n 2. Вывести упорядоченный список граждан проживающих на заданной улице не ранее, чем заданная дата поселения."); printf("\n 3. Выход."); printf("\n Введите номер выбранного пункта меню: "); scanf("%d", &numb); switch (numb) { case 1: { Reset_Queue(); Selection_Street(pRoot); printf("\n В ДБ-дереве найдена информация о %i улиц.\n", Count_Queue()); for (List* p = pFirst; p != NULL; p = p->pNext) { printf("ул. %.20s\n", p->pData->street); } system("pause"); break; } case 2: { printf("\n Введите название улицы: "); scanf("%s", s_street); printf("\n Введите дату поселения: "); scanf("%s", s_date); /* if (pFirst != NULL) { Print(); } else { printf("\n Ошибка. Не удалось найти информацию, соответствующую данным условиям."); system("pause"); }*/ break; } default: printf("\n Неверно выбран пункт меню.\n"); } } while (numb != 3); return 0; } |