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

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

Войти
Регистрация
Восстановить пароль
 
Nukla
Сообщений: n/a
#1

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

03.04.2014, 10:28. Просмотров 1024. Ответов 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++ Кодирование Хаффмана
Сжатие Хаффмана C++
C++ Дерево Хаффмана
C++ Архиватор Хаффмана c++
C++ Код шеннон или хаффмана в dev c++

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

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

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

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