«Коллекция данных – сбалансированное дерево поиска»
Скачать 305.47 Kb.
|
//Lab2.cpp #include "tree.h" #include #include void PrintMenu() //функция вывода меню { RusText("Главное меню: \n"); RusText("1 - вывод дерева на экран\n"); RusText("2 - опрос размера дерева\n"); RusText("3 - очистка дерева\n"); RusText("4 - проверка дерева на пустоту\n"); RusText("5 - добавление данных\n"); RusText("6 - удаление данных\n"); RusText("7 - поиск\n"); RusText("t - тестирование\n"); RusText("i - меню итератора\n"); RusText("q - выход из программы\n"); } void PrintItMenu() //функция вывода меню итератора { RusText("Меню итератора: \n"); RusText("1 - установка на первый элемент\n"); RusText("2 - установка на последний элемент\n"); RusText("3 - перейти к следующему элементу\n"); RusText("4 - перейти к предыдущему элементу\n"); RusText("5 - вывод текущего элемента\n"); RusText("6 - изменение текущего элемента\n"); RusText("7 - состояние итератора\n"); RusText("q - выход в главное меню\n"); } void Testing() { srand( (unsigned)time( NULL ) ); RusText("\nТестирование:\n"); int i=0, size=0, promah=0, promahR=0, pp=0, deli=0, type=0, rndkey=0, rnddata=0; double find_summ=0, add_summ=0, del_summ=0; double find_summR=0, add_summR=0, del_summR=0; bool pr=false; BST BST RusText("Выберите тип тестирования (1 - обычное, 2 - вырожденный случай): "); cin>>type; RusText("Введите количество элементов тестируемого дерева: "); cin>>size; RusText("Введите процент промахов (0-100): "); cin>>pp; int ppp=0; if (pp==0) ppp=0; else ppp=100/pp; int *Array=new int[size]; int progress=0; if (type==1) //Заполнение дерева { for(i=0;i { if (size>100) if (i%(size/100)==0) cout< pr=false; while(!pr) { rndkey=(rand()*rand()+rand()); rnddata=rand(); pr=true; for(int j=0;j if(Array[j]==rndkey) pr=false; } Array[i]=rndkey; TestT->Add(rndkey, rnddata); TestRT->Add(rndkey, rnddata); } } else if (type==2) { for(i=0;i { if (size>100) if (i%(size/100)==0) cout< rndkey=i*1000; rnddata=rand(); Array[i]=rndkey; TestT->Add(rndkey, rnddata); TestRT->Add(rndkey, rnddata); } } progress=0; RusText("Размерности деревьев: "); cout< cout<<"BST: "< cout<<"RND: "< RusText(": Сгенерированы деревья случайных элементов.\n"); for(i=0;i { if (size>100) if (i%(size/2/100)==0) cout< if (ppp!=0 && i%ppp==0) //промах поиска { pr=false; while(!pr) //выбираем несуществующий ключ { if (type==1) rndkey=(rand()*rand()+rand()); else rndkey=(double)rand()/RAND_MAX * (size*1000); rnddata=rand(); pr=true; for(int j=0;j if(Array[j]==rndkey) pr=false; } } else //не промах { int rndi=(double)rand() / RAND_MAX * (size-1); //выбираем существующий ключ rndkey=Array[rndi]; rnddata=rand(); } try { TestT->Search(rndkey); } catch (int a) { if (a==-1) promah++; if (a==-2) RusText("Ошибка\n\n"); } try { TestRT->Search(rndkey); } catch (int a) { if (a==-1) promahR++; if (a==-2) RusText("Ошибка в RND\n\n"); } find_summ+=TestT->np_find; find_summR+=TestRT->np_find; //удаление int rndi=(double)rand() / RAND_MAX * (size-1); //выбираем существующий ключ rndkey=Array[rndi]; deli=rndi; rnddata=rand(); TestT->Delete(rndkey); TestRT->Delete(rndkey); del_summ+=TestT->np_del; del_summR+=TestRT->np_del; pr=false; //вставка while(!pr) { if (type==1) rndkey=(rand()*rand()+rand()); else rndkey=(double)rand()/RAND_MAX * (size*1000); rnddata=rand(); pr=true; for(int j=0;j if(Array[j]==rndkey) pr=false; } Array[deli]=rndkey; TestT->Add(rndkey,rnddata); TestRT->Add(rndkey,rnddata); add_summ+=TestT->np_add; add_summR+=TestRT->np_add; } RusText(": Поиск завершен ( циклов: "); cout< RusText(": Удаление завершено ( циклов: "); cout< RusText(": Вставка завершена ( циклов: "); cout< RusText("- Результат поиска -\n"); RusText("Трудоемкость BST: "); cout< RusText(" (промахов : "); cout< RusText("Трудоемкость RND: "); cout< RusText(" (промахов : "); cout< RusText("- Результат вставки -\n"); RusText("Трудоемкость BST: "); cout< RusText("Трудоемкость RND: "); cout< RusText("- Результат удаления -\n"); RusText("Трудоемкость BST: "); cout< RusText("Трудоемкость RND: "); cout< RusText(":: Теоретическая трудоемкость: "); cout<<1.39*log((double)size)/log(2.0)< } void main() { srand( (unsigned)time( NULL ) ); char key,key2,key_t; BST BST RND RND RusText("Выберите тип дерева : 1 - BST, 2 - RND\n"); cin>>key_t; cout< if(key_t=='1') { while(1) { PrintMenu(); //вывод меню cin>>key; int k; int input,input2; cout< switch(key) { case '1': if (T->Show()); else RusText("Дерево пусто\n\n"); cout< break; case '2': RusText("Размерность дерева: "); cout< break; case '3': if (T->ClearTree()) RusText("Дерево очищено\n\n"); else RusText("Дерево пусто\n\n"); break; case '4': if (T->IsEmpty()) RusText("Дерево пусто\n\n"); else RusText("Дерево не пусто\n\n"); break; case '5': RusText("Введите ключ и данные для вставки: "); cin>>input; //ключ cin>>input2; cout< if (T->Add(input, input2)) RusText("Значение добавлено в дерево\n\n"); else RusText("Ошибка при добавлении\n\n"); break; case '6': RusText("Введите ключ для удаления: "); cin>>k; cout< if (T->Delete(k)) RusText("Элемент удален\n\n"); else RusText("Ошибка при удалении\n\n"); break; case '7': RusText("Введите ключ для получения данных: "); cin>>k; cout< try { cout< catch (int a) { if (a==-1) RusText("Узел с данным ключом не найден\n\n"); if (a==-2) RusText("Дерево пусто\n\n"); } break; case 't': Testing(); break; case 'q': return; //выход из программы default: RusText("нажмите другую клавишу\n\n"); break; case 'i': while(1) { PrintItMenu(); //вывод меню итератора cin>>key2; cout< switch(key2) { case '1': it.first(); break; case '2': it.last(); break; case '3': it.next(); break; case '4': it.prev(); break; case '5': try { cout<<*it< } catch(int er) { if (er==-1) {RusText("Итератор вне структуры\n\n"); } } break; case '6': try { int in; RusText("Введите новое значение: "); cin>>in; *it=in; } catch(int er) { if (er==-1) {RusText("Итератор вне структуры\n\n"); } } break; case '7': if(it.is_off()) RusText("Итератор вне структуры\n\n"); else RusText("Итератор в рабочем состоянии\n\n"); break; case 'q': break; default: RusText("нажмите другую клавишу\n\n"); break; } if (key2=='q') break; } } } } else if (key_t=='2') { while(1) { PrintMenu(); //вывод меню cin>>key; int k; int input,input2; cout< switch(key) { case '1': if (RT->IsEmpty()) { RusText("Дерево пусто\n\n"); break; } RT->Show(); cout< break; case '2': RusText("Размер дерева: "); cout< break; case '3': if (RT->ClearTree()) RusText("Дерево очищено\n\n"); else RusText("Дерево пусто\n\n"); break; case '4': if (RT->IsEmpty()) RusText("Дерево пусто\n\n"); else RusText("Дерево не пусто\n\n"); break; case '5': RusText("Введите ключ и данные для вставки: "); cin>>input; //ключ cin>>input2; cout< if (RT->Add(input, input2)) RusText("Значение добавлено в дерево\n\n"); else RusText("Ошибка при добавлении\n\n"); break; case '6': RusText("Введите ключ для удаления: "); cin>>k; cout< if (RT->Delete(k)) RusText("Элемент удален\n\n"); else RusText("Ошибка при удалении\n\n"); break; case '7': RusText("Введите ключ для получения данных: "); cin>>k; cout< try { cout< catch (int a) { if (a==-1) RusText("Узел с данным ключом не найден\n\n"); if (a==-2) RusText("Дерево пусто\n\n");; } break; case 't': Testing(); break; case 'q': return; //выход из программы default: RusText("нажмите другую клавишу\n\n"); break; case 'i': while(1) { PrintItMenu(); //вывод меню итератора cin>>key2; cout< switch(key2) { case '1': itr.first(); break; case '2': itr.last(); break; case '3': itr.next(); break; case '4': it.prev(); break; case '5': try { cout<<*itr< } catch(int er) { if (er==-1) {RusText("Итератор вне структуры\n\n"); } } break; case '6': try { int in; RusText("Введите новое значение: "); cin>>in; *itr=in; } catch(int er) { if (er==-1) {RusText("Итератор вне структуры\n\n"); } } break; case '7': if(itr.is_off()) RusText("Итератор вне структуры\n\n"); else RusText("Итератор в рабочем состоянии\n\n"); break; case 'q': break; default: RusText("нажмите другую клавишу\n\n"); break; } if (key2=='q') break; } } } } } |
Похожие:
 | Конспект урока по информатике для учащихся 11 класса «Средства поиска данных в Интернете» Введение. Содержание дисциплины и порядок ее изучения. Фактографический поиск. Математические модели фактографического поиска. Информационная... |  | Реферат на тему «Сбалансированное питание это здоровье нации» Здоровье человека важный показатель его личного успеха. Одним из важнейших условий сохранения и укрепления здоровья является сбалансированное... |
