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

Алгоритм Хаффмана, реализация через структуры - C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
RealShady911
Сообщений: n/a
16.12.2012, 16:02     Алгоритм Хаффмана, реализация через структуры #1
Добрый день, помогите пожалуйста найти ошибку в построении кодов Хаффмана.

использую следующие структуры:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct haffman
{
char Sim;
int Freq; 
char Code[32]; 
};
 
struct node
{
int Summ;
int Pos;
int Step;
int Num;
char Sim;
 
};
Собственно сам алгоритм построения:

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
int qwon;
int st1, st2;
int sum;
int i;
int k = 0;
int intswap;
 
qwon = qwontaty - 1;
 
while (HAF[0].Freq > NOD[qwon].Summ)
{
      
 for(i = qwontaty - 1; i >= 0;  i--) //сортировка по частоте встречаемости
 for(int j = 0; j < qwontaty; j++)
 if (NOD[i].Summ > NOD[j].Summ)
 {
 swaps = NOD[i];
 NOD[i] = NOD[j];
 NOD[j] = swaps; 
 }
 
    
for(i = 0; i <= NOD[qwon].Step; i++)
HAF[qwon - i].Code[NOD[qwon - i].Pos] = '0';      //Step показывает на сколько элементов применять команду
                                                  //в данном случае приписать 0;
 
for(i = (NOD[qwon].Step + 1); i <= NOD[qwon].Step + NOD[qwon - 1].Step + 1; i++)
HAF[qwon - i].Code[NOD[qwon - i].Pos] = '1';      //приписать 1;
 
for(i = 0; i <= NOD[qwon].Step; i++)
NOD[qwon - i].Pos++;                              //прибавить 1 к позиции символа кодового слова
 
for(i = (NOD[qwon].Step + 1); i <= NOD[qwon].Step + NOD[qwon - 1].Step + 1; i++)
NOD[qwon - i].Pos++;                              //прибавить 1 к позиции символа кодового слова
 
st1 = NOD[qwon].Step;
st2 = NOD[qwon].Step + NOD[qwon - 1].Step + 1;    //запись шага в отельную переменную
 
for (i = 0; i <= st1; i++)                        
NOD[qwon - i].Step++;                             //прибавить 1 к шагу
for (i = st1 + 1 ; i <= st2; i++)
NOD[qwon - i].Step++;                             //прибавить 1 к шагу
 
NOD[qwon].Summ = 0;
 
for (i = 0; i <= (st1 + st2); i++)
NOD[qwon].Summ = NOD[qwon].Summ + HAF[NOD[qwon - i].Num].Freq; //подсчет суммы элементов входящих в узел Хаффмана
}
Вложения
Тип файла: txt исходный код.txt (4.0 Кб, 20 просмотров)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2012, 16:02     Алгоритм Хаффмана, реализация через структуры
Посмотрите здесь:

C++ Алгоритм Хаффмана
Алгоритм Хаффмана C++
Поиск наименьших двух элементов массива или алгоритм Хаффмана C++
C++ Алгоритм Хаффмана
C++ Код Хаффмана реализованный через построение бинарного дерева
Потеря нулевых байт при архивации (алгоритм Хаффмана) C++
C++ Алгоритм Хаффмана
C++ Канонический алгоритм Хаффмана
Алгоритм Хаффмана с записью в файл C++
C++ Реализовать алгоритм оптимального кодирования Хаффмана
C++ Реализация алгоритма Хаффмана с использованием классов
C++ Оптимизация расшифровки файла | алгоритм хаффмана

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RealShady911
Сообщений: n/a
16.12.2012, 23:09     Алгоритм Хаффмана, реализация через структуры #2
Немного поделал еще, стало выходить более толково, но опять же явная ошибка, потому что сжатое сообщение превышало бы изначальное в объеме раз так в 15 )))
Если кто найдет косяк буду очень благодарен, а то я уже запарился совсем.

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
haffman m1, m2;
 
m1 = HAF[0];
m2 = HAF[0];
 
for (int i = 0; i < 256; i++)
if (m1.Freq >= HAF[i].Freq)
m1 = HAF[i];
 
for (int i = 0; i < 256; i++)
if (m2.Freq >= HAF[i].Freq)
if (HAF[i].Num != m1.Num)
m2 = HAF[i];
 
HAFFMAN:
 
for (int i = 0; i <= m1.Pos; i++)
{
HAF[m1.Num - i].Code[HAF[m1.Num - i].Pos] = '0';
HAF[m1.Num - i].Pos++;
}
 
for (int i = 0; i <= (m2.Pos); i++)
{
HAF[m2.Num - i].Code[HAF[m2.Num - i].Pos] = '1';
HAF[m2.Num - i].Pos++;    
}
 
for (int i = 0; i <= m1.Pos; i++)
HAF[m1.Num - i].Freq = HAF[m1.Num - i].FreqStatic;
 
for (int i = 0; i <= m2.Pos; i++)
HAF[m2.Num - i].Freq = HAF[m2.Num - i].FreqStatic;
 
int i = 1;
 
while (i <= (m1.Pos))
{
HAF[m1.Num].Freq = HAF[m1.Num].Freq + HAF[m1.Num - i].Freq;
i++;
}
 
i = 1;
 
while (i <= m2.Pos)
{
HAF[m2.Num].Freq = HAF[m2.Num].Freq + HAF[m2.Num - i].Freq;
i++;
}
 
HAF[m1.Num].Freq = HAF[m1.Num].Freq + HAF[m2.Num].Freq;
HAF[m2.Num].Freq = HAF[m1.Num].Freq;
 
i = 1;
 
while (i <= (m1.Pos))
{
HAF[m1.Num - i].Freq = HAF[m1.Num].Freq;
i++;
}
 
i = 1;
 
while (i <= m2.Pos)
{
HAF[m2.Num - i].Freq = HAF[m2.Num].Freq;
i++;
}
 
m1.Freq = HAF[m1.Num].Freq;
m2.Freq = HAF[m2.Num].Freq;
 
for (int i = 0; i < 256; i++)
if (m1.Freq >= HAF[i].Freq)
m1 = HAF[i];
 
for (int i = 0; i < 256; i++)
if (m2.Freq >= HAF[i].Freq)
if (HAF[i].Num != m1.Num)
m2 = HAF[i];
 
if (size > (m1.Freq + m2.Freq))
 
goto HAFFMAN;
Yandex
Объявления
16.12.2012, 23:09     Алгоритм Хаффмана, реализация через структуры
Ответ Создать тему
Опции темы

Текущее время: 09:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru