2022年数据结构课程设计--哈夫曼编码 .pdf

课 程 设 计 报 告课程名称数据结构课题名称哈夫曼编码与译码专业通信工程班级通信 0902 学号200903020228 姓名肖俊指导教师田娟秀、李杰君、张鏖烽2011 年07 月 01 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 28 页 -湖南工程学院课 程 设 计 任 务 书课程名称数据结构课题哈夫曼编码与译码专业班级通信 0902 学生姓名肖俊学号200903020228 指导老师田娟秀、李杰君、张鏖烽审批任务书下达日期2011 年06 月27 日任 务 完 成 日 期2011 年07 月01 日名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 28 页 -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 语言定义相关的数据类型。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 28 页 -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%）。名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 28 页 -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 字以上（不含程序原代码）。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 28 页 -目录一.需求分析 .1 1.程序的功能 .1 2.输入输出的要求 .1 二.概要设计 .1 1.程序模块及其关系 .1 2.课题涉及的数据结构 .2 三.详细设计 .3 1.相关数据类型 .3 2.各函数的调用关系图、主要函数的流程图.3 3.各模块的类 C码算法 .7 四.调试分析以及设计体会 .9 1.测试数据 .9 2.程序调试中遇到的问题以及解决问题的方法.10 3.课程设计过程经验教训、心得体会.10 五.用户使用手册 .11 六.附录.12名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 28 页 -第 1 页共 21 页一.需求分析1.程序的功能能对输入的字符串实现Huffman 编码，且能利用生成的编码对Huffman 代码串进行译码，输出相应字符串。2.输入输出的要求首先，输入一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的次数，然后输出通过Huffman 编码得到的各种字符的Huffman 编码。此时程序要求输入一串 Huffman 代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出译码结果。二.概要设计1.程序模块及其关系程序由主函数模块，编码模块，译码模块组成，主函数模块可调用编码模块，译码模块，编码模块可对字符串进行编码，译码模块可对输入的代码串进行译码并输出。各模块之间的关系示意图如下：图 1.各功能模块关系主函数模块编码模块译码模块输入字符串构造哈夫曼树生成哈夫曼编码输入代码串译码并输出名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 28 页 -第 2 页共 21 页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;名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 28 页 -第 3 页共 21 页三.详细设计1.相关数据类型（采用C语言定义）int cdn;/储存哈夫曼编码char strn;/储存需要编码的字符串double weight;/储存字符出现频度（权值）int lchild,rchild,parent;/储存哈夫曼树中各结点位置2.各函数的调用关系图、主要函数的流程图1.各函数调用关系main()insertstr()countstr()；dispCNode()；CreateHT()；CreateHCode()；DispHCode();insertstr1();DispHCode();strcompare();图 2.各函数调用关系示意图名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 28 页 -第 4 页共 21 页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-1 Y N i=n i2n-1 ki-1;k=0;htk.parent=-1 Y htk.weightmin1 htk.weightmin2 Y min2=htk.weight;rnode=k;Y N Y N N hti.weight=htlnode.weight+htrnode.weight;htilchilde=lnode;htirchilde=rnode;htlnode.parent=i;htrnode.parent=i;N Y N 名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 28 页 -第 5 页共 21 页3.main 函数开始调用 CreateHT 函数，构造 haffman 树调用 CreateHCode函数，生成 haffman 编码译码输入 str1;存在相应代码串结束N Y 图 4.main 函数流程图flag=0 Y N 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 28 页 -第 6 页共 21 页4.CreateHCode函数开始结束hc.start=n;c=i;f=hti.parent;htf.lchild=c htf.cdhc.start-=0;htf.cdhc.start-=1;Y N f!=-1 Y hc.start+;hcdi=hc;N in 图 5.CreateHcode 函数流程图名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 28 页 -第 7 页共 21 页3.各模块的类 C码算法1）编码模块：首先通过键盘输入需要键盘的字符串，调用countstr()函数统计并储存字符频度，再调用函数：void CreateHT(HTNode ht,int n)/构造哈弗曼树 int i,j,k,lnode,rnode;double min1,min2;/分别存放 lnode和 rnode的两个结点位置使所有结点的相关域置-1 for(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=-1 hc.start+;名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 28 页 -第 8 页共 21 页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;终止循环；名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 28 页 -第 9 页共 21 页四.调试分析以及设计体会1.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果：输入：图 6.编码输入演示图输出：图 7.编码输出演示图正确输入哈夫曼编码代号：图 8.正确译码输入演示图输出：图 9.正确输入译码译码结果输出演示图名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 28 页 -第 10 页共 21 页错误输入哈夫曼编码代号：图 10.错误输入哈夫曼编码代码串示意图输出：图 11.错误输入哈夫曼编码代码串输出示意图2.程序调试中遇到的问题以及解决问题的方法：编写完译码函数ReadCode（）后进行调试，程序会在译码过程中进入死循环，且无法译出正确字符串。经过仔细观察，发现程序中有一个循环的终止条件本应为 stri!=0，却将其误写成了stri!=n,因而无法正常终止循环并译码，改正后实现了译码功能。3.课程设计过程经验教训、心得体会：此次课程设计，我编写程序的时候遇到了不少问题，在攻克这些问题，最终实现课题任务的过程中，我学到了不少东西：首先，在完成一个课题之前，要仔细理解课题要求。我在此次课程设计中犯的最严重的错误，应该算没有仔细审题。课题的要求是用读取文件的方式输入需要编码字符，译码所需的编码代号也要用文本方式输入。我在拿到这个课题的时候，因为没有仔细理解这些要求，就采用了键盘输入字符进行编码和译码的方式，以致没有完全达到课题的要求。另外，这次课程设计充分暴露了我的惰性思想。在拿到这个课题后，因为对哈夫曼编码这个知识点理解比较到位，所以没花多少时间就完成了课题要求实现的功能。然而，在此之后，我由于自我感觉良好和惰性，没有积极地去寻找改进程序的方法，也没对程序运行的界面进行美化，使其拥有良好的用户使用体验。最终在答辩的时候，交给老师的是一个界面简陋，功能不全面的程序。通过这次课程设计，我更加深入了理解了哈夫曼编码的过程，以及利用哈夫名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 28 页 -第 11 页共 21 页曼编码对数据进行压缩的优越性，并且使我能够更熟练地运用树形的数据结构。并且体会到了在学习中，要严格要求自己，不能因为一点点的成功就骄傲自满，停止不前。五.用户使用手册1.运行程序，程序首先会要求你输入需要编码的字符串，输入完毕按回车即可进行编码：图 12.程序启动画面输出：图 13.编码输出画面2.输出编码后，程序会提示输入需要译码的哈夫曼编码串，输入后按回车即可进行译码：图 14.译码输入界面输出：图 15.译码输出界面3.译码结束后，输入a 可退出程序，输入b 可继续进行译码。名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 28 页 -第 12 页共 21 页六.附录源程序清单（带注释）：typedef.h文件代码：#define MAXV 30 typedef 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 名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 28 页 -第 13 页共 21 页#include#includetypedef.h#define N 100 extern 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+)/初始化哈弗曼树的叶子结点 名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 28 页 -第 14 页共 21 页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 名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 28 页 -第 15 页共 21 页#define N 100 void 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)名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 28 页 -第 16 页共 21 页 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 的两个结点位置名师资料总结-精品资料欢迎下载-名师精心整理-第 22 页，共 28 页 -第 17 页共 21 页for(i=0;i2*n-1;i+)/所有结点的相关域置-1 hti.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;名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 28 页 -第 18 页共 21 页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;else hc.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+)名师资料总结-精品资料欢迎下载-名师精心整理-第 24 页，共 28 页 -第 19 页共 21 页 j=0;printf(%c:,hti.data);for(k=hcdi.start;k=MAX)MAX=j;printf(n);return MAX;void insertstr1(char str1)/输入哈弗曼编码 int i;for(i=0;iN;i+)/初始化 str1 str1i=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+)名师资料总结-精品资料欢迎下载-名师精心整理-第 25 页，共 28 页 -第 20 页共 21 页stri=hcda.cdj;if(strcmp(str,temp)=0)return 1;else return 0;int ReadCode(char str1,HCode hcd,HTNode ht,int MAX,int n)/译码函数 int strcompare(HCode hcd,char temp,int a,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+)if(strcompare(hcd,temp,j,n)/存在对应编码 printf(%c,htj.data);for(k=0;k=MAX-1)/输入不合法名师资料总结-精品资料欢迎下载-名师精心整理-第 26 页，共 28 页 -第 21 页共 21 页 printf(无译码，你所输入的编码不正确！n);flag=0;break;return flag;/返回标记值 名师资料总结-精品资料欢迎下载-名师精心整理-第 27 页，共 28 页 -计算机与通信学院课程设计评分表课程名称：哈夫曼编码与译码项目评价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩教师签名：日期：（注：1此页附在课程设计报告之后；2综合成绩按优、良、中、及格和不及格五级评定。）名师资料总结-精品资料欢迎下载-名师精心整理-第 28 页，共 28 页 -