by

数据结构期末复习—Huffman

数据结构历来成为了备战各种考试的重中之重，无论是学校期末还是软考考数据结构终究离不开Huffman。最近期末复习到了二岔树这块，自我感觉还行吧，就当博文发了。Huffman是种带全路径长度最短的树，比较常用。完全二叉树就是这种路径最短的二叉树。树中的一个节点到另外一个节点的分支构成了两个节点间的路径，路径上面的分支数目称之为路径的长度。路径的长度是从树根到每一个节点的路径长度之和。

一般情况下，节点的带权路径长度为该节点到树根之间的路径长度乘以结点的权重（Quicl觉得数据结构就是现实生活在计算机的映射，比如权重为现实中的优先级云云）。数的带权路径为树中的所有叶子结点的带权路径长度总和。其中，带权路径长度最小的最小二叉树为最优二叉树或Huffman树。

构造Huffman树的方法：

  1. 根据实际应用时候的N个权重构成N棵二叉树的集合，其中每颗二叉树中只有一个唯一的根节点，其左右子树都为空。
  2. 在N棵二叉树的集合中取两颗根节点的权重最小的树为左右子树构造一空的新二叉树，并将新的二叉树根节点权值为左右子树+根结点权值之和。
  3. 在N棵二叉树中删除上述两颗二叉树，将新得到的二叉树加入其中。
  4. For Step 1、2 使得上述N棵二叉树中只有一棵树。
  5. End 至此已经建立好了一颗部长苹果的Huffman树

C语言实现代码如下

