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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Сосчитать автокорреляционную функцию между кодами, один из которых циклически сдвинут на k символов http://www.cyberforum.ru/cpp-beginners/thread1170936.html
Нужна помощь в реализации программы. Дано: скомпилированный с++ код. Необходимо сосчитать автокорреляционную функцию между ним и этим же кодом, но циклически сдвинутым на k символов. Для расчета использовать не байты, а типы инструкций. Понятно, что есть формула S(k) = ∑▒〖x(m)x(m+k)〗, но мне все равно не понятно, как быть в случае с кодом.
C++ Узнать файловое смещение переменной Как узнать файловое смещение переменной. Пробовал написать следующий код void main() { int a = 5; cout << hex << &a; system("pause"); }Вывело 18ff50. Пробовал при помощи PE Tools преобразовать в файловое смещение не получилось вывело out of range. Ребят если кто знает прошу помочь, очень надо http://www.cyberforum.ru/cpp-beginners/thread1170922.html
Факторизация методом Шнорра-Ленстры C++
Собственно курсач по этому методу. В рунете информации по нему практически нет, но нашёл в какой-то иностранной книге коротенький параграф с описанием алгоритма, перевёл. Вот он: Будем пытаться разделить N. Будем считать, что мы предварительно рассчитали р *…* р всех простых чисел до 1 . множество В ← , K ← 1, e ← . 2. пусть D = −KN if KN ≡ 3 (mod 4), D = −4KN иначе 3. Пусть ƒ_p...
Описать тип TDate — запись с полями целого типа Day (день), Month (месяц) и Year (год) — и функцию LeapYear(D) C++
Описать тип TDate — запись с полями целого типа Day (день), Month (месяц) и Year (год) — и функцию LeapYear(D) логического типа с параметром типа TDate, которая возвращает True, если год в дате D является високосным, и False в противном случае. Вывести значение функции LeapYear для пяти данных дат (предполагается, что все даты являются правильными). Високосным считается год, делящийся на 4, за...
C++ Разбитие массива на некое количество подмассивов одинаковой длинны http://www.cyberforum.ru/cpp-beginners/thread1170914.html
Здравствуйте. Для решения моей основной задачи требуется разбитие массива на некое количество подмассивов одинаковой длинны. Проблема в том, что конечный подмассив может быть заполнен не полностью, а ограничение на заполнение работает некорректно. Заранее спасибо. #include <iostream> #include <ctime> #include <iomanip> using namespace std;
C++ Как назвать переменную именем, введенным пользователем? Недавно начал изучать C++. Скажите пожалуйста, как назвать переменную значением из другой переменной? Вот код простой программы и как сделать чтобы она работала? #include <iostream> using namespace std; int main(){ char group; //Пусть имя состоит из одной буквы "x" cin>>group; int _ ; // " _ " Имя, вводимое пользователем; } подробнее

Показать сообщение отдельно
daert
1 / 1 / 2
Регистрация: 09.05.2014
Сообщений: 41
09.05.2014, 19:18     Код Хаффмана реализованный через построение бинарного дерева
Здравствуйте, есть код Хаффмана реализованный через построение бинарного дерева, узлами которого является элемент типа 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;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 04:26. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru