数据结构上机实验_树和二叉树的应用_哈夫曼编码设计 (含代码和报告).doc

数据结构实验报告 题目：数据结构实验报告 学院：工商管理学院 班级：信息1001 姓名：彭振宇 学号时间：2012/6/26实验三：树和二叉树的应用 实验题目：树和二叉树的应用 实验内容：哈夫曼编码设计 三．实验目的：掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内容。 四．实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。 五．概要设计原理： 1.选择parent为0且weight最小的两个结点。其序号分别为s1和s2 2.建立赫夫曼树叶 3.从叶子到根逆向求每个字符的赫夫曼编码 4.输出构造的树 5.输出得到的各权Huffman编码 六．详细程序清单及注释说明： #includestdio.h #includestdlib.h #includestring.h #define MAXSIZE 30 //最大叶子数 #define MAXCODE 10000 //编码最大长度 #define OK 1 #define ERROR 0 #define OVERLOW -2 //=============赫夫曼树和赫夫曼编码的存储表示===== typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; }HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表 /*----------------算法描述----------------*/ void Select(HuffmanTree HT, int n, int *s1, int *s2) //选择parent为0且weight最小的两个结点。其序号分别为s1和s2 { int minsum = 1000000; int i,j; for(i=1; i=n; i++) { if(HT[i].parent) continue; for(j=i+1; j=n; j++) { if(HT[j].parent) continue; if(HT[i].weight + HT[j].weight minsum) { minsum = HT[i].weight + HT[j].weight; *s1 = i; *s2 = j; } } } } void CreateHuffmanTree(HuffmanTree HT, int *w, int n) {//建立赫夫曼树叶 int m, s1, s2, i; if(n = 1) return; m = 2*n-1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); for( i = 1; i = n; i++, ++w) { HT[i].weight = *w; HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } for( ;i = m; ++i) { HT[i].weight = 0; HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } for(i = n+1; i = m; i++) {//在HT[1.i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2 Select(HT, i-1, s1, s2); HT[i].weight = HT[s1].weight + HT[s2].weight; HT[i].lchild = s1; HT[i].rchild = s2; HT[s1].parent = i; HT[s2].parent = i; } } void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n) {//从