该程序实现的功能是将一段字符串进行统计之后再进行huffman编码(二进制);
注意的地方:
1,huffman编码要用到贪心算法,所以用priority_queue可以在常量时间内取出和插入值。
2,静态建树:huffman树的节点表示方法采用了最多的变量,即父亲节点,左右子节点(因为程序中确实有这种需要,这里不同与二叉堆,无法通过在静态树(链表)的位置来确定其父亲节点和子节点);
1 #include<iostream>
2 #include<cstring>
3 #include<queue>
4 #include<cstdlib>
5 using namespace std;
6 const int MAXSIZE = 27;
7 class huffNode{
8 public:
9 int pr;
10 int lc , rc;
11 char s;
12 int pow;
13 bool operator < (const huffNode& b)const{
14 return pow > b.pow;
15 }
16 };
17 huffNode huff[MAXSIZE * 2];
18 string buf;
19 int count[26];
20 priority_queue<huffNode> greed;
21 //for the sake of convenience , assume that the
22 //standard input is from 'a' to 'z'.
23 int input(){
24 cout << "input the text!"<<endl;
25 cin >> buf;
26 for(int i = 0; i < 26 ; i++) count[i] = 0;
27 memset(huff , 0, sizeof(huff));
28 for(int i = 0; i < buf.length();i++)count[buf[i]-'a']++;
29 int len = 0;
30 for(int i = 0 ,j = 0; i < 26; i++)
31 if(count[i]){
32 huff[j].s = i + 'a';
33 huff[j].pow = count[i];
34 huff[j].pr = j;
35 cout << "the" << ' '<<'\''<< char(i+'a') <<'\''
36 <<' '<<"have arisen for " <<count[i]<<" time(s)"
37 <<endl;
38 greed.push(huff[j]);
39 len = j;
40 j++;
41 }
42 return len;
43 }
44
45 int createTree(int len){
46 if(len == 0) {
47 cout << " Only one kind of alf !"<<endl;
48 exit(1);
49 }
50 huffNode temp1 ,temp2,temp;
51 while(!greed.empty()){
52 temp1 = greed.top();
53 greed.pop();
54 temp2 = greed.top();
55 greed.pop();
56 len ++;
57 temp.lc = temp1.pr;
58 temp.rc = temp2.pr;
59 huff[temp1.pr].pr = huff[temp2.pr].pr = len;
60 temp.pr = len;
61 temp.pow = temp1.pow + temp2.pow;
62 huff[len] = temp;
63 if(!greed.empty()) greed.push(temp);
64 }
65 return len;
66 }
67
68 void reserve(char * a){
69 int len = strlen(a);
70 for(int i = 0 ; i <= len/2 ;i ++)
71 swap(a[i],a[len-i-1]);
72 }
73 struct code{
74 char s;
75 char co[50];
76 };
77
78 void coding(int len1,int len2){
79 code* mycode = new code[len1+1];
80 memset(mycode ,0 ,sizeof(mycode));
81 for(int i = 0; i <= len1 ; i++){
82 int j = i;
83 int t = 0;
84 mycode[i].s = huff[i].s;
85 while(j < len2){
86 if(huff[huff[j].pr].lc == j)
87 mycode[i].co[t++] = '0';
88 else mycode[i].co[t++] = '1';
89 j = huff[j].pr ;
90 }
91 reserve(mycode[i].co);
92 cout << "the code of " << mycode[i].s
93 << " is " << mycode[i].co <<endl;
94 }
95 delete[] mycode;
96 }
97
98 int main(){
99 int len1 = input();
100 int len2 = createTree(len1);
101 coding(len1,len2);
102 }
103
104
105
106