По
этому уроку пытаюсь написать функцию генерации дерева Хаффмана. Считывание, получение алфавита и частот реализовал, все работает. Но вот с деревом встал в тупик.
Вот код:
...
struct SYM // представление символа
{
unsigned char ch; // ASCII-код
float freq; // частота встречаемости
char code[256]; // массив для нового кода
struct SYM *left; // левый потомок в дереве
struct SYM *right; // правый потомок в дереве
};
...
struct SYM* buildTree(struct SYM *psym[], int N)
{
// создаём временный узел
struct SYM *temp = (struct SYM*)malloc(sizeof(struct SYM));
// в поле частоты записывается сумма частот
// последнего и предпоследнего элементов массива psym
temp->freq = psym[N - 2]->freq + psym[N - 1]->freq;
// связываем созданный узел с двумя последними узлами
temp->left = psym[N - 1];
temp->right = psym[N - 2];
temp->code[0] = '\0';
if (N == 2) // мы сформировали корневой элемент с частотой 1.0
return temp;
for (int i = 0; i < N; i++)
if (temp->freq>psym[i]->freq)
{
for (int j = N - 1; j>i; j--)
psym[j] = psym[j - 1];
psym[i] = temp;
break;
}
return buildTree(psym, N - 1);
}
void makeCodes(struct SYM *root)
{
if (root->left)
{
strcpy(root->left->code, root->code);
strcat(root->left->code, "12");
makeCodes(root->left);
}
if (root->right)
{
strcpy(root->right->code, root->code);
strcat(root->right->code, "45");
makeCodes(root->right);
}
}
void division(struct alphabet *alphabetLetter, int groupCount)
{
int psysms[256];
struct SYM str[256];
for (int i = 0; i < alphabetLen; i++) {
// Пысы: в массиве структур alphabetLetter как раз находится наш алфавит, с
частотами
psysms[i] = &alphabetLetter[i];
str[i].ch = alphabetLetter[i].letter;
str[i].code[0] = '\0';
str[i].freq = alphabetLetter[i].probability;
str[i].left = NULL;
str[i].right = NULL;
}
struct SYM *root = buildTree(psysms, alphabetLen);
makeCodes(root);
}
...
int main() {
division(alphabetLetter, alphabetLen); // alphabetLetter - массив структур алфавита (символ, частота, код)
}
При компиляции выдает ошибку:
Методом научного тыка понял что процедура makeCodes выполняется больше раз, чем нужно, видимо проверки if (root->left) и if (root->right) не работают.
Чего я только не перепробовал, какие только проверки не сооружал, все равно процедура выполняется больше нужного количества раз.
Заранее спасибо за помощь
Простой
