资源描述：
《哈弗曼树课程设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、09计算机课程设计哈夫曼编码/译码器（树的应用）09计算机科学与技术刘小青7一．题目哈弗曼树编码/译码（树的应用）二．目的1.巩固数据结构基础知识，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，从而提高分析问题、解决问题的能力，提高编程技能，培养理论结合实践的能力。2.熟练掌握数据结构的线性表、树、图等结构的应用的设计实现以及操作方法，为进一步的应用开发打好基础。3.培养查阅文献和撰写文档的能力。三．要求1.课程设计题目可从指导老师提供的题目列表中选择或自行提出。从实际情况出发选择工作量适当
2、、难度适中的题目。自选题目必须要得到指导老师的同意才能开题，否则不予承认，要求课题能够体现学生综合运用所学知识的能力。2.课程设计可参考已有的成果，但必须在功能、数据结构及算法上体现自己的独到之处。3.程序源代码和课程设计说明书必须按照相关要求和格式完成。四．题目设计分析：简述算法实现的过程。1.定义哈弗曼树。2.设计算法CrtHuffmanTree存放哈弗曼树的各个权值，建立哈弗曼树。3.设计算法CrtHuffmanCode从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码，即“密文”。4.设计算法TrsHuffmanTree求哈弗曼
3、编码对应的“明文”。5．设计main函数，利用以上函数实现建立哈弗曼函数、求编码和译文的目的。五．设计源代码#include#include#includetypedefchar*HuffmanCode;/*动态分配数组，存储哈夫曼编码*/typedefstruct{unsignedintweight;/*用来存放各个结点的权值*/unsignedintparent,LChild,RChild;/*指向双亲、孩子结点的指针*/}HTNode,*HuffmanTree;/*动态分配
4、数组，存储哈夫曼树*/voidselect(HuffmanTree*ht,intn,int*s1,int*s2){inti;intmin;for(i=1;i<=n;i++){7if((*ht)[i].parent==0){min=i;i=n+1;}}for(i=1;i<=n;i++){if((*ht)[i].parent==0){if((*ht)[i].weight<(*ht)[min].weight)min=i;}}*s1=min;for(i=1;i<=n;i++){if((*ht)[i].parent==0&&i!=(*s1)){m
5、in=i;i=n+1;}}for(i=1;i<=n;i++){if((*ht)[i].parent==0&&i!=(*s1)){if((*ht)[i].weight<(*ht)[min].weight)min=i;}}*s2=min;}voidCrtHuffmanTree(HuffmanTree*ht,int*w,intn){/*w存放已知的n个权值，构造哈夫曼树ht*/intm,i;ints1,s2;m=2*n-1;*ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));/*0号单元未使用*/for
6、(i=1;i<=n;i++){/*1-n号放叶子结点，初始化*/(*ht)[i].weight=w[i];(*ht)[i].LChild=0;7(*ht)[i].parent=0;(*ht)[i].RChild=0;}for(i=n+1;i<=m;i++){(*ht)[i].weight=0;(*ht)[i].LChild=0;(*ht)[i].parent=0;(*ht)[i].RChild=0;}/*非叶子结点初始化*//*------------初始化完毕！对应算法步骤1---------*/for(i=n+1;i<=m;i++)
7、/*创建非叶子结点,建哈夫曼树*/{/*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/select(ht,i-1,&s1,&s2);(*ht)[s1].parent=i;(*ht)[s2].parent=i;(*ht)[i].LChild=s1;(*ht)[i].RChild=s2;(*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;}}/*哈夫曼树建立完毕*/voidoutputHuffman(Huff
8、manTreeHT,intm){if(m!=0){printf("%d",HT[m].weight);outputHuffman(HT,HT[m].LChild);outputHuffman(HT,HT[m
