哈夫曼编译码器数据结构课程设计

1、课程设计(论文)题 目 名 称 哈夫曼编/译码器 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 指 导 教 师 2012年 12 月 23 日摘要随着计算机的普遍应用与日益发展, 其应用早已不局限于简单的数值 运算,而涉及到问题的分析,数据结构框架的设计以及设计最短路线等复 杂的非数值处理和操作.算法与数据结构的学习就是为以后利用计算机资 源高效地开发非数值处理的计算机程序打下坚实的理论, 方法和技术基础. 算法与数据结构旨在分析研究计算机加工的数据对象的特性,以便选 择适当的数据结构和存储结构,从而使建立在其上的解决问题的算法达到 最优. 数据结构是在整个计算机科学

2、与技术领域上广泛被使用的术语.它用 来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方 式构成,呈什么结构.数据结构有逻辑上的数据结构和物理上的数据结构 之分.逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据 结构反映成分数据在计算机内部的存储安排. 数据结构是数据存在的形式. 数据结构主要介绍一些最常用的数据结构,阐明各种数据结构内 在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算 时的实现算法,并对算法的效率进行简单的分析和讨论.数据结构是介于 数学,计算机软件和计算机硬件之间的一门计算机专业的核心课程,它是 计算机程序设计,数据库,操作系统,编译原

3、理及人工智能等的重要基础, 广泛的应用于信息学,系统工程等各种领域. 学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来 并对它们进行处理.通过课程设计可以提高学生的思维能力,促进学生的 综合应用能力和专业素质的提高。目 录1 问题描述12 需求分析13 概要设计231抽象数据类型定义232模块划分34 详细设计441数据类型的定义442主要模块的算法描述55 测试分析66 课程设计总结9参考文献9附录（源程序清单）101 问题描述 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来

4、的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。2 需求分析 一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码

5、进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据（1）数据一：已知某系统在通信联络中只可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。（2）用下表给出的字符集和频度的

6、实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”。字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811613 概要设计31抽象数据类型定义ADT Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：若D为空集，则称为空树。 若D仅为一个数据元素，则R为空集，否则R=H，H是如下的二元关系：（1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。（2）若D-root<>空集

7、，则存在一个划分D1，D2，···，Dm（m>0）。（3）对应于D-root的划分，H-<root，X1，···，<root，Xm>有唯一的一个划分H1，H2，···，Hm（m>0）。基本操作：InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T已存在。操作结果：树T被销毁。ClearTree(&T)初始条件：树T已存在。操作结果：将树T清为空栈。TreeEmpty(T)初始条件：树T已存在。操作结果：若树T为空，

8、则返回TRUE，否则FALSE。TreeDepth(T)初始条件:树T已存在。操作结果：返回T的深度。Root（T）初始条件：树T已存在。操作结果：返回树T的根。32模块划分本程序包括三个模块：（1）主程序模块void main()初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；（2）哈夫曼模块实现哈夫曼树的抽象数据类型（3）求哈夫曼编码模块实现求哈夫曼编码算法的数据类型4 详细设计41数据类型的定义（1）哈夫曼树类型typedef struct/构造树 char data;/结点权值 int weight;/权重 int parent;/双亲结点 int lchild;/左孩子 int

9、rchild;/右孩子 HTNode; HTNode ht30;（2）求哈夫曼编码类型typedef struct char cd30;/存放当前结点的哈弗曼编码 int start;/cdstartcdn存放哈弗曼码 HCode; HCode hcd30;42主要模块的算法描述Int I,f,c;i+Hc.start+;multiplexi=0hc.start=n;c=i;i<nf!=-1图4.3-2哈夫曼编码算法流程图Int i;scanf(“%d”,&htt.wei+i<n结束开始图4.3-1主函数流程图5 测试分析6 课程设计总结通过这次课程设计使我充分的理解了用哈

10、夫曼树再编码问题中基本原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码问题的程序。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点能力的程序，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到很茫然，无从下手。但是困难是可以解决的，只要通过努力，向老师虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才还有一个比较满意的成果。在此我非常要感谢的是我的指导老师黄同成教授，感

11、谢老师的细心认真的辅导，让我对数据结构这门课程有了跟深刻的认识，同时我还要感谢帮助过我的同学，没有他们的帮助我不肯能完成这样顺利，谢谢！参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，2008附录（源程序清单）#include<stdio.h>#define n 27 /叶子数目#define m (2*n-1) /结点总数#define maxval 10000.0#define maxsize 100 /哈夫曼编码的最大位数typedef struct char ch; float

12、 weight; int lchild,rchild,parent;hufmtree;typedef struct char bitsn; /位串 int start; /编码在位串中的起始位置 char ch; /字符codetype;void huffman(hufmtree tree);/建立哈夫曼树void huffmancode(codetype code,hufmtree tree);/根据哈夫曼树求出哈夫曼编码void decode(hufmtree tree);/依次读入字符，根据哈夫曼树译码void main() printf(" 哈夫曼编码n"); pr

13、intf("总共有%d个字符n",n); hufmtree treem; codetype coden; int i,j;/循环变量 huffman(tree);/建立哈夫曼树 huffmancode(code,tree);/根据哈夫曼树求出哈夫曼编码 printf("【输出每个字符的哈夫曼编码】n"); for(i=0;i<n;i+) printf("%c: ",codei.ch); for(j=codei.start;j<n;j+) printf("%c ",codei.bitsj); printf

14、("n"); printf("【读入字符，并进行译码】n"); decode(tree);/依次读入电文，根据哈夫曼树译码void huffman(hufmtree tree)/建立哈夫曼树 int i,j,p1,p2;/p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标 float small1,small2,f; char c; for(i=0;i<m;i+) /初始化 treei.parent=0; treei.lchild=-1; treei.rchild=-1; treei.weight=0.0; printf("【依

15、次读入前%d个结点的字符及权值(中间用空格隔开)】n",n); for(i=0;i<n;i+) /读入前n个结点的字符及权值 printf("输入第%d个字符为和权值",i+1); scanf("%c %f",&c,&f); getchar(); treei.ch=c; treei.weight=f; for(i=n;i<m;i+) /进行n-1次合并，产生n-1个新结点 p1=0;p2=0; small1=maxval;small2=maxval; /maxval是float类型的最大值 for(j=0;j<

16、i;j+) /选出两个权值最小的根结点 if(treej.parent=0) if(treej.weight<small1) small2=small1; /改变最小权、次小权及对应的位置 small1=treej.weight; p2=p1; p1=j; else if(treej.weight<small2) small2=treej.weight; /改变次小权及位置 p2=j; treep1.parent=i; treep2.parent=i; treei.lchild=p1; /最小权根结点是新结点的左孩子 treei.rchild=p2; /次小权根结点是新结点的右孩子

17、 treei.weight=treep1.weight+treep2.weight; /huffmanvoid huffmancode(codetype code,hufmtree tree)/根据哈夫曼树求出哈夫曼编码/codetype code为求出的哈夫曼编码/hufmtree tree为已知的哈夫曼树 int i,c,p; codetype cd; /缓冲变量 for(i=0;i<n;i+) cd.start=n; cd.ch=treei.ch; c=i; /从叶结点出发向上回溯 p=treei.parent; /treep是treei的双亲 while(p!=0) cd.sta

18、rt-; if(treep.lchild=c) cd.bitscd.start='0' /treei是左子树，生成代码'0' else cd.bitscd.start='1' /treei是右子树，生成代码'1' c=p; p=treep.parent; codei=cd; /第i+1个字符的编码存入codei /huffmancodevoid decode(hufmtree tree)/依次读入字符，根据哈夫曼树译码 int i,j=0; char bmaxsize; char endflag='2' /电文结束标志取2 i=m-1; /从根结点开始往下搜索 printf("输入发送的编码(以'2'为结束标志)："); gets(b); printf("译码后的字符为"); while(bj!='2') if(bj='0') i=treei.lchild; /走向左孩子 else i=treei.rchild; /走向右孩子 if(treei.lchild=-1) /treei是叶