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

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

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

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

03.04.2014, 10:28. Просмотров 1193. Ответов 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++
Каждому числу соответствует любое двоичное (специальная таблица пример 1 соответствует 00111, 2 соответствует 11 и так далее). При вводе...

Код шеннон или хаффмана в dev c++ - C++
всем добрый день; сможете помочь с кодом, надо написать код шеннон или хаффмана в dev c++, плиииз. по братский

Код Хаффмана реализованный через построение бинарного дерева - C++
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого является элемент типа map ,либо символ и...

Коды Фано, Хаффмана, Хэмминга, Шеннона, код с проверкой на четность - C++
Помогите пожалуйста!!!!!!очень срочно надо!!!:(:(нужно реализовать коды Фано,Хаффмана,Хэмминга((7,4),(8,4)),Шеннона,код с проверкой на...

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

Шифрование Хаффмана - C++
Ребята есть код шифрования Хаффмана, он почему-то пропускает букву Н. Помогите пожалуйста разобраться int main(int argc, char *argv) ...

кодировка Хаффмана - C++
Дорогие программисты. Вот был написан код &quot;кодировка Хаффмана&quot;, и тут мы вводим количество данных и их частоту. Но я не могу то ли...

Архиватор Хаффмана c++ - C++
Пишу архиватор на c++ методом Хаффмана. Не могу найти как считывать байты из файла в c++.

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

Сжатие Хаффмана - C++
Есть прога, реализующая сжатие Хаффмана: #include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;map&gt; #include...

Кодирование Хаффмана - C++
Добрый вечер. Я за эту неделю малость зафлудил форум наверно. Прошу прощения за это. Просто уже не знаю, куда ещё обратиться со всем...

Кодирование Хаффмана - C++
Есть дерево Хаффана, с помощью функции, приведенной ниже прохожусь по дереву и &quot;выписываю&quot; 0 и 1, получившиеся коды символов записываю в...


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

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

Беглый анализ не обнаруживает самого главного - выделения двух наибольших вероятностей при построении дерева кодирования. Ты код писал сам?
Ответ Создать тему
Опции темы

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