0 / 0 / 0
Регистрация: 09.06.2021
Сообщений: 5
1

Создайте частотный словарь на основе сбалансированного дерева

09.06.2021, 07:11. Показов 745. Ответов 7

В программе нужно построить дерево и реализовать функции поиска слова в тексте, количества его повторений. Столкнулась с проблемой "Вызвано необработанное исключение: нарушение доступа для чтения.
current было 0xCDCDCDCD." Как я поняла, это проблема с памятью, но разобраться почему конкретно она появилась я не смогла

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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
using namespace std;
#pragma warning(disable: 4018)
#pragma warning(disable : 4996)
#define TEXT "word1. word2. word3 word3 word4."
#define RED "\033[31m"
#define YELLOW "\033[33m"
#define RESET "\033[0m"
 
typedef struct branch {
    char word[20];
    int repeats_num;
    struct branch* left;
    struct branch* right;
} tree_t;
 
int Count_Words(char* str);
int Print_Text(char* text);
char** Make_Str_Array(int H, int L);
char** Split_Text(char* text);
int* Count_Frequency(char** words_arr, int H);
int Sort_Repeats(char** words_arr, int* repeats, int H);
int Print_Str_Array(char** words_arr, int* repeats, int H);
int Fill_Tree(tree_t* current, char** words_arr, int* repeats_arr, int L);
int Delete_Empty_Elements(char** words_arr, int* repeats, int H);
tree_t* Make_Vocabulary(char* text);
int Print_Tree(tree_t* current, int n);
int Find_Middle(int* array, int L);
int* Find_Entery(char* text, char* word, int repeats_num);
int Mark_Word(char* text, int* repeats_id, char* word);
int Print_Interface(tree_t* tree, char* text);
 
int main() {
    setlocale(0, "");
    
    char* text = new char[sizeof(TEXT)];
    strcpy(text, TEXT);
    Print_Text(text);
    tree_t* vocabulary = Make_Vocabulary(text);
    Print_Interface(vocabulary, text);
    delete[] vocabulary;
    return 0;
}
int Print_Text(char* text) {
    printf(" Текст:\n");
    for (int i = 0; i < strlen(text); i++) {
        if (*(text + i - 2) == '.') {
            printf("\n");
        }
        printf("%c", *(text + i));
    }
    printf("\n--------------------------------------\nКоличество слов: " RED "%d" RESET "\n--------------------------------------\n", Count_Words(text));
  
 
    return 0;
}
int Count_Words(char* text) {
    char* buffer = new char[strlen(text)+1];
    strcpy(buffer, text);
    int num = 1;
    while (strchr(buffer, ' ') != 0) {
        char* pointer = strchr(buffer, ' ');
        *pointer = '_';
        num++;
    }
    delete [] buffer;
    return num;
}
 
char** Make_Str_Array(int H, int L) {
    char** str_arr = new char* [H * sizeof(char*)];
    for (int i = 0; i < H; i++) {
        *(str_arr + i) = new char[L * sizeof(char)];
    }
    return str_arr;
}
 
char** Split_Text(char* text) {
    int height = Count_Words(text);
    int length = strlen(text)+1;
    char* buffer = new char[length];
    strcpy(buffer, text);
 
    while (strchr(buffer, '.') != 0) {
        char* pointer = strchr(buffer, '.');
        *pointer = ' ';
    }
    char** words_arr = Make_Str_Array(length, height);
    for (int i = 0, j = 0, k = 0; i < height && j < length; i++) {
        while (*(text + j) != ' ' && *(text + j) != '\0') {
            *(*(words_arr + i) + k) = *(text + j);
            if (*(text + j + 1) == '.') {
                j++;
            }
            j++;
            k++;
        }
        j++;
        k = 0;
    }
    return words_arr;
}
 
int* Count_Frequency(char** words_arr, int H) {
    int* repeats = new int[sizeof(int) * H];
    for (int i = 0; i < H; i++) {
        *(repeats + i) = 1;
        for (int j = 0; j < H; j++) {
            if (i != j && strcmp(*(words_arr + i), *(words_arr + j)) == 0) {
                strcpy(*(words_arr + j), "\0");
                *(repeats + i) += 1;
            }
        }
    }
    Sort_Repeats(words_arr, repeats, H);
    return repeats;
}
 
 
int Delete_Empty_Elements(char** words_arr, int* repeats, int H) {
    char** words_buffer = Make_Str_Array(H, 1);
    int* repeats_buffer = new int[sizeof(int) * H];
    int height = 0;
    for (int i = 0, j = 0; i < H; i++) {
        if (**(words_arr + i) != '\0') {
            strcpy(*(words_buffer + j), *(words_arr + i));
            *(repeats_buffer + j) = *(repeats + i);
            height++;
            j++;
        }
    }
    for (int i = 0; i < height; i++) {
        strcpy(*(words_arr + i), *(words_buffer + i));
        *(repeats + i) = *(repeats_buffer + i);
    }
    delete [] words_buffer;
    delete [] repeats_buffer;
    return height;
}
 
int Sort_Repeats(char** words_arr, int* repeats, int H) {
    int sequence = 0;
    while (sequence < H - 1) {
        sequence = 0;
        for (int i = 0; i < H - 1; i++) {
            if (*(repeats + i) > *(repeats + i + 1)) {
                {
                    int buffer = *(repeats + i);
                    *(repeats + i) = *(repeats + i + 1);
                    *(repeats + i + 1) = buffer;
                }
                char* buffer = new char[strlen(*(words_arr + i))+1];
                strcpy(buffer, *(words_arr + i));
                strcpy(*(words_arr + i), *(words_arr + i + 1));
                strcpy(*(words_arr + i + 1), buffer);
                delete [] buffer;
            }
            else {
                sequence++;
            }
        }
    }
    return 0;
}
 
int Print_Str_Array(char** words_arr, int* repeats, int H) {
    for (int i = 0; i < H; i++) {
        printf("Количество упомянаний слова \"" YELLOW "%s" RESET "\" " RED "%d" RESET "\n", *(words_arr + i), *(repeats + i));
    }
    printf("--------------------------------------\n");
    return 0;
}
 
int Fill_Tree(tree_t* current, char** words_arr, int* repeats_arr, int L) {
    if (L <= 0) return 1;
    int mean = Find_Middle(repeats_arr, L);
    strcpy(current->word, words_arr[mean]);
    current->repeats_num = repeats_arr[mean];
    current->left = new tree_t[sizeof(tree_t)];
    current->right = new tree_t[sizeof(tree_t)];
 
    Fill_Tree(current->left, words_arr, repeats_arr, mean);
    Fill_Tree(current->right, words_arr + mean + 1, repeats_arr + mean + 1, L - mean - 1);
    return 0;
}
 
tree_t* Make_Vocabulary(char* text) {
    char** words_array = Split_Text(text);
    int* repeats = Count_Frequency(words_array, Count_Words(text));
    int height = Delete_Empty_Elements(words_array, repeats, Count_Words(text));
    tree_t* vocabulary = new tree_t[sizeof(tree_t)];
    vocabulary->repeats_num = 0;
    Fill_Tree(vocabulary, words_array, repeats, height);
    return vocabulary;
}
 
 
 
int Print_Tree(tree_t* current, int n) {
    if (n == 0) {
        printf("Бинарное дерево слов:\n");
    }
    if (current && current->repeats_num == NULL ) return 0;
    else{
        Print_Tree(current->left, n + 5);
        for (int i = 0; i < n; i++) {
            printf(" ");
        }
        printf("%s %d\n", current->word, current->repeats_num);
        Print_Tree(current->right, n + 5);
    }
    return 0;
}
int* Find_Entery(char* text, char* word, int repeats_num) {
    char* buffer = new char[strlen(text)+1];
    strcpy(buffer, text);
    int* repeats_id = new int[sizeof(int) * repeats_num];
    int n = 0;
    while (strstr(buffer, word) != NULL) {
        char* pointer = strstr(buffer, word);
        *(repeats_id + n) = pointer - buffer;
        *pointer = '#';
        n++;
    }
    delete[] buffer;
    return repeats_id;
}
int Find_Middle(int* array, int L) {
    int *s_array=new int[L];
    int l = 0;
    for (int i = 0, j = 0; i < L - 1; i++) {
        if (*(array + i) != *(array + i + 1)) {
            *(s_array + j) = *(array + i);
            j++;
            l++;
        }
    }
    int i = L - 1;
    while (*(s_array + i) != *(s_array + (L / 2))) {
        i--;
    }
    return i;
}
int Mark_Word(char* text, int* repeats_id, char* word) {
    printf("Места упомянания слова " YELLOW "\"%s\"" RESET "\n", word);
    for (int i = 0, j = 0; i < strlen(text); i++) {
        if (i == *(repeats_id + j)) {
            printf(YELLOW);
            j++;
        }
        else if (*(text + i) == ' ' || *(text + i) == '.') {
            printf(RESET);
        }
        else if (*(text + i - 2) == '.') {
            printf("\n");
        }
        printf("%c", *(text + i));
    }
    printf("\n--------------------------------------\n");
    return 0;
}
 
int Tree_Find(tree_t* current, int num, char* text) {
    int result = 0;
    if (!current && !current->repeats_num) {
        result += Tree_Find(current->right, num, text);
        if (current->repeats_num == num) {
            int* repeats_id = Find_Entery(text, current->word, current->repeats_num);
            Mark_Word(text, repeats_id, current->word);
            result++;
        }
        result += Tree_Find(current->left, num, text);
    }
    return result;
}
int Tree_Find(tree_t* current, char* word, char* text) {
    int result = 0;
    if (current && current->repeats_num != 0) {
        result += Tree_Find(current->right, word, text);
        if (strstr(current->word, word) != NULL) {
            int* repeats_id = Find_Entery(text, current->word, current->repeats_num);
            Mark_Word(text, repeats_id, current->word);
            result = current->repeats_num;
        }
        result += Tree_Find(current->left, word, text);
    }
    return result;
}
 
 
int Print_Interface(tree_t* tree, char* text) {
    printf(
        "Команды:\n"
        RED " n" RESET " Найти слово по количеству упомянаний\n"
        RED " s" RESET " Найти количеству упомянаний слова\n"
        RED " p" RESET " Вывести в консоль дерево\n"
        RED " q" RESET " Выйти\n--------------------------------------\nВведите команду: "
    );
    char command = 'n';
    scanf("%c", &command);
    if (command == 'n') {
        int num = 1;
        printf("--------------------------------------\nВведите количеством упомянаний искомого слова:");
        scanf("%d", &num);
        printf("Слова с количеством упомянаний равным " RED "%d" RESET ":\n", num);
        if (Tree_Find(tree, num, text) == 0) {
            printf("Нет слов с таким количеством упомянаний\n");
        }
    }
    else if (command == 's') {
        char word[20] = {};
        printf("Введите слово:");
        scanf("%s", word);
        printf("Количеством упомянаний слова \"" RED "%s" RESET "\" = %d\n", word, Tree_Find(tree, word, text));
    }
    else if (command == 'p') {
        Print_Tree(tree, 0);
    }
    else if (command == 'q') {
        return 0;
    }
    command = '\0';
    while (command == '\0') {
        scanf("%c", &command);
    }
    Print_Interface(tree, text);
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.06.2021, 07:11
Ответы с готовыми решениями:

Частотный словарь с использованием дерева
Задача: определить понятие слово, прочитать текст и сформировать набор слов данного языка вместе с...

Создать частотный словарь на основе map
Нужно создать частотный словарь на основе map. На ввод подается текст. Вывести все слова,...

Алфавитно-частотный словарь на основе односвязного списка с применением токенов
Здравствуйте, дорогие форумчане! Возникла задача создать алфавитно-частотный словарь на основе...

Частотный словарь из слов текстового файла в виде дерева двоичного поиска
Задача: Построить частотный словарь из слов текстового файла в виде дерева двоичного поиска....

7
фрилансер
4171 / 3579 / 799
Регистрация: 11.10.2019
Сообщений: 9,633
09.06.2021, 07:36 2
zzppvvss,

для начала - это проблема с инициализацией:
C++
1
2
3
4
5
6
7
struct tree_t
{
    char word[20]{};
    int repeats_num{};
    struct tree_t* left{};
    struct tree_t* right{};
};
а затем - отладчик в руки - и где именно происходит остановка?

Не по теме:

в 207 строке нужен не NULL, а 0



Добавлено через 3 минуты
Цитата Сообщение от zzppvvss Посмотреть сообщение
current->left = new tree_t[sizeof(tree_t)];
    current->right = new tree_t[sizeof(tree_t)];
Цитата Сообщение от zzppvvss Посмотреть сообщение
tree_t* vocabulary = new tree_t[sizeof(tree_t)];
вот тут странное что-то. Зачем new[sizeof(tree_t)]?

Добавлено через 1 минуту
current->left = new tree_t; // и где delete ?

current->right = new tree_t; // и где delete ?

tree_t* vocabulary = new tree_t[тут количество элементов];
0
0 / 0 / 0
Регистрация: 09.06.2021
Сообщений: 5
09.06.2021, 07:40  [ТС] 3
Остановка происходит на 206 строке

Добавлено через 1 минуту
Код
tree_t* vocabulary = new tree_t[sizeof(tree_t)];
нужен для дерева с минимальным размером
0
фрилансер
4171 / 3579 / 799
Регистрация: 11.10.2019
Сообщений: 9,633
09.06.2021, 07:42 4
zzppvvss, дерево с минимальным размером - это 0 элементов ))

а тут
Цитата Сообщение от zzppvvss Посмотреть сообщение
tree_t* vocabulary = new tree_t[sizeof(tree_t)];
у тебя выделяется память на количество элементов, равное (зачееем?) размеру структуры tree_t в байтах
0
0 / 0 / 0
Регистрация: 09.06.2021
Сообщений: 5
09.06.2021, 07:46  [ТС] 5
на вопрос зачем нет ответа ;с
0
фрилансер
4171 / 3579 / 799
Регистрация: 11.10.2019
Сообщений: 9,633
09.06.2021, 07:47 6
Лучший ответ Сообщение было отмечено zzppvvss как решение

Решение

тут тоже похожая ошибка. Не нужно путать new с malloc - в new указывается количество элементов, а не байтов
Цитата Сообщение от zzppvvss Посмотреть сообщение
char** Make_Str_Array(int H, int L) {
    char** str_arr = new char* [H * sizeof(char*)];
    for (int i = 0; i < H; i++) {
        *(str_arr + i) = new char[L * sizeof(char)];
    }
    return str_arr;
}
1
0 / 0 / 0
Регистрация: 09.06.2021
Сообщений: 5
09.06.2021, 08:43  [ТС] 7
исправила, большое спасибо, программка запустилась! не успела отпраздновать, как на отладчике заметила, что в функции Split_Text появляются артефакты. Не подскажете как можно это исправить?

Добавлено через 32 минуты
И из-за них, я так полагаю, бинарное дерево тоже строится неправильно
0
фрилансер
4171 / 3579 / 799
Регистрация: 11.10.2019
Сообщений: 9,633
09.06.2021, 09:32 8
zzppvvss, я не копался в коде, и сейчас немного занятый
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.06.2021, 09:32
Помогаю со студенческими работами здесь

Частотный словарь (на основе контейнера map)
Создать частотный словарь (на основе контейнера map) и реализовать такой функционал: - словарь...

Реализация многочлена (класс на основе списка, бинарного или сбалансированного дерева)
Здравствуйте! Скоро сдавать зачет и препод скорее всего попросит написать на листочке реализацию...

Составить частотный словарь на основе сообщения длинной не более 255 символов. Используя формулу Шеннона
1.Составить частотный словарь на основе сообщения длинной не более 255 символов. Используя формулу...

Задане:частотный словарь символов слогов их двух производных символов (см.частотный словарь слов)
Задане:частотный словарь символов слогов их двух производных символов (см.частотный словарь слов) ...

Словарь на основе бинарного дерева
Объясните, пожалуйста, что делает программа в функциях push и как осуществляется поиск, не совсем...

В чем разница идеально сбалансированного дерева и АВЛ дерева?
Добрый день, сам вопрос впринципе описан в заголовке. Перелазил большую часть интернета и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru