哈夫曼樹和哈弗曼編碼小記

原本是資料結構課的作業……到後來沒查，放着占記憶體，删了有點浪費，幹脆扔在部落格上吧……

1 #include<cstdio>
 2 #include<iostream>
 3 #include<queue>
 4 #include<vector>
 5 #include<stack>
 6 #define maxn 10000+5
 7 using namespace std;
 8 
 9 int n;
10 struct Node{
11     int num;//節點編号 
12     int lchild,rchild,parent;//節點的父節點、左子節點、右子節點 
13     char c;
14     int freq;//字母出現的頻率 
15     bool operator<(const Node &oth)const
16     {
17         return freq>oth.freq;
18     }//重定義小于号運算符，使得結構體之間可以進行大小比較 
19 }node[maxn];
20 
21 int main()
22 {
23     while(scanf("%d",&n)!=EOF)
24     {
25         priority_queue<Node> q;
26         for(int i=1;i<=n;i++)//輸入
27         {
28             cin>>node[i].c>>node[i].freq;
29             node[i].num=i;
30             node[i].lchild=0;
31             node[i].rchild=0;
32             node[i].parent=0;
33             q.push(node[i]);
34         }
35         for(int i=n+1;i<=2*n-1;i++)//建樹 
36         {
37             Node x,y;
38             x=q.top(); q.pop();
39             y=q.top(); q.pop();
40             
41             node[x.num].parent=i;
42             node[y.num].parent=i; 
43             
44             node[i].num=i;
45             node[i].lchild=x.num;
46             node[i].rchild=y.num;
47             node[i].parent=0;
48             node[i].freq=x.freq+y.freq;
49             node[i].c='\0';
50             
51             q.push(node[i]);
52         }
53         printf("哈夫曼樹：\n"); 
54         for(int i=1;i<=2*n-1;i++)
55         {
56             printf("node %d: p=%d \t lc=%d \t rc=%d \t c=%c \t freq=%d\n",node[i].num,node[i].parent,node[i].lchild,node[i].rchild,node[i].c,node[i].freq);
57         }
58         printf("哈夫曼編碼：\n"); 
59         for(int i=1;i<=n;i++)//輸出 
60         {
61             stack<bool> output;
62             Node now=node[i];
63             while(now.parent!=0)
64             {
65                 if(now.num == node[now.parent].lchild)//目前節點是其父節點的左子節點 
66                     output.push(0);
67                 else                                //目前節點是其父節點的右子節點
68                     output.push(1);
69                 now=node[now.parent];
70             }
71             printf("%c : ",node[i].c);
72             while(!output.empty())
73             {
74                 printf("%d",output.top());
75                 output.pop();
76             }
77             printf("\n");
78         } 
79     }
80 }
81 
82 /*
83 測試資料：
84 6
85 f 5
86 e 9
87 c 12
88 b 13
89 d 16
90 a 45
91 */