Multimedia-Algorithms/dhuffman.cpp at master · ard1498/Multimedia-Algorithms · GitHub

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
#include<bits/stdc++.h>
using namespace std;

struct Node{
    char c;
    Node* left;
    Node* right;
    int freq;

    Node(char c1){
        left = NULL;
        right = NULL;
        c = c1;
        freq = 0;
    }

    Node(Node* L,Node* R){
        left = L;
        right = R;
        freq = L->freq + R->freq;
    }
};

struct compare{
    bool operator()(Node* a,Node* b){
        return a->freq < b->freq;
    }
};

void generatecode(Node* root,map<char,string> &table,string code){
    if(root->left != NULL){
        //code.push_back(0);

        generatecode(root->left,table,code+'0');
    }
    if(root->right != NULL){
        //code.push_back(1);
        generatecode(root->right,table,code+'1');
    }
    if(root->left == NULL && root->right == NULL){
        table[root->c] = code;
    }

    /*
    if(code.size()){
        code.pop_back();
    }*/
}

int main(){
    string s;
    cout<<"\nenter the string:";
    cin>>s;
    //vector<int> code;
    string code = "";
    map<char,string> table;
    map<int,int> nfreq;


    list<Node*> t;
    Node* r1 = new Node('$');
    r1->freq = 1;
    t.push_back(r1);

    for(int i = 0;i < s.size();i++){
        char cr = s[i];

        if(nfreq.find(cr) == nfreq.end()){
            cout<<"\ncur symbol is :"<<s[i];
            nfreq[cr]++;
            Node* nn = new Node(cr);
            nn->freq = nfreq[cr];
            t.push_back(nn);
            t.sort(compare());
        }

        else{
            for(auto itr = t.begin();itr != t.end();itr++){
                Node* cur = *itr;
                if(cur->c == cr){
                    cur->freq++;
                    nfreq[cr]++;
                    t.sort(compare());
                }
            }
        }

        list<Node*> tree = t;
        while(tree.size() > 1){
            tree.sort(compare());
            Node* l = tree.front();
            tree.pop_front();
            Node* r = tree.front();
            tree.pop_front();
            Node* nr = new Node('$');
            nr->freq = l->freq + r->freq;
            nr->left = l;
            nr->right = r;
            tree.push_front(nr);
        }

        Node* root = tree.back();
        generatecode(root,table,code);

        for(auto i = table.begin();i != table.end();i++){
            cout<<"\n"<<i->first<<"\t"<<i->second;
        }

        cout<<"\n";
    }

    return 0;
}