数据结构课程设计--哈夫曼编码.doc

课 程 设 计 报 告课程名称 数据结构 课题名称 哈夫曼编码与译码 专 业 通信工程 班 级 学 号 姓 名 指导教师 田娟秀、李杰君、张鏖烽 2011年 07 月 01日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 哈夫曼编码与译码 专业班级 学生姓名 学 号 指导老师 审 批 任务书下达日期 2011 年 06 月 27 日 任务完成日期 2011 年 07 月 01 日1设计内容与设计要求1.1设计内容课题五：对电文中的字符串编码和译码Huffman编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景，是数据压缩中的一个重要理论依据。对输入的一串文字符号实现Huffman编码，再对Huffman编码生成的代码串进行译码，输出电文字符串。要求完成以下功能：a) 针对给定的字符串，建立Huffman树。b) 生成Huffman编码。c) 对编码文件译码。1.2 选题方案：所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9，则所选题目号为：9%6+1（题目4）。注意，所有的课题都要求用图形方式演示步骤和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。1.3设计要求：1.3.1 课程设计报告规范（1）需求分析a.程序的功能。b.输入输出的要求。（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a.采用C语言定义相关的数据类型。b 写出各模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录源程序清单（带注释）1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.3.3 课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2 进度安排第 19 周：星期一 8：0012：00 上课 星期一 14：3018：30 上机星期二 14：3018：30 上机 星期四 8：0012：00 上机 附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在4500字以上（不含程序原代码）。 目录一.需求分析11.程序的功能12.输入输出的要求1二.概要设计11.程序模块及其关系12.课题涉及的数据结构2三.详细设计31.相关数据类型32.各函数的调用关系图、主要函数的流程图33.各模块的类C码算法7四.调试分析以及设计体会91.测试数据92.程序调试中遇到的问题以及解决问题的方法103.课程设计过程经验教训、心得体会10五.用户使用手册11六.附录12一. 需求分析1.程序的功能能对输入的字符串实现Huffman编码，且能利用生成的编码对Huffman代码串进行译码，输出相应字符串。2.输入输出的要求首先，输入一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的次数，然后输出通过Huffman编码得到的各种字符的Huffman编码。此时程序要求输入一串Huffman代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出译码结果。二. 概要设计1.程序模块及其关系主函数模块编码模块译码模块输入字符串构造哈夫曼树生成哈夫曼编码输入代码串译码并输出程序由主函数模块，编码模块，译码模块组成，主函数模块可调用编码模块，译码模块，编码模块可对字符串进行编码，译码模块可对输入的代码串进行译码并输出。各模块之间的关系示意图如下：图1.各功能模块关系2. 课题涉及的数据结构 1. 哈夫曼树类型HTNode（树形结构）：typedef struct /哈弗曼树结点char data; /存储字符double weight; /存储权值int parent; /双亲结点位置int lchild; /左右孩子结点位置int rchild;HTNode; HTNode ht2n-1;2.哈夫曼编码类型HCode（顺序结构）typedef struct /各叶子结点的哈弗曼编码char cd30; /cdstartcdn存储哈夫曼编码int start; /字符数组中哈夫曼编码的起始位置HCode; HCode hcdn;3.CNode类型(顺序结构)typedef struct CNode /用于保存字符频度的类型char c; /存储出现字符种类int num; /字符出现次数int flag; /存储字符是否出现的标记 ; CNode CharNodeMAXV;三. 详细设计1.相关数据类型（采用C语言定义）int cdn; /储存哈夫曼编码 char strn; /储存需要编码的字符串double weight; /储存字符出现频度（权值）int lchild,rchild,parent; /储存哈夫曼树中各结点位置2.各函数的调用关系图、主要函数的流程图 main()insertstr() countstr() ；dispCNode()；CreateHT()；CreateHCode()；DispHCode();insertstr1();DispHCode();strcompare();图2.各函数调用关系示意图1.各函数调用关系2. CreateHT函数开始hti.parent=hti.lchild=hti.rchild=-1;i+;min1=min2=32767;lnode=rnode=-1;min2=min1;rnode=lnode;min1=htk.weight;lnode=k结束图3.CreateHT函数流程图i=0;i2n-1YNi=ni2n-1ki-1;k=0;htk.parent=-1Yhtk.weightmin1htk.weightmin2Ymin2=htk.weight;rnode=k;YNYNNhti.weight=htlnode.weight+htrnode.weight;htilchilde=lnode;htirchilde=rnode;htlnode.parent=i;htrnode.parent=i;NYN3.main函数开始调用CreateHT函数，构造haffman树调用CreateHCode函数，生成haffman编码译码输入str1;存在相应代码串结束NY 图4.main函数流程图flag=0YN开始结束hc.start=n;c=i;f=hti.parent;htf.lchild=chtf.cdhc.start-=0;htf.cdhc.start-=1;YNf!=-1Yhc.start+;hcdi=hc;Nin图5.CreateHcode函数流程图4. CreateHCode函数3.各模块的类C码算法1）编码模块：首先通过键盘输入需要键盘的字符串，调用countstr()函数统计并储存字符频度，再调用函数：void CreateHT(HTNode ht,int n) /构造哈弗曼树int i,j,k,lnode,rnode;double min1,min2; /分别存放lnode和rnode的两个结点位置 使所有结点的相关域置-1for(i=n;i2*n-1;i+)先寻找权值最小结点，使其成为左右孩子结点；再求出权值为左右孩子结点权值之和的hi结点；使hti作为双亲结点；再调用：void CreateHCode(HTNode ht,HCode hcd,int n) for(i=0;in;i+)hc.start=n;c=i;f=hti.parent;若hti为htf的左孩子结点，则hc.cdhc.start-=0;若hti为htf的右孩子结点，则hc.cdhc.start-=1;再对htf进行同样的判断，直至f=-1hc.start+;hcdi=hc;2）译码模块：先通过键盘输入哈夫曼编码代码串，再调用：int ReadCode(char str1,HCode hcd,HTNode ht,int MAX,int n) /译码函数int i,j,m=0,k;int flag=1; /flag为1则哈弗曼编码输入合法char temp30=;for(i=0;str1i!=0;i+,m+) /进行译码tempm=str1i;for(j=0;jn;j+)若找到对应编码printf(%c,htj.data);for(k=0;k30;k+)tempk=0;m=-1;终止循环；四. 调试分析以及设计体会1.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果：输入：图6.编码输入演示图输出：图7.编码输出演示图正确输入哈夫曼编码代号：图8.正确译码输入演示图输出：图9.正确输入译码译码结果输出演示图错误输入哈夫曼编码代号：图10.错误输入哈夫曼编码代码串示意图输出：图11.错误输入哈夫曼编码代码串输出示意图2.程序调试中遇到的问题以及解决问题的方法：编写完译码函数ReadCode（）后进行调试，程序会在译码过程中进入死循环，且无法译出正确字符串。经过仔细观察，发现程序中有一个循环的终止条件本应为stri!=0，却将其误写成了stri!=n,因而无法正常终止循环并译码，改正后实现了译码功能。3.课程设计过程经验教训、心得体会：此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终实现课题任务的过程中，我学到了不少东西：首先，在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题的时候，因为没有仔细理解这些要求，就采用了键盘输入字符进行编码和译码的方式，以致没有完全达到课题的要求。另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实现的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找改进程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用体验。最终在答辩的时候，交给老师的是一个界面简陋，功能不全面的程序。通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。五. 用户使用手册1.运行程序，程序首先会要求你输入需要编码的字符串，输入完毕按回车即可进行编码：图12.程序启动画面输出：图13.编码输出画面2.输出编码后，程序会提示输入需要译码的哈夫曼编码串，输入后按回车即可进行译码：图14.译码输入界面输出：图15.译码输出界面3.译码结束后，输入a可退出程序，输入b可继续进行译码。六. 附录源程序清单（带注释）：typedef.h文件代码：#define MAXV 30typedef struct CNode /用来保存字符次数的结构体char c;int num;int flag; ;typedef struct /哈弗曼树结点char data;double weight;int parent;int lchild;int rchild;HTNode;typedef struct /各叶子结点的哈弗曼编码char cd30;int start;HCode;main.cpp文件代码：#include#include#include #includetypedef.h#define N 100extern void insertstr(char str);extern int countstr(char str,CNode *);extern void dispCNode(CNode *,int);extern void CreateHT(HTNode ht,int); extern void CreateHCode(HTNode ht,HCode hcd,int n);extern int DispHCode(HTNode ht,HCode hcd,int n);extern void insertstr1(char str);extern int ReadCode(char str1,HCode hcd,HTNode ht,int MAX,int n);int n=0;void main()int i;int MAX; /哈弗曼编码的最大长度int flag=0; /标记哈弗曼编码输入是否合法char choice;char strN,str1N;CNode CharNodeMAXV;HTNode ht100;HCode hcd50;insertstr(str);printf(n);n=countstr(str,CharNode);printf(n);dispCNode(CharNode,n);printf(n);for(i=0;in;i+) /初始化哈弗曼树的叶子结点hti.data=CharNodei.c;hti.weight=CharNodei.num;CreateHT(ht,n);CreateHCode(ht,hcd,n);MAX=DispHCode(ht,hcd,n);printf(n);while(flag=0)insertstr1(str1);printf(n);printf(译码结果如下：n);flag=ReadCode(str1,hcd,ht,MAX,n);printf(n请选择：a（退出）/b（继续译码）n);getchar();scanf(%c,&choice);switch(choice)case a:exit(1);break;case b:flag=0;break;function.cpp文件代码：#include#include#includetypedef.h#define N 100void insertstr(char str) /输入字符串printf(请输入一个字符串：n);scanf(%s,str);int countstr(char str,CNode *CharNode) /记录字符出现次数，并保存在CNode中int i,j,a=0;for(i=0;iMAXV;i+)CharNodei.flag=-1;CharNodei.num=0;CharNodei.c=|;for(i=0;stri!=0;i+)for(j=0;jMAXV;j+)if(stri=CharNodej.c)CharNodej.num+;break;else if(CharNodej.flag=-1) a+;CharNodej.c=stri;CharNodej.num+;CharNodej.flag=0;break; return a;void dispCNode(CNode *CharNode,int n)int i;printf(输入的字符极其出现次数如下 ：n);for(i=0;iMAXV;i+)if(CharNodei.flag!=-1)printf(%c: ,CharNodei.c);printf(%dn,CharNodei.num); void CreateHT(HTNode ht,int n) /构造哈弗曼树int i,j,k,lnode,rnode;double min1,min2; /分别存放lnode和rnode的两个结点位置for(i=0;i2*n-1;i+) /所有结点的相关域置-1hti.parent=hti.lchild=hti.rchild=-1;for(i=n;i2*n-1;i+)min1=min2=32767;lnode=rnode=-1;for(k=0;k=i-1;k+)if(htk.parent=-1)if(htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if(htk.weightmin2)min2=htk.weight;rnode=k;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode; hti.rchild=rnode; /hti作为双亲结点htlnode.parent=i; htrnode.parent=i;void CreateHCode(HTNode ht,HCode hcd,int n) /求哈弗曼编码int i,f,c;HCode hc;for(i=0;in;i+)hc.start=n;c=i;f=hti.parent;while(f!=-1)if(htf.lchild=c)hc.cdhc.start-=0;elsehc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;hcdi=hc;int DispHCode(HTNode ht,HCode hcd,int n) /输出哈弗曼编码int i,k;int j;int MAX=0;printf(输出哈弗曼编码：n);for(i=0;in;i+)j=0;