Форум программистов, компьютерный форум CyberForum.ru

Англо-русского словарь методом дерева бинарного поиска - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Определить 3 точки, являющиеся вершинами треугольника, для которых разность точек вне е го и внутри является минимальной. http://www.cyberforum.ru/cpp-beginners/thread280192.html
В одномерном массиве с четным количеством элементов(2n) находятся координаты n точек плоскости.Они распологаются в следующем порядке:x1 y1,x2 y2, x3 y3 и т.д. Определить 3 точки, являющиеся вершинами треугольника, для которых разность точек вне е го и внутри является минимальной.
C++ Русские символы в BC31 Как в Borland C++ 3.1 печатать русские буквы?? И как их считать их файла?? CharToOem не работает. http://www.cyberforum.ru/cpp-beginners/thread280189.html
C++ Подсчет скобок в тексте
проверить, имеется ли в заданном тексте баланс открывающих и закрывающих круглых скобок. Помогите пожалуйста. Заранее спасибо !
Найти первый отрицательный член последовательности C++
найти U-первый отрицательный член последовательности: cos(ctg(n)), n=1,2,3... Помогите пожалуйста. Заранее благодарю !
C++ Написать программу которая вычисляет определитель квадратной матрицы http://www.cyberforum.ru/cpp-beginners/thread280168.html
Написать программу которая вычисляет определитель квадратной матрицы вещественных чисел 3х3.Значения матрицы вводятся пользователем.
C++ Структуры. Напишите программу. Очень нужно В компьютере автосалона хранятся сведения о продаваемых автомобилях: марка автомобиля, номер, год выпуска и фамилия авто владельца. Напечатать: --список автомобилей «старше» 2000 года; --сколько автомобилей продаёт гражданин Иванов; подробнее

Показать сообщение отдельно
TheAthlete
152 / 152 / 13
Регистрация: 31.08.2010
Сообщений: 534

Англо-русского словарь методом дерева бинарного поиска - C++

20.04.2011, 17:27. Просмотров 1961. Ответов 2
Метки (Все метки)

Здравствуйте!
Есть задача: реализовать англо-русский словарь с помощью бинарного дерева поиска. Решаю эту задачу на примере книги "Алгоритмы на С++ Роберт Седжвик".
Часть уже реализовал:

Item.h - АТД (абстрактный тип данных) элемента, содержит ключ (Key) - английское слово, соответствующее ему русское слово (item) и счетчик (количество обращений к ключу)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#ifndef ITEM_H
#define ITEM_H
 
#include <iostream>
#include <string>
 
typedef std::string Key;
 
class Item
{
    friend std::ostream &operator<<(std::ostream &os, const Item &x);
    friend std::istream &operator>>(std::istream &in, Item &x);
    friend bool operator==(const Item &lhs, const Item &rhs);
    friend bool operator<(const Item &lhs, const Item &rhs);
public:
    Item(const size_t c = 0) : Count(c) {}
    Item(const Key &itsKeyval, const std::string &itsInfo, const size_t c = 0) : keyval(itsKeyval), info(itsInfo), Count(c) {}
    ~Item() {}
 
    Key key()           const { Count++; return keyval; }
    std::string item()  const { return info; }
    bool null()         const { return keyval.empty(); }
    int count()         const { return Count; }
    
    bool scan(const Key &itsKeyval, const std::string &itsInfo, const size_t c);
    void show(std::ostream &os = std::cout) { os << keyval << " " << info << " " << Count << std::endl; }
 
private:
    Key keyval;
    std::string info;
    mutable size_t Count; // позволяет изменять переменную даже в константной функции-члене
};
 
#endif
Item.cpp

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include "Item.h"
#include <iostream>
 
using std::istream;
using std::ostream;
using std::string;
 
bool Item::scan(const Key &itsKeyval, const std::string &itsInfo, const size_t c) {
    Count = c;
    keyval = itsKeyval;
    info = itsInfo;
    return !keyval.empty() && !info.empty();
}
 
ostream &operator<<(ostream &os, const Item &x) {
    os << x.keyval << " " << x.info << " " << x.Count;
    return os;
}
 
istream &operator>>(istream &in, Item &x) {
    in >> x.keyval >> x.info >> x.Count;
    if (!in) x = Item(); // ввод неудачен: вернуть объект в стандартное состояние
    return in;
}
 
bool operator==(const Item &lhs, const Item &rhs) {
    return lhs.keyval == rhs.keyval;
}
 
bool operator<(const Item &lhs, const Item &rhs) {
    for(string::size_type ix1 = 0, ix2 = 0; ix1 != lhs.keyval.size() && ix2 != rhs.keyval.size(); ++ix1, ++ix2) {
        return lhs.keyval[ix1] < rhs.keyval[ix2];
    }
}
ST.h - Таблица символов на основе дерева бинарного поиска

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#ifndef ST_H
#define ST_H
 
#include <iostream>
 
template<typename Item, typename Key>
class ST
{
public:
    ST() : head(0) {}
    ~ST() {}
 
    Item search(Key v) { return searchR(head, v); }
    void insert(Item x) { insertR(head, x); }
    void show(std::ostream &os) { showR(head, os); }
    void remove(Item x) { removeR(head, x.key()); }
    
private:
    struct node {
        Item item;
        node *l, *r;
        node(Item x) : item(x), l(0), r(0) {}
    };
    
    typedef node *link;
    
    link head;
    Item nullItem;
 
    Item searchR(link h, Key v) {
        if (h == 0) return nullItem;
 
        Key t = h->item.key();
 
        if (v == t) 
            return h->item;
 
        if (v < t)
            return searchR(h->l, v);
        else
            return searchR(h->r, v);
    }
 
    void insertR(link &h, Item x) {
        if (h == 0) {
            h = new node(x);
            return;
        }
        if (x.key() < h->item.key())
            insertR(h->l, x);
        else
            insertR(h->r, x);
    }
 
    void showR(link h, std::ostream &os) {
        if (h == 0) return;
        showR(h->l, os);
        h->item.show(os);
        showR(h->r, os);
    }
 
    // Ротации в BST-деревьях
    void rotR(link &h) {
        link x = h->l;
        h->l = x->r;
        x->r = h;
        h = x;
    }
    
    void rotL(link &h) {
        link x = h->r;
        h->r = x->l;
        x->l = h;
        h = x;
    }
 
    // Разбиение BST-дерева
    void partR(link &h, int k) {
        int t = (h->l == 0) ? 0 : h->l->N;
        if (t > k) {
            partR(h->l, k);
            rotR(h);
        }
        if (t > k) {
            partR(h->r, k - t - 1);
            rotL(h);
        }
    }
 
    link joinLR(link a, link b) {
        if (b == 0) return a;
        partR(b, 0);
        b->l = a;
        return b;
    }
 
    void removeR(link &h, Key v) {
        if (h == 0) return;
        Key w = h->item.key();
        if (v < w) removeR(h->l, v);
        if (w < v) removeR(h->r, v);
        if (v == w) {
            link t = h;
            h = joinLR(h->l, h->r);
            delete t;
        }
    }
};
 
#endif
Внимание вопрос: при реализации разбиения BST-дерева (другое названиие бинарного дерева поиска) (метод Item partR(link &h, int k)), предполагается, что каждый узел дерева содержит размер своего поддерева (в данном методе это элемент h->l->N)

Я так полагаю, что необходимо добавить элемент N в структуру node:

C++
1
2
3
4
5
6
struct node {
        Item item;
        node *l, *r;
                      int N;
        node(Item x) : item(x), l(0), r(0), N(0) {}
    };
Только не пойму никак как определить размер поддерева для узла и тем самым записать это значение в N.

Зарание спасибо!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru