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

《数据结构课程设计--哈夫曼编码.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计--哈夫曼编码.docx（28页珍藏版）》请在三一办公上搜索。

1、课程设计报告课程名称数据结构课题名称哈夫曼编码与译码业级号名通信工程专班学姓指导教师田娟秀、李杰君、张鏖烽2011年07月01日湖南工程学院课程设计任务书课程名称数据结构课 题哈夫曼编码与译码专业班级学生姓名学号指导老师审批1设计内容与设计要求1.1设计内容课题五：对电文中的字符串编码和译码Huffman编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景， 是数据压缩中的一个重要理论依据。对输入的一串文字符号实现Huffman编码，再对 Huffman编码生成的代码串进行译码，输出电文字符串。要求完成以下功能：a）针对给定的字符串，建立Huffman树。b）生成Huffman编码。

2、c）对编码文件译码。1.2选题方案：所选题目根据学号确定，学号模6加1，即（学号%6+1）。如你的学号为9,则 所选题目号为：9%6+1=（题目4）。注意，所有的课题都要求用图形方式演示步骤 和结果。有兴趣的同学可以自己针对数据结构课程中所讲算法来设计一个演示过程 的算法。1.3设计要求：1.3.1课程设计报告规范（1）需求分析a. 程序的功能。匕输入输出的要求。（2）概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模 块的功能。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样 的结构，它们之间有什么关系等。（3）详细设计a.采用C语言定义

3、相关的数据类型。b. 写出各模块的类C码算法。c. 画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和 含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a. 设计报告要求用A4纸打印成册：b. 一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录源程序清单（带注释）1.3.2考核方式指导老师负责验收程序的运行结果，并结合学

4、生的工作态度、实际动手能力、创新 精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出 每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.3.3课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依

5、内容的创新程度，完善程序情况及对程序讲解情况打分。2进度安排第19周：星期一8: 0012：00上课星期一14： 30-18：30上机星期二14：3018：30上机星期四8：0012：00上机附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。正文的格式:一级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）三、主要功能的实现（至少要有 一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。 正文总字数要求在4

6、500字以上（不含程序原代码）。目录一. 需求分析11. 程序的功能12. 输入输出的要求1二. 概要设计11. 程序模块及其关系12. 课题涉及的数据结构2三. 详细设计31. 相关数据类型32. 各函数的调用关系图、主要函数的流程图33. 各模块的类C码算法7四. 调试分析以及设计体会91. 测试数据92. 程序调试中遇到的问题以及解决问题的方法103. 课程设计过程经验教训、心得体会10五. 用户使用手册11六. 附录12一. 需求分析1. 程序的功能能对输入的字符串实现Huffman编码，且能利用生成的编码对Huffman代码串进 行译码，输出相应字符串。2. 输入输出的要求首先，输入

7、一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的 次数，然后输出通过Huffman编码得到的各种字符的Huffman编码。此时程序要求输 入一串Huffman代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出 译码结果。二. 概要设计1. 程序模块及其关系程序由主函数模块，编码模块，译码模块组成，主函数模块可调用编码模块，译码 模块，编码模块可对字符串进行编码，译码模块可对输入的代码串进行译码并输出。 各模块之间的关系示意图如下：图1.各功能模块关系2. 课题涉及的数据结构1.哈夫曼树类型HTNode （树形结构）：typedef struct/哈弗曼树结点char d

8、ata;存储字符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 CNodechar c;int num

9、;int flag;CNode CharNodeMAXV;三. 详细设计1. 相关数据类型（采用C语言定义）int cdn;储存哈夫曼编码char strn;储存需要编码的字符串double weight;储存字符出现频度（权值）int lchild,rchild,parent;储存哈夫曼树中各结点位置2. 各函数的调用关系图、主要函数的流程图1. 各函数调用关系strcompare();图2.各函数调用关系示意图2. CreateHT 函数图3.CreateHT函数流程图3.main函数图4.main函数流程图4. CreateHCode函 数开始htf.lchild=cf!=-1YNinY

10、NIFhc.start=n;c=i;f=hti.parent;htf.cdhc.start-=0；htf.cdhc.start-= 1hc.start+;hcdi=hc;图5.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+)先寻

11、找权值最小结点，使其成为左右孩子结点；再求出权值为左右孩子结点权值之和的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的左孩子结点，贝uhc.cdhc.start-=0;若hti为htf的右孩子结点，贝uhc.cdhc.start-=1;再对htf进行同样的判断，直至f=-1hc.start+;hcdi=hc;2)译码模块： 先通过键盘输入哈夫曼编码代码串，再调用： int ReadCode(char str1,HC

12、ode 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.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果:输入：请输入一个字符串:abbcccdddd

13、图6.编码输入演示图输出:输入的字符极其出现次数如下:a： 1b： 2c： 3d： 4输出哈弗曼编码：a： 110b： 111c： 10d： 0正确输入哈夫曼编码代号:请输入一串需要译码的哈弗景编码:1111100图8.正确译码输入演示图输出:译码结果如下:bad图9.正确输入译码译码结果输出演示图错误输入哈夫曼编码代号:请输入一串需要译码的哈弗曼编码:123455678图10.错误输入哈夫曼编码代码串示意图输出：耘活次雷酬入的编码不正确!青选择：丑（退出）外（继续译码）图11.错误输入哈夫曼编码代码串输出示意图2. 程序调试中遇到的问题以及解决问题的方法：编写完译码函数ReadCode（）后

14、进行调试，程序会在译码过程中进入死循 环，且无法译出正确字符串。经过仔细观察，发现程序中有一个循环的终止条 件本应为stri!=:0,，却将其误写成了 stri!=:n5,因而无法正常终止循环并译 码，改正后实现了译码功能。3. 课程设计过程经验教训、心得体会：此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终 实现课题任务的过程中，我学到了不少东西：首先，在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯 的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入 需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题 的时候，因为没有仔细理

15、解这些要求，就采用了键盘输入字符进行编码和译码 的方式，以致没有完全达到课题的要求。另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对 哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实 现的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找 改进程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用 体验。最终在答辩的时候，交给老师的是一个界面简陋，功能不全面的程序。通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫 曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结 构。并且体会到了在学习中，要严格要

16、求自己，不能因为一点点的成功就骄傲 自满，停止不前。五.用户使用手册1.运行程序，程序首先会要求你输入需要编码的字符串， 可进行编码：输入完毕按回车即请输入一个字符串：图12.程序启动画面输出:输入的字符极其出现次数如下:a： 3d： 2F： 1输出哈弗曼编码：a： 0d： 11F： 10图13.编码输出画面2.输出编码后，程序会提示输入需要译码的哈夫曼编码串，输入后按回车即 可进行译码：青输入一串需要译码的哈弗曼编码:图14.译码输入界面输出：译码结果如下：adf请选择：己（退出）凡（继续译码）图15.译码输出界面3.译码结束后，输入a可退出程序，输入b可继续进行译码。六.附录源程序清单（带

17、注释）：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 100exte

18、rn 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,H

19、Code 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

20、=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:

21、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(

22、j=0;jMAXV;j+)if(stri=CharNodej.c)CharNodej.num+;break;elseif(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.n

23、um);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

24、.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(

25、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；printf(%c: ,hti.data);for(k=hcdi.start;k=MAX)MAX=j;printf(n);return MAX;void insertstr1(char str1

26、)/ 输入哈弗曼编码int i;for(i=0;iN;i+)/初始化 str1str1i=0;printf(请输入一串需要译码的哈弗曼编码：n);scanf(%s,str1);int strcompare(HCode hcd,char temp,int a,int n)/ 字符串比较函数int i,j=hcda.start;char str30=”;for(i=0;j=n;i+,j+)stri=hcda.cdj;if(strcmp(str,temp)=0)return 1;elsereturn 0;int ReadCode(char str1,HCode hcd,HTNode ht,int M

27、AX,int n)/ 译码函数int strcompare(HCode hcd,char temp,int a,int n);/声明字符串比较函数 printf（无译码，你所输入的编码不正确！ n）;int i,j,m=0,k;int flag=1;合法char temp30=”;for(i=0;str1i!=0;i+,m+)tempm=str1i;for(j=0;jn;j+)if(strcompare(hcd,temp,j,n)printf(%c,htj.data);for(k=0;k=MAX-1)/flag为1则哈弗曼编码输入进行译码/存在对应编码/输入不合法flag=0;break;return flag;/返回标记值计算机与通信学院课程设计评分表课程名称：哈夫曼编码与译码项目评价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩教师签名：日 期：（注：1.此页附在课程设计报告之后；2.综合成绩按优、良、中、及格和不及格五级评定。）