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

软 件 学 院课程设计报告书课程名称 数据结构 设计题目 哈夫曼编码系统 专业班级 学 号 姓 名 指导教师 2012 年 1 月 目 录1 设计时间42 设计目的43 设计任务44 设计内容44.1 需求分析44.1.1 程序所能达到的功能44.1.2 输入的形式和输入值范围44. 1. 3 输出的形式44. 1. 4 测试数据44.2 总体设计54.2.1抽象数据类型的定义54.2.2主程序流程及各程序模块之间的层次关系图64.3详细设计74.3.1主函数及其他函数伪码算法74.3.2函数的调用关系图114.4 测试与分析124.4.1 测试124.4.2 分析144.5 附录145 总结与展望18参考文献19成绩评定201 设计时间2012年1月2日-2012年1月6日2 设计目的哈弗曼的设计，编码，译码输出。数据结构主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。3设计任务 从键盘输入一串电文字符能输出对应的哈夫曼编码。同时，能翻译由哈夫曼编码生成的代码串，输出相应的电文字符串。4 设计内容 4.1需求分析 4.1.1程序所能达到的功能:(1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树及哈夫曼编码。(2)利用已经建好的哈夫曼树，对输入的字符串进行编码，输出编码序列。(3)利用已建好的哈夫曼树对输入的二进制编码进行译码，并输出结果。4.1.2输入的形式和输入值的范围：输入的形式:数字；n=0; 4.1.3输出的形式：输出的形式：字符和数字4.1.4测试数据：正确的输入：输入构造哈夫曼树的数据个数：4输入第1个元素权值：7输入第2个元素权值：5输入第3个元素权值：2输入第4个元素权值：4输出：输出哈夫曼编码元素权值7 编码为0元素权值5 编码为10元素权值2 编码为110元素权值4 编码为111错误的输入：输入构造哈夫曼树的数据个数：4输出：输入数据个数不合法4.2总体设计4.2.1抽象数据类型的定义:(1)typedef struct tree int weight;/权值 int parent;/双亲结点 int lchild;/左孩子结点 int rchild;/右孩子结点 tree;(2)typedef struct code char cdmax;/存放哈夫曼码 nt start; /从start开始读cd中的哈夫曼码code;4.2.2主程序流程及各程序模块之间的层次（调用）关系图：翻译结果字符对应代码字符总数num建立哈夫曼树哈夫曼编码哈夫曼译码输入字符开始否是图4-1：主程序流程及各程序模块之间的层次（调用）关系图结束输入字符建立哈夫曼树翻译成代码哈夫曼编码哈夫曼译码进行翻译哈夫曼树否是图4-2：各程序模块之间的层次（调用）关系图4.3详细设计4.3.1主函数及其他函数伪码算法：/* - 赫夫曼树和赫夫曼编码的存储表示-*/# define max 50 # include stdio.htypedef struct tree int weight;/权值 int parent;/双亲结点 int lchild;/左孩子结点 int rchild;/右孩子结点 tree;typedef struct code char cdmax;/存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码code;/*-构造赫夫曼树 -*/void creat(tree *ht,int n)int i;if(n1)/判断输入值是否合法printf(输入数据个数不合法);exit(0);for(i=1;iweight); (ht+i)-parent=0; for(;iparent=(ht+i)-lchild=(ht+i)-rchild=0; /*-从叶子结点到根逆向求每个字符的赫夫曼编码-*/main() struct tree ht2*max; /建立结构体struct code hcdmax,d; /建立结构体int i,k,n,c,s1,s2,m1,m2,f; printf(输入构造哈夫曼树的数据个数: ); /建立哈夫曼树scanf(%d,&n); creat(ht,n);for(i=n+1;i=2*n-1;i+) /从叶子结点到根逆向求每个字符的赫夫曼编码 m1=m2=30000; s1=s2=0; for(k=1;k=i-1;k+) if(htk.parent=0 & htk.weightm1)/选择parent为0且weight最小的两个节点，其序号分别为s1,s2 m2=m1; s2=s1; m1=htk.weight; s1=k; else if(htk.parent=0 & htk.weightm2) m2=htk.weight; s2=k; hts1.parent=hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; for(i=1;i=n;i+)/逐个字符求哈夫曼编码 d.start=n-1; c=i; f=hti.parent; while(f) /循序直到树根结点结束循环，逆向 if(htf.lchild=c)d.cd-d.start=0; else d.cd-d.start=1; c=f; f=htf.parent; hcdi=d; printtree(ht,n,hcd); /*-输出每个叶子结点的赫夫曼编码-*/void printtree(tree *ht,int n,code *hcd)int i,k;printf(输出哈夫曼编码n ); /输出每个元素的哈夫曼编码for(i=1;iweight); printf(编码为);for(k=(hcd+i)-start;kcdk); printf(n ); 4.3.2函数的调用关系图：结束输入字符建立哈夫曼树翻译成代码哈夫曼编码哈夫曼译码进行翻译哈夫曼曼树否是图4-3：函数的调用关系图4.4测试与分析4.4.1测试输入构造哈夫曼树的数据个数：4输入第1个元素权值：7输入第2个元素权值：5输入第3个元素权值：2输入第4个元素权值：4输出哈夫曼编码元素权值7 编码为0元素权值5 编码为10元素权值2 编码为110元素权值4 编码为111错误的输入：输入构造哈夫曼树的数据个数：-1输出：输入数据个数不合法4.4.2分析从以上的截图可以看出，程序运行比较成功的进行了哈夫曼编码，而且对于一些错误的情况有了比较正确的反应。但是程序对于函数的调用方面有很大的不足。而且只能进行数字的哈夫曼树建立。时间复杂度上也有极大的改进机会。4.5 附录源程序代码：# define max 50 # include stdio.htypedef struct tree int weight;/权值 int parent;/双亲结点 int lchild;/左孩子结点 int rchild;/右孩子结点 tree;typedef struct code char cdmax;/存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码code;void creat(tree *ht,int n)int i;if(n1)/判断输入值是否合法printf(输入数据个数不合法);exit(0);for(i=1;iweight); (ht+i)-parent=0; for(;iparent=(ht+i)-lchild=(ht+i)-rchild=0; void printtree(tree *ht,int n,code *hcd)int i,k;printf(输出哈夫曼编码n ); /输出每个元素的哈夫曼编码for(i=1;iweight); printf(编码为);for(k=(hcd+i)-start;kcdk); printf(n ); main() struct tree ht2*max; /建立结构体struct code hcdmax,d; /建立结构体int i,k,n,c,s1,s2,m1,m2,f; printf(输入构造哈夫曼树的数据个数: ); /建立哈夫曼树scanf(%d,&n); creat(ht,n);for(i=n+1;i=2*n-1;i+) /从叶子结点到根逆向求每个字符的赫夫曼编码 m1=m2=30000; s1=s2=0; for(k=1;k=i-1;k+) if(htk.parent=0 & htk.weightm1)/选择parent为0且weight最小的两个节点，其序号分别为s1,s2 m2=m1; s2=s1; m1=htk.weight; s1=k; else if(htk.parent=0 & htk.weightm2) m2=htk.weight; s2=k; hts1.parent=hts2.parent=i; hti.lchild=s1; hti.rchild=s2; hti.weight=hts1.weight+hts2.weight; for(i=1;i=n;i+)/逐个字符求哈夫曼编码 d.start=n-1; c=i; f=hti.parent; while(f) /循序直到树根结点结束循环，逆向 if(htf.lchild=c)d.cd-d.start=0; else d.cd-d.start=1; c=f; f=htf.parent; hcdi=d; printtree(ht,n,hcd); 5 总结与展望通过一周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候，代码中有许多的错误，特别是有一个“无法找到文件”的错误让我束手无策，最后还是屏蔽了定义的四个头文件然后慢慢地改正错误才让我又看到了希望。然后在实现编码的读入时，由于对文件不是太熟悉，只好翻开C语言书本仿照其模式编写，但后来进入了死循环，最后的解决方式是把main函数里的一个dowhile循环去掉。在程序中， 许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，学会了如何截图，学会了如何更好的画流程图，明白了做事情只有认真，才能真正做得更好！参考文献1严蔚敏.数据结构（C语言版）M.北京:清华大学出版社,20072赵文静等.数据结构辅导M.西安交通大学出版社,1999 3张乃笑编.数据结构与算法M.电子工业出版社,20044陈文博,朱青著.数据结构与算法M.机械工业出版社,1996成绩评定成绩 教师签字19