001 /*
002 * Tanky Woo
003 * Blog: www.WuTianQi.com
004 * Description: Huffman Tree
005 * Date: 2011.12.3
006 */
007 #include <iostream>
008 using namespace std;
009
010 int m, s1, s2; // m是总结点个数，s1,s2用于筛选出最小和第二小的两个数
011
012 typedef struct{
013     unsigned int weight;
014     unsigned int parent, lchild, rchild;
015 }HTNode, *HuffmanTree;   //动态分配数组存储哈夫曼树
016
017 typedef char* HuffmanCode;   //动态分配数组存储哈夫曼编码表
018
019 void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode);
020
021 int main()
022 {
023     HuffmanTree HT;   // 哈夫曼树
024     HuffmanCode *HC;  // 保存哈夫曼编码
025     int *w, nNode, i; // w记录权值
026     puts("输入结点数: ");
027     scanf("%d", &nNode);
028     HC = (HuffmanCode *) malloc (nNode* sizeof(HuffmanCode));
029     w = (int *) malloc (nNode * sizeof(int));
030     printf("输入 %d 个结点的权值\n", nNode);
031     for(i = 0; i < nNode; i++)
032         scanf("%d", &w[i]);
033     HuffmanCoding(HT, HC, w, nNode);
034     puts("\n各结点的哈夫曼编码:");  
035     for(i = 1; i <= nNode; i++)
036         printf("%2d(%4d):%s\n", i, w[i–1], HC[i]);
037     getchar();
038 }
039
040 //选出weight最小的两个结点,s1保存最小的，s2保存第二小的
041 void SelectMin(HuffmanTree HT, int nNode)
042 {
043     int i, j;
044     for(i = 1; i <= nNode; i++)
045         if(!HT[i].parent)
046         {
047             s1 = i;
048             break;
049         }
050     for(j = i+1; j <= nNode; j++)
051         if(!HT[j].parent)
052         {
053             s2 = j;
054             break;
055         }
056
057     for(i = 1; i <= nNode; i++)
058         if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i))
059             s1 = i;
060     for(j = 1; j <= nNode; j++)
061         if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j))
062             s2 = j;
063     // 以上只筛选出最小的两个，这里保证s1的weight比s2的小
064     if(HT[s1].weight > HT[s2].weight)
065     {
066         int tmp = s1;
067         s1 = s2;
068         s2 = tmp;
069     }
070 }
071
072 // w[]存放nNode个字符的权值（均大于0），构造哈夫曼树HT，
073 // 并求出nNode个字符的哈夫曼编码HC
074 void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode)
075 {
076     int i, j;
077     char *hfcode;
078     int p;
079     int cdlen;
080     if(nNode < 1)
081         return;
082     m = 2*nNode–1;   //哈夫曼树的结点数
083
084     /////////////////////////////以下是求Huffman树的初始化/////////////////////////////
085     HT = (HTNode*) malloc ((m+1) *sizeof(HTNode));  //0号单元未用
086     for(i = 1; i <= nNode; i++)    //初始化
087     {
088         HT[i].weight = w[i–1];
089         HT[i].parent = 0;
090         HT[i].lchild = 0;
091         HT[i].rchild = 0;
092     }
093     for(i = nNode+1; i <= m; i++)
094     {
095         HT[i].weight = 0;
096         HT[i].parent = 0;
097         HT[i].lchild = 0;
098         HT[i].rchild = 0;
099     }
100
101     puts("\n哈夫曼树的构造过程如下所示: ");
102     printf("HT初态:\n 结点 weight parent lchild rchild");
103     for(i = 1; i <= nNode; i++)
104         printf("\n%4d%8d%8d%8d%8d", i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
105
106     printf("按任意键,继续…");
107     getchar();
108
109     /////////////////////////////以下是求Huffman树的构建/////////////////////////////
110     for(i = nNode+1; i <= m; i++)
111     {
112         // 建立哈夫曼树
113         // 在HT[1..i-1]中选择parent为0且weight最小的两个节点
114         // 其序号分别是s1和s2
115         SelectMin(HT, i–1);
116         HT[s1].parent = i;
117         HT[s2].parent = i;
118         cout << "S1 && S2: " << HT[s1].weight << " " << HT[s2].weight << endl;
119         HT[i].lchild = s1;
120         HT[i].rchild = s2;
121         HT[i].weight = HT[s1].weight + HT[s2].weight;
122         printf("\nselect: s1 = %d s2 = %d\n", s1, s2);
123         printf("结点 weight parent lchild rchild");
124         for(j = 1; j <= i; j++)
125             printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild);
126         printf("按任意键,继续…");
127         getchar();
128     }
129
130
131     /////////////////////////////以下是求Huffman树的编码/////////////////////////////
132     // 可以看看算法导论上对于DFS求路径的方法，分三色：白，灰，黑，这里weight=0,1,2和那里思想是类似的
133     // 可以拿7,5,2,4这组数据来模拟下面的过程，以求更简单理解
134     // 从根出发
135     //递归遍历哈夫曼树,求哈夫曼编码
136     hfcode = (char *) malloc (nNode * sizeof(char));   //分配求编码的工作空间
137     p = m;
138     cdlen = 0;
139     for(i = 1; i <= m; i++)
140         HT[i].weight = 0;   //遍历哈夫曼树时用作结点状态的标志
141
142     while(p)        //退出条件：p = 结点m的parent,即为0
143     {
144         if(HT[p].weight == 0)   //向左
145         {
146             HT[p].weight = 1;
147             if(HT[p].lchild != 0)
148             {
149                 p = HT[p].lchild;
150                 hfcode[cdlen++] = ‘0’;
151             }
152             else if(HT[p].rchild == 0)
153             {
154                 HC[p] = (char *) malloc ((cdlen+1) * sizeof(char));
155                 hfcode[cdlen] = ‘\0’;   //保证后面的不会被复制
156                 strcpy(HC[p], hfcode);   //复制编码
157             }
158         }
159         else if(HT[p].weight == 1)   //向右
160         {
161             HT[p].weight = 2;
162             if(HT[p].rchild != 0)
163             {
164                 p = HT[p].rchild;
165                 hfcode[cdlen++] = ‘1’;
166             }
167         }
168         else
169         {
170             // HT[p].weight == 2 退回到父结点，编码长度减一
171             HT[p].weight = 0;
172             p = HT[p].parent;
173             —cdlen;
174         }
175     }
176 }

 

这几天，天气转冷，身体很不舒服，感觉做什么都力不从心。甚至前天晚上不敢睡觉，生怕出了什么意外。昨天出去买了些药，以及帽子。看来再也不可以像以前那样单薄过冬了……寒假需要备考明年的软考还有学习CSS+DIV，以及老生常谈的英语。希望自己可以顺利的过完这个冬天。打了这么多年的CS，最近听到Taking Fire , Need Assistance .格外亲切，是的，Taking Fire , Need Assistance ！