资源描述：
《课程设计：实现构造哈夫曼树的哈夫曼算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、中国矿业大学徐海学院计算机系《软件认知实践》报告姓名：学号：专业：设计题目：指导教师：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)求带权路径长度：先求每个叶子结点到树根之间的路径长度与该叶子结点所带权值之积，在将所得之积求和。10中国矿业大学徐海学院《软件认知实践》报告第2章系统流程图开始输出叶子结点个数n输入n个ASCII和权值引用pr()函数构建哈夫曼树引用pr()函数引用bm()函数从叶子到根逆向求书编码引用print（）函数引用dq()函数求带权路径长度输出带权路径长度结束结点1~n与n+1~
3、m分别初始化输入初始状态图输入初始状态图输出哈夫曼编码10中国矿业大学徐海学院《软件认知实践》报告第3章数据结构和算法使用树TREE的结构，编造最优二叉树（即哈夫曼树），涉及到主要函数有Inithuffmantree,Destoryhuffmantree,huffmancodeing,Visithuffmantree等，用于在一定时间复杂度内寻找到最佳（最短）路径，节约比较次数。1.Inithuffmantree(&T)操作结果：构造一个已知结点和权值的huffmantree.2.Destoryhuffmantree(&T)条件：huffmantree已经存在结果：销毁huffmantree.
4、3.huffmancoding(&T)条件：huffmantree已经存在结果：输出huffmancode.4.Visithuffmantree(&T)条件：huffmantree已经存在结果：显示huffmantree.代码运行结果10中国矿业大学徐海学院《软件认知实践》报告10中国矿业大学徐海学院《软件认知实践》报告第4章核心代码分析（1）定义ints1=0,s2=0;//定义两个全局变量typedefstruct//定义/结构体{intc;//字符域intw;//权值域intp,l,r;/双亲域/左孩子域右孩子域，}HT,*HuffmanTree;//动态分配数组存储赫夫曼树typede
5、fchar**HuffmanCode;//动态分配数组存储赫夫曼编码HT*HTree;（2）找出两个最小权值s1，s2voidSelect(HT*HTree,intb){inti,j,t;for(i=1;i<=b;i++)if(!HTree[i].p){s1=i;break;}for(j=i+1;j<=b;j++)if(!HTree[j].p){s2=j;break;}for(i=1;i<=b;i++)if((HTree[s1].w>HTree[i].w)&&(!HTree[i].p)&&(s2!=i))s1=i;for(j=1;j<=b;j++)if((HTree[s2].w>HTree[j
6、].w)&&(!HTree[j].p)&&(s1!=j))s2=j;if(s1>s2)//令s1小于s210中国矿业大学徐海学院《软件认知实践》报告{t=s1;s1=s2;s2=t;}}HuffmanCodeHCode（3）输出状态图voidpr(HT*HTree,intm){inti;HT*h;printf("输出状态图字符t权值t双亲t左孩子t右孩子");h=HTree+1;for(i=1;i<=m;i++,h++){printf("%ct%dt%dt%dt%d",h->c,h->w,h->p,h->l,h->r);}（4）逐个字符求赫夫曼编码voidStrcp
7、y(char*p1,char*p2,inti,intj){intk;for(k=0;i<=j;k++,i++)*(p1+k)=*(p2+i);}（5）逐个字符求赫夫曼编码voidbm(HT*HTree,intn,char*code){inti,start,t,P;for(i=1;i<=n;i++){start=n-1;//编码结束符位置for(t=i,P=HTree[i].p;P!=0;t=P,P