| Реферат на тему «Сбалансированное питание это здоровье нации» Здоровье человека важный показатель его личного успеха. Одним из важнейших условий сохранения и укрепления здоровья является сбалансированное... | | Коллекция/модуль поиска |
| В базе данных Исакова О. Н. Основы поиска патентов в базе данных Европейского патентного ведомства: Препринт 03 – Новосибирск: гпнтб со ран, 2003.... | | Программа дисциплины Технологии поиска, анализа данных и распространения информации в Интернет Значение проекта Семантическая Паутина для расширения возмож-ностей смыслового поиска информации в сети Интернет |
| Урока информатики по теме «Табличные базы данных». (Открытый урок.) Данный урок «База данных. Системы управления базами данных» является первым уроком по теме «Технологии хранения, поиска и сортировки... | | Коллекция обивочных тканей Данная коллекция станет украшением любой модели кроватей. Ткань относится к категории мебельного атласа отличается не только богатым... |
| Определитесь с инструментами поиска Для обнаружения в текстах фрагментов, аналогичных заданному, используются инструменты линейного поиска информации. К таким инструментам... | | Коллекция игр Играющие садятся в круг, ведущий объявляет, что все участники игры, начиная с первого, должны назвать по одному растению, причем... |
| Коллекция 038 Белгород Это пример платной текущей распечатки бдкр, вместо контактных данных указаны только номера коллекций и | | Коллекция 614 Тюмень Это пример платной текущей распечатки бдкр по комнатным растениям, вместо контактных данных указаны только |
| Коллекция 589 Мордовия, Саранск Это пример платной текущей распечатки бдкр по садовым овощным растениям, вместо контактных данных указаны | | Программа по формированию навыков безопасного поведения на дорогах... Сейба, дынное дерево, шоколадное дерево, пальмы, фикусы, гевея, кувшинка Виктория регия |
| Литература по химии. Азбука веб-поиска для химиков. Методика поиска... Химия и жизнь: научно-популярный журнал. Электронная версия научно-популярного журнала. Архив содержаний номеров. Доступ к полной... | | Тематика контента (источников, баз(ы) данных Архив (acs legacy Archives) 25-ти журналов коллекция ретроспективных выпусков журналов с 1879 по 1995гг. Реферативные источники |
