数据结构 实验三.doc

《数据结构 实验三.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、华北水利水电学院数据结构实验报告2010～2011学年第二学期08级通信专业实验三树的应用一、实验目的：1．进一步掌握树的结构及非线性特点，递归特点和动态性。2．进一步巩固对指针的使用和二叉树的建立方法。3．熟练掌握建立哈夫曼树及求哈夫曼编码的算法。二、实验内容：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出每个字符及对应的哈夫曼编码。三、实验要求：1．C/C++完成算法设计和程序设计并上机调试通过。2．撰写实验报告，提供实验结果和数据。3．写出算法设计小结和心得。四、程序源代码

2、：#include#include#include#include#include#defineMAXVALUE10000#defineMAXLEAF30#defineMAXNODEMAXLEAF*2-1#defineMAXBIT50typedefstructnode/*结点类型定义*/{charletter;intweight;intparent;intlchild;intrchild;}HNodeType;typedefstruct/*编码类型定义*/{ch

3、arletter;intbit[MAXBIT];intstart;}HCodeType;typedefstruct/*输入符号的类型*/{chars;intnum;}lable;voidHuffmanTree(HNodeTypeHuffNode[],intn,lablea[]){inti,j,m1,m2,x1,x2,temp1;chartemp2;for(i=0;i<2*n-1;i++)/*结点初始化*/{HuffNode[i].letter=0;HuffNode[i].weight=0;HuffNode[i].parent=-1;HuffNode[i].lc

4、hild=-1;HuffNode[i].rchild=-1;}for(i=0;ia[i].num){temp1=a[i].num;a[i].num=a[j].num;a[j].num=temp1;temp2=a[i].s;a[i].s=a[j].s;a[j].s=temp2;}for(i=0;i

5、/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;j

6、ht=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}}voidHuffmanCode(intn,lablea[]){HNodeTypeHuffNode[MAXNODE];HCodeTypeHuffCode[MAXLEAF],cd;inti,j,c,p;HuffmanTree(HuffNode,n,a);for(i=0;i

7、nt;while(p!=-1){if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HuffNode[c].parent;}for(j=cd.start+1;j

8、de[i].letter);for(j