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

Код Хаффмана - C++

Восстановить пароль Регистрация
 
Nukla
Сообщений: n/a
03.04.2014, 10:28     Код Хаффмана #1
Всем доброго дня! имеется код хафманна, работает, но считает неправильно! кто может объяснить в чем дело?

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
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <fstream>
#include <string>
 
using namespace std;
 
class Node
{
    public:
     float a;
     char c;
     Node *left, *right;
 
     Node(){left=right=NULL;}
 
     Node(Node *L, Node *R)
     {  left =  L;
        right = R;
        a = L->a + R->a;  }
};
 
 
struct MyCompare
{
    bool operator()(const Node* l, const Node* r) const { return l->a < r->a; }
};
 
 
vector<bool> code;
map<char,vector<bool> > table;
 
void BuildTable(Node *root)
{
    if (root->left!=NULL)
                      { code.push_back(0);
                      BuildTable(root->left);}
 
    if (root->right!=NULL)
                       { code.push_back(1);
                       BuildTable(root->right);}
 
    if (root->c) table[root->c]=code;
 
    code.pop_back();
}
 
string Decode(string s,Node *p)
{
    int counter=0;
    string result="";
    Node *root= p;
 
    while(counter!=s.length())
    {
    if (s[counter]=='1') p=p->right; else p=p->left;
    if (p->left==NULL && p->right==NULL) {result=result+p->c; p=root;}
    counter++;
    }
    return result;
}
 
 
int main ()
{
////// считаем вероятности символов
 
    map<char,float> m;
    int count;
    cout << "How many characters? ";
    cin >> count;
 
    while (count)
    {
        cout << " Character :";
        char c;
        cin >> c;
        cout << "Probability:";
        cin >> m[c];
        count--;
    }
 
 
////// записываем начальные узлы в список list
 
   list<Node*> t;
   for( map<char,float>::iterator itr=m.begin(); itr!=m.end(); ++itr)
   {
      Node *p = new Node;
      p->c = itr->first;
      p->a = itr->second;
      t.push_back(p);      }
 
 
//////  создаем дерево
 
  while (t.size()!=1)
  {
     t.sort(MyCompare());
 
     Node *SonL = t.front();
     t.pop_front();
     Node *SonR = t.front();
     t.pop_front();
 
     Node *parent = new Node(SonL,SonR);
     t.push_back(parent);
 
  }
 
    Node *root = t.front();   //root - указатель на вершину дерева
 
////// создаем пары 'символ-код':
 
    BuildTable(root);
 
    cout << "====TABLE====" << endl;
    map<char,vector<bool> >::iterator ii;
    for(ii=table.begin(); ii!=table.end();ii++)
    {
        cout << "\n" << ii->first << "=";
        for(int i=0; i<table[ii->first].size();i++)
            cout << table[ii->first][i];
    }
    cout << "\n====TABLE====" << endl ;
    cout << "\nString for encode: ";
    string s;
    cin >> s;
 
    for(int i=0; i<s.length();i++)
    {
        vector<bool> x = table[ s[i] ];
        for(int n=0;n<x.size();n++)
            cout << x[n];
    }
 
    cout << "\nString for decode: ";
    cin >> s;
    cout << Decode(s, root);
 
    cin>>s;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2014, 10:28     Код Хаффмана
Посмотрите здесь:

C++ коды Фано, Хаффмана, Хэмминга, Шеннона, код с проверкой на четность
C++ Псевдоалгоритм Хаффмана
кодирование хаффмана C++
Алгоритм Хаффмана C++
модифицированный код Хаффмана. Сделать прогу C++
C++ Код Хаффмана реализованный через построение бинарного дерева
Сжатие Хаффмана C++
C++ Кодирование Хаффмана

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Catstail
Модератор
 Аватар для Catstail
21500 / 10253 / 1669
Регистрация: 12.02.2012
Сообщений: 17,139
03.04.2014, 11:10     Код Хаффмана #2
Цитата Сообщение от Nukla Посмотреть сообщение
имеется код хафманна
- Хаффмана
Цитата Сообщение от Nukla Посмотреть сообщение
работает, но считает неправильно
- т.е. не работает.

Беглый анализ не обнаруживает самого главного - выделения двух наибольших вероятностей при построении дерева кодирования. Ты код писал сам?
Yandex
Объявления
03.04.2014, 11:10     Код Хаффмана
Ответ Создать тему
Опции темы

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