Словарь — бинарное дерево

Уровень сложности:

Задание
Решение

Есть словарь — текстовый файл в котором хранится слово и его перевод, например:
apple:яблоко
mouse:мышь
………… и так далее.

Необходимо реализовать хранение слова и его перевода в бинарном дереве, и соответственно поиск по нему. То есть, мы вводим английское слово, происходит поиск по бинарному дереву, на выходе получаем русское слово.

К сожалению, решения данной задачи пока нет. Если Вы решили эту задачу, сообщите нам, и мы выложим её на сайте.

E-mail : admin@cppstudio.com

Следующие статьи помогут вам в решении данной задачи:

Работа с файлами в С++

Обсудить на форуме

Автор: admin

Дата: 12.09.2012

#include <iostream>
#include <fstream>
#include <string>
#include <map>

using namespace std;

string left (string c) {
    int i;
    
    for (i = 0; i < c.size(); i++)
        if (c.at(i) == ':')
            break;
    
    char str[i + 1];
    
    for (int j = 0; j < i; j++)
        str[j] = c.at(j);
    
    str[i] = '';
    
    return str;
}

string right (string c) {
    int i;
    
    for (i = 0; i < c.size(); i++)
        if (c.at(i) == ':')
            break;
    
    char str[c.size() - i];
    
    for (int j = 0; j < i; j++)
        str[j] = c.at(j + i + 1);
    
    str[i] = '';
    
    return str;
}

int main(void) {
    ifstream fin;
    map <string, string> dictonary;
    
    fin.open("/Users/Alexey/Desktop/input.txt");
    if (!fin.is_open()) {
        fin.close();
        cout << "Can't open file" << endl;
        return 0;
    }
    
    while (1) {
        string c;
        
        fin >> c;
        
        if (c.empty())
            break;
        
        dictonary[left(c)] = right(c);
        
    }
    fin.close();
    
    cout << "Kol-vo: " << dictonary.size() << endl;
    cout << endl;
    
    while (1) {
        int a;
        string tmp;
        
        
        cout << "Input 1 to fing string\n";
        if (!(cin >> a))
            break;
        if (a != 1)
            break;
        
        cout << "Input string\n";
        
        cin >> tmp;
        if (tmp.empty())
            break;
        
        auto it = dictonary.find(tmp);
        if (it != dictonary.end())
            cout << it->first << " : " << it->second << endl << endl;
        else
            cout << "Can't find" << endl << endl;
        
    }
    dictonary.clear();
    
    return 0;
}

Mechanic

02.08.2015

Предлагаю следующее решение:
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <cstring>
#include <clocale>
#include <locale.h>

using namespace std;



class Node{
    private:
        char *strEng, *strRus;
        Node *left, *right;
        
        int compare(char *nodeStr, char *newStr){//функция сравнивает 2 строки: возвращает 1, если 2я > 1й, 0 если 2=1, -1 если 2<1
            int i = 0;
            if (strlen(newStr) > strlen(nodeStr)){
                return 1;
            } else if (strlen(newStr) < strlen(nodeStr)){
                return -1;
            } else {
                while(i<strlen(newStr)){
                    if(newStr[i] > nodeStr[i]){
                        return 1;
                    } else if (newStr[i] < nodeStr[i]){
                        return -1;
                    }
                    i++;
                }
            }
            return 0;
        }
        
    public:
        Node(char *str1, char *str2) {
            strEng = str1;
            strRus = str2;
            left = right = NULL;
        }
        
        
        void add(char *str1, char *str2){
            int branch;
            branch = compare(strEng, str1);
            if(branch == 1){
                if(right != NULL){
                    right->add(str1, str2);
                } else {
                    right = new Node(str1, str2);
                }
            } else if (branch == -1){
                if(left != NULL){
                    left->add(str1, str2);
                    
                } else {
                    left = new Node(str1, str2);
                }
            }
        }
        
        void search(char *str){
            int branch;
            branch = compare(strEng, str);
            if(branch == 1){
                if(right != NULL){
                    right->search(str);
                } else {
                    cout << "can't find!" << endl;
                }
            } else if (branch == -1){
                if(left != NULL){
                    left->search(str);
                } else {
                    cout << "can't find!" << endl;
                }
            } else if (branch == 0){
                cout << strEng << ":" << strRus << endl;
            }
        }
        
        void printAll(){        
            if(right!=NULL){
                right->printAll();
            }
            cout << strEng << "-" << strRus << endl;
            if(left!=NULL){
                left->printAll();
            }
        }
};

Node *root = NULL;

void readFile(char *fileName){//считывает посимвольно файл и распознает символы, слова записывает в дерево
    ifstream file(fileName);
    if (!file.is_open()){
        cout << "can't open file!\n" << endl;
    } else {
        char s;
        
        char buff[32];
        char *str1, *str2;
        int i = 0, j = 0;

        while(file.read(&s, 1)) {
            if(i > 31){
                cout << "error!" << endl;
                break;
            }
            if(s == '\n') continue;
            
            if(s == ':'){
                str1 = new char [i];
                while(j<=i){
                    str1[j] = buff[j];
                    buff[j] = 0;
                    j++;
                }
                j=0;
                i=0;
                continue;
            }

            if(s == '\r'){
                str2 = new char [i];
                while(j<=i){
                    str2[j] = buff[j];
                    buff[j] = 0;
                    j++;
                }
                if (root != NULL){
                    root->add(str1, str2);
                } else {
                    root = new Node(str1, str2);
                }
                j=0;
                i=0;
                continue;
            }

            buff[i] = s;
            i++;
        }
    }
}

int printMenu(){
    int select;
    cout << "\nmenu: "
            "1) search word\t"
            "2) print tree\t"
            "3) exit\t: ";
    cin >> select;
    return select;
}

bool menuSelect(){//выполняет команды меню, также если вернет true в main прервет цикл, завершив работу программы
    int select = printMenu();
    char word[32];
    
    switch(select){
        case 1:
            cout << "enter word: ";
            cin >> word;
            root->search(word);
            break;
        case 2:
            cout << "tree: \n";
            root->printAll();
            break;
        case 3:
            return true;
            break;
        default:
            cout << "uncorrect input! please try again\n";
            menuSelect();
            break;
    }
}

/*
 * 
 */

int main(int argc, char** argv) {
    setlocale(LC_ALL, "Russian_Russia.866");//примечание: исходный файл должен быть закодирован в UTF-8
    
    readFile("dictionary.txt");
    bool exit = false;
    do {
        exit = menuSelect();
    } while(!exit);
        
    return 0;
}

jojogis

07.06.2015

#include <iostream>
#include <fstream>

using namespace std;
void find(){int i=0; char s[50];char word[50]; bool r=false;
cin>>word;
ifstream f("file");
while(!f.eof()){i=0;
f>>s;
 while(s[i]!=':'){
 if(s[i]!=word[i]){r=false;break;}else r=true;
 i++;}
 if(r){i++;while(s[i]!=''){cout<<s[i];i++;}cout<<endl;}
}
f.close();
}
int main(int v,char* a[]){
find();
}

petruska

09.12.2014

Програма отлично работает,но слова в файле должны быть сохр так:

apple:яблоко mouse:мышь ………… и так далее.

#include "stdafx.h" // here all libs


int _tmain(int argc, _TCHAR* argv[])
{

	setlocale(LC_CTYPE, "rus"); // fro russain leng
	char buffer[200]; //save data fom file

	// get string with roud to file
	string roud;
	cout << "Enter roud to file: ";
	getline(cin,roud);

	ifstream file(roud); // open file
	if ( !file )
	{
		cout << "Error, can't open file" <<endl;
		return 0;
	}
	file.getline(buffer,200); // save data on buffer
	file.close();  // close file

	//save on string vector separately all wods (eng and russians), use strtok func
	vector <string> vData(0);
    char * pch = strtok (buffer," :");
    while (pch != NULL) 
    {
		vData.push_back(pch);
        pch = strtok (NULL, " :");
    }

	// creat map with eng-rus words (benary trea)
	map <string,string> mp;
	//algorithm for save appropriate words
	int j=1,k=0;
	for (int i=0; i < vData.size()/2; i++)
	{
		mp.insert(pair<string,string>(vData[i+k],vData[i+j]));
		j++;
		k++;
	}

	// find rus word on trea
	string sFind;
	cout << "Enter word: ";
	getline(cin,sFind);

	map <string,string>::iterator p; // create iterator for search
	p=mp.find(sFind);
	if ( p != mp.end() )
		cout <<p->first<<" : " << p->second<<endl;
	else
		cout << "Can't find this word!" <<endl;

	return 0;
}

Оставить комментарий

Вы должны войти, чтобы оставить комментарий.

Словарь — бинарное дерево

Комментарии

Алеша Исмагилов

Mechanic

jojogis

petruska

Оставить комментарий