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

中华人民共和国矿业大学徐海学院计算机系软件认知实践报告姓 名： 学 号： 专 业： 设计题目： 指引教师： 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章 实验小结通过这一段时间课程设计，我通过查找资料，仔细思考，运营修改，编出赫夫曼树应用这个程序。在编程序过程中，也遇到了诸多困难：检查没有错误却无法得出想要成果，语句也和书上同样却无法连接结点，又或是想达到效果编不出来等等。这阐明咱们掌握知识不够完整，不够夯实，需要加深巩固。咱们一点点地摸索、求证、询问、查找，虽然尚有不完美地方，终于将程序完毕，也对树知识有了更深理解。这一周课程设计让我收获颇丰，也感谢教师平时上课辅导。参照文献严蔚敏 吴伟民编.数据构造（c语言版）. 清华大学出版社谭浩强编.C程序设计.清华大学出版社