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

Построение дерева Хаффмана - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Класс рациональных дробей http://www.cyberforum.ru/cpp-beginners/thread454080.html
Написать пользоват. тип рациональных дробей. Внутреннее представление типа: int a, b; должно быть таким, что число a/b должно представлять собой несократимую дробь. Должно правильно выполняться: 1) создание объектов: Rational x = Rational(1, 3), y(1, 3); Rational n = 4; 2) присваивание w = q; 3) Арифметические операции n.Add(x); (к n прибавляем x)
C++ Куб числа Доброго времени суток, уважаемые форумчане) Нужно найти число, которое равняется кубу суммы всех своих цифр. Ну например: 512=(5+1+2)^3 Просьба, помочь) Бо в голове не укладывается как это сделать( уже заюзал цикл for все равно, не выходит( http://www.cyberforum.ru/cpp-beginners/thread454077.html
C++ Написать программу
Написать программу на языке C++, что получает у пользователя путь и имя каталога и осуществляет переход в заданный контекст.
В сберкассу на трехпроцентный вклад положили S рублей. Какой станет сумма вклада через N лет? C++
Здравствуйте,в общем как ни пытался "зашарить" все осталось безуспешным,поэтому пытаюсь обратится к Вам за помощью,и если не затруднит помочь решить пару задач С++ (компилятор GNU GCC) 8. В сберкассу на трехпроцентный вклад положили S рублей. Какой станет сумма вклада через N лет? 20. Написать программу, которая по заданным значениям чисел a и b находит ab. В запросе укажите допустимые...
C++ По данному натуральному числу N найдите сумму чисел http://www.cyberforum.ru/cpp-beginners/thread454058.html
По данному натуральному числу N найдите сумму чисел 1+1/1!+1/2!+1/3!+...+1/N!. Количество действий должно быть пропорционально N.
C++ В данном натуральном числе переставить цифры таким образом, чтобы образовалось наименьшее число, записанное этими цифрами 1)В данном натуральном числе переставить цифры таким образом, чтобы образовалось наименьшее число, записанное этими же цифрами. 2)Дано предложение. Найти наибольшее количество идущих подряд пробелов. 3)Дан одномерный массив целых чисел. Вставить число k впереди и после всех элементов, заканчивающихся на данную цифру k. 4)Дан упорядоченный по убыванию массив. Найти количество... подробнее

Показать сообщение отдельно
VladSharikov
 Аватар для VladSharikov
22 / 22 / 1
Регистрация: 02.12.2010
Сообщений: 824
27.02.2012, 23:45     Построение дерева Хаффмана
Привет! Есть проблемка. Здесь на форуме нашел темку про код Хаффмана, сейчас уже не буду искать скину отрезок кода.

Принцип Хаффмана(построение дерева): в левое поддерево помещается символ с самой большой частотой повторения, в правое остальные символы. На следующем шаге опять в левое поддерево помещается самый часто повторяющийся, в правое все остальное. При этом к коду левого поддерева добавляется 0, к коду правого 1.

Я не очень понимаю как здесь должны использоваться рекурсивные функции? кто-то может разобраться?

Вот построение дерева и построение кодов:
построение кодов
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void makeCodes(sym *root)
{
        if(root->left)
        {
                strcpy(root->left->code,root->code);
                strcat(root->left->code,"0");
                makeCodes(root->left);
        }
        if(root->right)
        {
                strcpy(root->right->code,root->code);
                strcat(root->right->code,"1");
                makeCodes(root->right);
        }
}
создание дерева хаффмана:
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
sym *makeTree(sym *psym[],int k)
{
        sym *temp;
        temp=(sym*)malloc(sizeof(sym));
        temp->freq=psym[k-1]->freq+psym[k-2]->freq;
        temp->code[0]=0;
        temp->left=psym[k-1];
        temp->right=psym[k-2];
 
        if(k==2)
                return temp;
        else //внесение в массив в нужное место элемента дерева Хофмана
        {
                for(int i=0;i<k;i++)
                        if (temp->freq>psym[i]->freq)
                        {       
                                for(int j=k-1;j>i;j--)
                                        psym[j]=psym[j-1];                                                                      
                                
                                psym[i]=temp;
                                break;
                        }               
        }
return makeTree(psym,k-1);
}
на всякий случай вот еще вывод(его я писал сам, может здесь что-то неправильно, потому криво выводит?

C++
1
2
3
4
5
6
7
8
9
10
    void outTree(sym *root, int step) {
        
        if(root != NULL) {
            outTree(root->left, step+1);
            for(int i = 1; i <= 2*step; i++) 
                cout << "\t";
            printf("%s\n", root->code);
            outTree(root->right, step+1);
        }
    }

Итак... На входе имеем строку символов: ACCCCCBBDACD
По хаффману должно получиться( от руки )
________ABCD
C_________________ABD
______________A________BD
_____________________B____D
А то что имеем
[IMG]http://s018.***********/i521/1202/5c/970787841d0d.png[/IMG]
Вторая ступень, макс. частота пошла не на ту сторону, направо а не налево, потому и код неправильно - например у буквы А должен быть 111, а он 011.

Не подскажете как поправить?

Добавлено через 1 час 42 минуты
Есть идеи?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru