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

Код Хаффмана реализованный через построение бинарного дерева - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
daert
1 / 1 / 2
Регистрация: 09.05.2014
Сообщений: 41
09.05.2014, 19:18     Код Хаффмана реализованный через построение бинарного дерева #1
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого является элемент типа map ,либо символ и его вес, либо просто вес, если узел хранит только вес, значение его идентификатора берётся наверное стандартное символ номер -51 'Н', и проверка для вывода дерева не срабатывает, если же добавить условие на то что идентификатор не равен этому символу то в дереве выведется узел который появился ниоткуда (не из слияния 2-х символов как остальные узлы без букв а просто возник), т.е. символ 'Н' как бы не участвует в дереве и код ошибочный, преподователь обезательно придерётся к этому и не зачтёт курсовую работу ((
подскажите как обойти данную проблему

вот код
условие про которое я писал строка 62
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <fstream>
using namespace std;
 
class Node
{
    public:
     int a;
     char c;
     Node *left, *right;
     
     Node(){left=right=NULL;}
 
     Node(Node *L, Node *R) //конструктор принимающий 2 ссылки на левый и правый узлы нижестоящего уровня дерева
     {  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; // возвращает результат сравнения: вес левого узла меньше веса правого узла? если да то true, если нет то false
    }
};
 
 
vector<bool> code;// массив типа вектор (булевский массив )                
map<char,vector<bool> > table;// ассоциативный массив связывающий символ и его код     
 
void BuildTable(Node *root)
{   
    if (root->left!=NULL) // если у текущего узла существуют на нижестоящем уровне узлы которым не пренадлежит символ (т.е. не нижние узлы) то
                      { code.push_back(0);// текущему ребру дерева приравниваем 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();// удаляем последний элемент(цифру) кода символа 
}
 
void print (Node* root, unsigned k=0)
{
    if(root!=NULL)
    {
        print(root->left,k+3);//рекурсивно продвигаемся от корня к вершинам (от единственного узла верхнего уровня до узлов нижнего уровня), 
                            //к-отступ для вывода на экран
        for(unsigned i=0; i<k;i++) 
            cout<<"  ";
 
        if(root->c&&(int)(root->c)!=-51) cout<<root->a<<" ("<<root->c<<")"<<endl;// если у текущего узла есть буква (буквы принадлежат лиш верхним узлам дерева)выводим её вес и символ 
        else cout<<root->a<<endl; // выводим вес узла если ему не принадлежит буква
        print(root->right,k+3);
    }
}
 
int main (int argc, char *argv[])
{
    ifstream f("1.txt");
    setlocale(LC_ALL, "Russian");// преобразование ASCII таблицы сдвигом на 64 всех символов начиная с 128 символа
    map<char,int> m;// ассоциативный массив, позволяет использовать в качестве индексов любой тип данных, в данном случае чар, к примеру m[a]=1, m[b]=2
 
    ////// считаем частоты символов 
    while (!f.eof())// пока не дошли до конца файла выполнять
    { 
        char c = f.get(); // считываем символ из файла
        cout<<c;
        m[c]++;// увеличиваем счётчик встречаемости данного символа
    }
    
  
////// записываем начальные узлы в список list
                 
   list<Node*> t;// создаём лист указателей на Node (узлы дерева хаффмана)
   for( map<char,int>::iterator itr=m.begin(); itr!=m.end(); ++itr)// проходим по каждому элементу ассоциативного массива m
       // для этого типа данных необходимо использовать итератор для доступа к элементам массива, от начала массива и пока не дойдём до последнего элемента
   {  
      Node *p = new Node;// создаём динамический указатель на узел, 
      p->c = itr->first;// в переменную с, являющуюся частью выше созданного узла, 
                        //записываем  ключ доступа к текущему элементу, m[a]=1, в с запишется символ 'a'
      p->a = itr->second;  // в переменную a, являющуюся частью выше созданного узла, 
                            //записываем  данные из текущему элементу, m[a]=1, в a запишется число 1
      t.push_back(p);    // добавляем в лист указателей в конец новый элемент(указатель на узел)
   }    
    
 
//////  создаем дерево Хаффмана     
  while (t.size()!=1)// пока в списке не останется 1 элемент(узел) выполнять
  {  
     t.sort(MyCompare());// сортирую список узлов дерева по частоте встречаемости символа от наименьшей к наибольшей, MyCompare() - условие сортировки
    
     Node *SonL = t.front();// создаём указатель на 1-й узел (т.е. на узел с наименьшей частотой встречаемости)
     t.pop_front();// удаляем взятый узел
     Node *SonR = t.front(); // создаём указатель на 1-й узел (2-й до удаления 1-го узла)  
                        //(т.е. на узел с наименьшей частотой встречаемости в списке из которго был удалён 1-й элемент)
     t.pop_front();// удаляем взятый узел
     
     Node *parent = new Node(SonL,SonR); // создаём узел следующего уровня из 2-х узлов текущего уровня
     t.push_back(parent);// добавляем созданный узел в список (дерево)
  }
    
  //после цикла в списке t остался только 1 элемент, root указатель на данный элемент
    Node *root = t.front();   //root - указатель на вершину дерева
 
    cout<<"\n\n";
    print(root);// выводим на экран полученное дерево
    
 
    BuildTable(root);   // создаем пары 'символ-код':       
        
////// Выводим коды в файл output.txt
 
    f.clear(); // сбрасываем ошибки которые могли произойти при работе с файлом
    f.seekg(0); // перемещаем указатель снова в начало файла
    
    cout<<"\n\n";
    // вывод сжатого текста в виде полученных кодов симолов
    while (!f.eof())
    {
        char c;
        f>>c;
        vector<bool> x = table[c];
        for(unsigned n=0; n<x.size(); n++)
            cout<<x[n];
    }
 
 
    // вывод сиволов и их кодов
    cout<<"\n\n";
    ofstream g("res.txt");
    cout<<endl;
    g<<endl;
    g<<"\n\n";
    map<char,vector<bool> >::iterator ii;
    for(ii=table.begin();ii!=table.end();ii++)
    { char c1;
    c1=ii->first;
    vector<bool> x = table[c1];
    cout<<c1<<'\t';
    g<<c1<<'\t';
        for(unsigned n=0; n<x.size(); n++)
        {
            cout<<x[n];
            g<<x[n];
        }
        cout<<endl;
        g<<endl;
    }
    
    f.close();
    g.close(); 
    
 
    system("pause");
    return 0;
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.05.2014, 19:18     Код Хаффмана реализованный через построение бинарного дерева
Посмотрите здесь:

Построение бинарного дерева из двумерного массива C++
Построение бинарного дерева C++
Построение бинарного дерева из строки C++
C++ Вывод бинарного дерева
Построение бинарного дерева C++
C++ Обход дерева Хаффмана
C++ Построение бинарного дерева. Где ошибка?
Построение дерева в кодировании Хаффмана C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tuma
59 / 40 / 18
Регистрация: 28.09.2013
Сообщений: 186
10.05.2014, 19:50     Код Хаффмана реализованный через построение бинарного дерева #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
При заполнение дерева,если в узле будет храниться только вес,то значение c(вашего символа) нужно принудительно обнулять,иначе в нем будет храниться всякий мусор типа 'H'.И не забудьте при заполнение дерева обнулить значение символа,если его там нет,а то я не нашел где это у вас.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void print (Node* root, unsigned k=0)
{
    if(root!=NULL)
    {
        if (root->c==NULL)
        {
            for(int i = 0; i < k; i++)
                cout<<"  ";
            cout<< root->a << endl;
        } else
        {
            print(root->left,k+3);
            for(unsigned i=0; i<k;i++) 
                cout<<"  ";
            cout<<root->a<<" ("<<root->c<<")"<<endl;
            print(root->right,k+3);
        }
    }
}
Yandex
Объявления
10.05.2014, 19:50     Код Хаффмана реализованный через построение бинарного дерева
Ответ Создать тему
Опции темы

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