课程设计构造哈夫曼树.doc

中国矿业大学徐海学院计算机系软件认知实践报告姓 名： 学 号： 专 业： 设计题目： 指导教师： 2013年12月目 录第1章 题目概述1第1.1节 题目要求1第1.2节 主要难点1第2章 系统流程图1第3章 数据结构和算法1第4章 核心代码分析1第5章 实验小结1参考文献1中国矿业大学徐海学院软件认知实践报告第1章 题目概述设计程序以实现构造哈夫曼树的哈夫曼算法 第1.1节 题目要求（1）可以使用实验工具的有关功能。（2）要能演示构造过程。（3）求解出所构造的哈夫曼树的带权路径长度。 第1.2节 主要难点(1)构造哈夫曼树：根据给定的权值构成二叉树集合，其中每棵二叉树中只有一个带权的根节点，其左右子树均为空；在二叉树集合中选取两棵根节点权值最小的树作为左右子树构造一棵新的二叉树，且新的二叉树的根节点的权值为其左、右子树上根节点的权值之和；在二叉树集合中删除这两棵树，并将得到的二叉树加入集合中；重复上述步骤，直至二叉树集合中只含一棵树为止。(2)求带权路径长度：先求每个叶子结点到树根之间的路径长度与该叶子结点所带权值之积，在将所得之积求和。第2章 系统流程图开始输出叶子结点个数n输入n个ASCII和权值引用pr()函数构建哈夫曼树引用pr()函数引用bm()函数从叶子到根逆向求书编码引用print（）函数引用dq()函数求带权路径长度输出带权路径长度结束结点1n与n+1m分别初始化输入初始状态图输入初始状态图输出哈夫曼编码第3章 数据结构和算法 使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。1.Init huffmantree(&T) 操作结果：构造一个已知结点和权值的huffmantree.2.Destory huffmantree(&T) 条件：huffmantree已经存在 结果：销毁huffmantree.3.huffman coding(&T) 条件：huffmantree已经存在 结果：输出huffman code.4.Visit huffmantree(&T) 条件：huffmantree已经存在 结果：显示 huffman tree.代码运行结果第4章 核心代码分析（1） 定义int s1=0,s2=0;/定义两个全局变量typedef struct/ 定义/结构体int c;/字符域 int w;/权值域int p,l,r;/双亲域/左孩子域右孩子域，HT,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char * *HuffmanCode;/动态分配数组存储赫夫曼编码HT *HTree;（2） 找出两个最小权值s1，s2void Select(HT *HTree,int b) int i,j,t; for(i=1;i=b;i+) if(!HTreei.p)s1 = i;break; for(j=i+1;j=b;j+) if(!HTreej.p)s2 = j;break; for(i=1;iHTreei.w)&(!HTreei.p)&(s2!=i)s1=i; for(j=1;j HTreej.w)&(!HTreej.p)&(s1!=j)s2=j; if(s1s2)/令s1小于s2 t=s1; s1=s2; s2=t; HuffmanCode HCode（3） 输出状态图void pr(HT *HTree,int m)int i;HT *h;printf(n输出状态图n字符t权值t双亲t左孩子t右孩子);h=HTree+1;for(i=1;ic,h-w,h-p,h-l,h-r);（4） 逐个字符求赫夫曼编码void Strcpy(char *p1,char *p2,int i,int j) int k; for(k=0;i=j;k+,i+)*(p1+k)=*(p2+i);（5） 逐个字符求赫夫曼编码void bm(HT *HTree,int n,char *code)int i,start,t,P;for(i=1;i=n;i+) start=n-1;/编码结束符位置for(t=i,P=HTreei.p;P!=0;t=P,P=HTreeP.p)/从叶子到根逆向求编码if (HTreeP.l=t)code-start=0;/左孩子编码为0else code-start=1;/有孩子编码为1 HCodei=(char *)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间Strcpy(HCodei,code,start,n-1);/把code占到hcode上（6） 输出赫夫曼编码函数void Print(HuffmanTree HTree,HuffmanCode HCode,int n) int i;for(i=1;i=n;i+)printf(%c-,HTreei.c); printf(%d-,HTreei.w); printf(%s,HCodei); printf(n);（7） 带权路径长度dq(HT *HTree,int n)int i,l,P,WPL;int wpl100;for(i=1;i=n;i+) for(l=0,P=HTreei.p;P!=0;P=HTreeP.p) l+=1;/l是路径个数wpli=HTreei.w*l; for(i=1,WPL=0;i=n;i+)WPL+=wpli;return WPL;（8） 主函数void main()int n,m,i,C,W,WPL;HT *h;printf(赫夫曼树应用！);printf(n输入叶子节点个数:);scanf(%d,&n);m=2*n-1; HTree=(HT *)malloc(m+1)*sizeof(HT);/0号单元未用,初始化赫夫曼树 h=HTree+1;printf(n输入%d个字符的Asc码(97-133)和权值:,n); /叶子结点初始化for(i=1;ic=C;h-w=W;h-p=0;h-l=0;h-r=0; /中间结点初始化 for(i=n+1;ic= ;h-w=0;h-p=0;h-l=0;h-r=0;printf(n初始n);pr(HTree,m);/输出初始状态图 /建赫夫曼树 for(i=n+1;i=m;i+) Select(HTree,i-1); HTrees1.p=i; HTrees2.p=i; HTreei.l=s1; HTreei.r=s2; HTreei.w=HTrees1.w+HTrees2.w;/输出终结状态图printf(n终结n);pr(HTree,m); /从叶子到根逆向求赫夫曼树编码 char *code; HCode=(HuffmanCode)malloc(n+1)*sizeof(char);/0号单元未用,分配n个字符编码的头指针向量 code=(char *)malloc(n*sizeof(char);/分配求编码的公用工作空间 coden-1=0;/编码结束符bm(HTree,n,code);printf(n赫夫曼编码为:n); Print(HTree,HCode,n);/带权路径长度 WPL=dq(HTree,n); printf(n带权路径长度:%dn,WPL);第5章 实验小结通过这一段时间的课程设计，我通过查找资料，仔细思考，运行修改，编出赫夫曼树应用这个程序。在编程序的过程中，也遇到了很多困难：检查没有错误却无法得出想要的结果，语句也和书上的一样却无法连接结点，又或是想达到