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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
RealShady911
Сообщений: n/a
#1

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

16.12.2012, 16:02. Просмотров 1275. Ответов 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 Кб, 21 просмотров)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.12.2012, 16:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Хаффмана, реализация через структуры (C++):

Реализация алгоритма Хаффмана с использованием классов - C++
Всем привет. Пишу Алгоритм Хаффмана. Хочу сделать все красиво в классах,но как-то не додумываюсь. Пытался сделать чтение файла методом,но...

Алгоритм Хаффмана - C++
Ребят, подскажите как реализовать кодирование по алгоритму Хаффмана.. Может есть какие то идеи или исходники (желательно с пояснением)? ...

Алгоритм Хаффмана - C++
Доброго времени суток, пишу сюда, так как отчаялся найти ошибку сам. Собственно проблема состоит в непонимании где я допустил ошибку....

Алгоритм Хаффмана - C++
Решил разобраться с этим алгоритмом, собственно он состоит из нескольких из таких шагов: 1) Создать массив со всеми символами. 2)...

Алгоритм Хаффмана - C++
Возможно и наболевшая тема на форуме, но всё же есть реализация алгоритма Хаффмана. Допустим, у меня в файле есть следующая строка: ...

Канонический алгоритм Хаффмана - C++
Здравствуйте! Нужен пример программы в которой реализован канонический алгоритм Хаффмана. Очень прошу помочь. Может у вас есть готовый...

1
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;
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.12.2012, 23:09
Привет! Вот еще темы с ответами:

Алгоритм Хаффмана с записью в файл - C++
Коды Хаффмана (сжатие информации). Реализовать процедуры кодирования и декодирования согласно алгоритму Хаффмана. а)На вход процедуры...

Реализовать алгоритм оптимального кодирования Хаффмана - C++
Добрый день! Нужно реализовать алгоритма Хаффмана. Помогите, пожалуйста.

Оптимизация расшифровки файла | алгоритм хаффмана - C++
Привет, форумчани! Собственно сразу к вопросу. У меня имеется зашифрованный файл весом 390 КБ и считывание (расшифровка) в режиме debug ...

Потеря нулевых байт при архивации (алгоритм Хаффмана) - C++
Неправильно архивирует pdf файлы Как мне сказали вся ошибка в функции BuildTable &quot;Вместо условия проверки отсутствия символа,...


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

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

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