Автор работы: Пользователь скрыл имя, 07 Мая 2013 в 15:24, контрольная работа
1. Задание
Описать класс, реализующий бинарное дерево, обладающее возможностью добавления новых элементов, удаления существующих, поиска элемента по ключу, а также последовательного доступа ко всем элементам.
Написать программу, использующую этот класс для представления англо-русского словаря.
АКАДЕМИЯ МАРКЕТИНГА И СОЦИАЛЬНО-ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ (ИМСИТ г. Краснодар)
Факультет информатики и ВТ
Кафедра компьютерных систем управления
и обработки информации
КОНТРОЛЬНАЯ РАБОТА
по дисциплине:
«Объектно-ориентированное программирование»
Работа выполнена студентом
4 курса гр. 10-ЗСПО-01
Болбат Александром Александровичем
Научный руководитель
к. ф.-м., доцент
Бужан В.В.
г. Краснодар
2012
Описать класс, реализующий
бинарное дерево, обладающее возможностью
добавления новых элементов, удаления
существующих, поиска элемента по ключу,
а также последовательного
Написать программу, использующую этот класс для представления англо-русского словаря.
#include "stdafx.h"
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
/**
*@brief класс, обеспечивающий работу с листьями дерева
*/
class Leaf
{
public:
Leaf *left;
Leaf *right;
string rus_word;
string eng_word;
Leaf *rootPtr;
Leaf();
};
/**
*@brief класс, обеспечивающий работу со словарем
*/
class Dictionary
{
friend Leaf;
public:
Dictionary(string &ew, string &rw);
Dictionary();
void InsertNode(string &, string &);
void See();
void Search(string &);
void InsertRoot(Leaf *);
Leaf* Delete(string &);
const string& operator [] (string&);
private:
void InsertNodeHelper(Leaf **, string &, string &);
void SeeHelper(Leaf *);
void SearchHelper(Leaf *, string &);
Leaf* DeleteHelper(Leaf * ,string &);
}
/**
* @brief оператор для поиска русского слова
* @param ew - английское слово
*/
const string & Dictionary::operator [] (string& ew)
{
string rw=Search(ew);
return rw;
}
/**
* @brief Функция создания корня дерева.
* @param ptr - указатель на класс Leaf
*/
void Dictionary::InsertRoot(Leaf *ptr)
{
rootPtr = ptr;
}
/**
* @brief конструктор класса Dictionary
* @param ew - английское слово
* @param rw русское слово
*/
Dictionary::Dictionary(string &ew, string &rw)
{
eng_word = ew;
rus_word = rw;
left = right = 0;
}
/**
* @brief конструктор класса Leaf
*/
Leaf::Leaf()
{
rootPtr = 0;
}
/**
* @brief интерфейс функции вставки узла
* @param ew - английское слово
* @param rw - русское слово
*/
void Dictionary::InsertNode(string &ew, string &rw)
{
InsertNodeHelper(&rootPtr, ew, rw);
}
/**
* @brief функция вставки узла
* @param ptr - элемент класса Leaf
* @param ew - английское слово
* @param rw - русское слово
*/
void Dictionary::InsertNodeHelper(
{
if(*ptr==0)
{
*ptr = new Dictionary(ew, rw);
}
else
if(ew < (*ptr)->eng_word)
InsertNodeHelper(&((*ptr)->
else
if(ew > (*ptr)->eng_word)
InsertNodeHelper(&((*ptr)->
}
/**
* @brief интерфейс функции просмотра словаря
*/
void Dictionary::See()
{
SeeHelper(rootPtr);
}
/**
* @brief функция просмора словаря
* @param ptr - указатель на элемент класса Leaf
*/
void Dictionary::SeeHelper(Leaf *ptr)
{
if(ptr!=0)
{
cout<<ptr->eng_word<<"-"<<ptr-
SeeHelper(ptr->left);
SeeHelper(ptr->right);
}
}
/**
* @brief интерфейс функции поиска узла
* @param ew - английское слово
*/
string Dictionary::Search(string &ew)
{
string shame=SearchHelper(rootPtr, ew);
return shame;
}
string Dictionary::SearchHelper(Tree *ptr, string &ew)
{
if(ptr)
{
if(ptr->eng_word==ew)
{
cout<<"Your Word"<<endl;
return ptr->rus_word;
}
SearchHelper(ptr->right, ew);
SearchHelper(ptr->left, ew);
}
else
return "there is no this word";
}
/**
* @brief интерфейс функции удаления узла
* @param ew - английское слово
*/
Leaf* Dictionary::Delete(string &ew)
{
return DeleteHelper(rootPtr, ew);
}
/**
* @brief функция удаления узла
* @param ptr - указатель на элемент класса Leaf
* @param ew - английское слово
*/
Leaf* Dictionary::DeleteHelper(Leaf *ptr, string &ew)
{
Leaf * deleting_el, *prev_deleting_el, *record, *prev_record;
deleting_el = ptr;
prev_deleting_el = 0;
while((deleting_el!=0)&&(
{
prev_deleting_el = deleting_el;
if(deleting_el->eng_word > ew) deleting_el = deleting_el->left;
else deleting_el = deleting_el->right;
}
if(deleting_el==0)
{
cout<<"Deleting element is not found"<<endl;
return ptr;
}
if (deleting_el->right == 0) record = deleting_el->left;
else
if (deleting_el->left == 0) record = deleting_el->right;
else
{
prev_deleting_el = deleting_el;
record = deleting_el->left;
while(record->right!=0)
{
prev_record = record;
record = record->right;
}
if(prev_record = deleting_el) record->right = deleting_el->right;
else
{
record->right = deleting_el->right;
prev_record->right = record->left;
record->left = prev_record;
}
}
if(deleting_el==ptr)
ptr = record;
else
if(deleting_el->eng_word < prev_deleting_el->eng_word)
prev_deleting_el->left =record;
else prev_deleting_el->right = record;
return ptr;
}
int main(int argc, char* argv[])
{
string ew, rw , str;
Dictionary dict;
int menu, pos;
cout<<"MENU"<<endl;
cout<<"If you want input dictionary from file enter 1:"<<endl;
cout<<"If you want input dictionary from keyboard enter 2:"<<endl;
cout<<"If you want exit input 0:"<<endl;
cin>>menu;
ifstream fin("dictionary.txt");
switch (menu)
{
case 0:
{
exit(1);
}break;
case 1:
{
while(getline(fin, str))
{
pos = str.find(' ');
ew = str.substr(0, pos);
rw = str.substr(pos+1);
dict.InsertNode(ew, rw);
}
} break;
case 2:
{
cout<<"If you want stop input press q"<<endl;
while(1)
{
cout<<"Input english word:"<<endl;
cin>>ew;
if(ew=="q") break;
cout<<"Input translation:"<<endl;
cin>>rw;
dict.InsertNode(ew, rw);
}
}break;
}
while(1)
{
cout<<"MENU 2"<<endl;
cout<<"If you want input new word enter 1:"<<endl;
cout<<"If you want search some word enter 2:"<<endl;
cout<<"If you want delete some word enter 3:"<<endl;
cout<<"If you want see the dictionary enter 4:"<<endl;
cout<<"If you want exit enter 0:"<<endl;
cin>>menu;
switch(menu)
{
case 0:
{
exit(1);
}break;
case 1:
{
cout<<"Input english word:"<<endl;
cin>>ew;
cout<<"Input translation:"<<endl;
cin>>rw;
dict.InsertNode(ew, rw);
}break;
case 2:
{
cout<<"Input searching word:"<<endl;
cin>>ew;
cout<<dict[ew]<<endl;
}break;
case 3:
{
cout<<"Enter word which you want delete:"<<endl;
cin>>ew;
dict.InsertRoot(dict.Delete(
}break;
case 4:
{
dict.See();
}break;
}
}
return 0;
}
Добавление и удаление слов при вводе с клавиатуры
Информация о работе Контрольная работа по «Объектно-ориентированное программирование»