《数据结构课程设计--哈夫曼编码》由会员分享，可在线阅读，更多相关《数据结构课程设计--哈夫曼编码（28页珍藏版）》请在金锄头文库上搜索。
1、课程设计报告课程名称数据结构课题名称哈夫曼编码与译码专业通信工程班级学号姓名指导教师田娟秀、李杰君、张鏖烽2011年 07 月 01 日湖南工程学院课程设计任务书课程名称数据结构课 题哈夫曼编码与译码专业班级学生姓名学 号指导老师审 批任务书下达日期 2011 年 06 月 27 日任务完成日 期 2011 年 07 月 01 日1 设计内容 与设计要求1.1设计内容课题五：对电文中的字符串编码和译码Huffman编码是一种最优变长码，即带权路径最小。这种编码有很强的应用背景， 是数据压缩中的一个重要理论依据。对输入的一串文字符号实现Huffman编码，再对 Huffman编码生成的代码串进行
2、译码，输出电文字符串。要求完成以下功能：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. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模 块的
3、功能。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样 的结构，它们之间有什么关系等。( 3 )详细设计a.采用C语言定义相关的数据类型。b. 写出各模块的类C码算法。c. 画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和 含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。（5）使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a. 设计报告要求用A4纸打印成册：b. 级标题用3号黑
4、体，二级标题用四号宋体加粗，正文用小四号宋体;行距为 22。（7）附录源程序清单（带注释）1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新 精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出 每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占 10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占 40%）（4）设计报告（占 30%） 注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立
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。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画
6、出模块图）；三、主要功能的实现（至少要有 一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释） 正文总字数要求在 4500字以上（不含程序原代码）。目录一. 需求分析 11. 程序的功能 12. 输入输出的要求 1二. 概要设计 11. 程序模块及其关系 12. 课题涉及的数据结构 2三. 详细设计 31.相关数据类型 32.各函数的调用关系图、主要函数的流程图33. 各模块的类 C 码算法 7四. 调试分析以及设计体会91.测试数据 92.程序调试中遇到的问题以及解决问题的方法103. 课程设计过程经验教训、心得体会10五. 用户使用手册 1
7、1六.附录 12一. 需求分析1. 程序的功能 能对输入的字符串实现 Huffman 编码，且能利用生成的编码对 Huffman 代码串进 行译码，输出相应字符串。2. 输入输出的要求 首先，输入一个字符串，程序会列出字符串中包含的字符种类及每一种字符出现的 次数，然后输出通过 Huffman 编码得到的各种字符的 Huffman 编码。此时程序要求输 入一串Huffman代码串，输入完毕程序会判断输入的代码串是否合法，若合法则输出 译码结果。二. 概要设计1. 程序模块及其关系 程序由主函数模块，编码模块，译码模块组成，主函数模块可调用编码模块，译码 模块，编码模块可对字符串进行编码，译码模
8、块可对输入的代码串进行译码并输出。 各模块之间的关系示意图如下：图 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;/字符数组中哈夫曼编码的
9、起始位置HCode;HCode hcdn;/用于保存字符频度的类型/存储出现字符种类/字符出现次数/存储字符是否出现的标记3.CNode 类型（顺序结构）typedef struct CNodechar c;int num;int flag;CNode CharNodeMAXV;三. 详细设计1相关数据类型（釆用C语言定义）int cdn;/储存哈夫曼编码char strn;/储存需要编码的字符串double weight;/储存字符出现频度（权值）int lchild,rchild,parent; /储存哈夫曼树中各结点位置2 各函数的调用关系图、主要函数的流程图1.各函数调用关系main(
10、)DSDstrcompare();2. CreateHT 函数图 3.CreateHT 函数流程图3.main 函数开始N存在相应代码串YYNflag=0输入 strl;调用CreateHCode函数, 生成haffman编码调用CreateHT函数, 构造haffman树译码第5页共 2l 页4. CreateHCode函数开始htf.lchild=cNYYf!=-1Ninhc.start=n;c=i; f=hti.parent;htf.cdhc.start-=O；htf.cdhc.start-=Thc.start+; hcdi=hc;3. 各模块的类C码算法1)编码模块：首先通过键盘输入需
11、要键盘的字符串，调用countstr()函数统计并储存字符频 度，再调用函数：void CreateHT(HTNode ht,int n) /构造哈弗曼树int i,j,k,lnode,rnode;double minl,min2;分别存放Inode和rnode的两个结点位置使所有结点的相关域置-1for(i=n;i2*n-l;i+) 先寻找权值最小结点，使其成为左右孩子结点； 再求出权值为左右孩子结点权值之和的hi结点；使hti作为双亲结点；再调用：void CreateHCode(HTNode ht,HCode hcd,int n)for(i=0;in;i+)hc.start=n;c=i;
12、f=hti.parent;若hti为htf的左孩子结点，贝Uhc.cdhc.start-=0;若hti为htf的右孩子结点，贝Uhc.cdhc.start-=l;再对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.测试数据： 准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果：输入：请输入一个字符串:abbcccdddd图 6. 编码输入演示图输出：输入的字符极其岀现次数如下:a： 1b： 2c： 3d： 4输岀哈弗曼编码：a： 110b： 111c： 10d： 0正确输入哈夫曼编码代号:请输
