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

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

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

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

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

Модифицированный код Хаффмана - C++
Каждому числу соответствует любое двоичное (специальная таблица пример 1 соответствует 00111, 2 соответствует 11 и так далее). При вводе...

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

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

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

Дерево Хаффмана - C++
Здравствуйте. Хотел узнать как работает дерево Хаффмана и 4 дня изучал материалы в интернете (статьи, видеоуроки) и т.д.), написал...

Метод Хаффмана - C++
Есть метод Хаффмана, но при выполнение в кодировании где-то добавляються переносы строк и из-за этого происходит неправильная кодировка. ...

1
Catstail
Модератор
23500 / 11608 / 1894
Регистрация: 12.02.2012
Сообщений: 18,949
03.04.2014, 11:10 #2
Цитата Сообщение от Nukla Посмотреть сообщение
имеется код хафманна
- Хаффмана
Цитата Сообщение от Nukla Посмотреть сообщение
работает, но считает неправильно
- т.е. не работает.

Беглый анализ не обнаруживает самого главного - выделения двух наибольших вероятностей при построении дерева кодирования. Ты код писал сам?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.04.2014, 11:10
Привет! Вот еще темы с ответами:

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

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

Сжатие Хаффмана - C++
Как изменить данный алгоритм, чтобы ограничить длину кода символа заданным числом Nmax? Спасибо! #include &quot;stdafx.h&quot; #include...

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


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

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

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