《数据结构课程设计总结报告 哈夫曼编码译码.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计总结报告 哈夫曼编码译码.doc（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 数据结构课程设计实验报告题 目 哈夫曼编码/译码器 学 院 数理与信息学院 专 业 计算机科学与技术 班 级 计科132 学生姓名 刘海澍 5 周弘杰 8 徐铭瑶 3 指导教师 编写日期 目 录1 问题描述12 问题分析13 算法设计23.1抽象数据类型定义23.2模块划分34 详细设计44.1数据类型的定义44.2主要模块的算法描述44.3 流程图65 测试分析96 课程设计总结107 成员分工10参考文献11附录（源程序清单）121.问题描述设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。1) 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫
2、曼树；2) 编码：利用建好的哈夫曼树生成哈夫曼编码；3) 输出编码；4）显示哈夫曼树；5）界面设计的优化；6) 设字符集及频度如下表：字符 空格 A B C D E F 频度 4 9 23 2 17 15字符 G H I J K频度 1 2 3 3 42.问题分析（1）定义一个变量名为HTNode的结构体，用该结构体中的char data、int weight、int parent、int lchild、int rchild分别表示哈夫曼树中每个结点的权值、权重、双亲结点、左孩子、右孩子，再定义一个HTNode类型的数组ht60存放哈夫曼树；另外定义一个变量名为HCode的结构体，采用HCod
3、e类型变量的cdstartcdn存放当前结点的哈夫曼编码、最后定义一个HCode类型的数组hcd30的数组用于存放当前叶子结点hti的哈夫曼编码。（2）编写CodeInput(n,ht)函数并在函数中设置一个for(i=0;n;+)循环，首先输入n个字符，再编写一个for(j=0;jn;j+)循环将n个字符保存到全局数组ch里，再利用函数中的for(i=0;in;i+)循环实现对这n个字符的权值的输入。（3）编写CreateHT(ht,n)函数来构造一棵哈夫曼树，首先用一个for(i=0;2*n-1;+)循环将所有2n-1个结点的parent、lchild、rchild域均置初值为-1；再用一
4、个for(i=n;2*n-1;+)循环来构造哈夫曼树，在该循环中首先令lnode和rnode为最小权值的两个结点位置且其域值均为-1，再用一个for(k=0;k=i-1;k+)循环在数组ht30中寻找权值最小并且尚未构造二叉树的结点中查找，由于只能在尚未构造二叉树的结点中查找，因此在for(k=0;k=i-1;k+)循环中加入一个if(htk.parent=-1)语句来判断结点lnode和rnode是否已经在二叉树中，如果结点lnode和rnode在二叉树中，则结点lnode和rnode的parent的值为其双亲结点在数组ht30中的序号就不会为-1了，在查找到htlnode和htrnode后
5、将他们作为hti的左右子树，htlnode和htrnode的双亲结点置为hti，且hti.weight=htlnode.weight+htrnode.weight。如此处理下去，直到所有2n-1个结点处理完毕。（4）编写CreateHCode(ht,hcd,n)函数来求哈夫曼编码，由于求哈夫曼编码只需求叶子结点的哈夫曼编码。对于当前叶子结点hti，首先将对应的哈夫曼编码hcdi的start域值置初值n，找其双亲结点htf，若当前结点是双亲结点的左孩子结点，则在hcdi的cd数组中添加0，若当前结点是双亲的右孩子结点，则在hcdi的cd数组中添加1，将start域减1。再对双亲结点进行同样的操作
6、，直到无双亲结点为止，最后让start指向哈夫曼编码最开始字符。因此在函数中设置一个for(i=0;in;i+)循环，在循环中设置一个while(f!=-1)循环语句来判断循环是否到了根结点，再在while(f!=-1)中设置一个if(htf.lchild=c)语句来判断该处理左孩子结点还是该处理右孩子结点。最后用这个for(i=0;in;i+)循环来根据哈夫曼树求出哈夫曼编码。（5）最后编写CodeOutput(n,hcd)函数，首先利用for(i=0;in;i+)循环和for(j=hcdi.start;j=n;j+)循环来实现所有字符的哈夫曼编码的输出；再利用for(i=0;in;i+)循
7、环和for(j=hcdi.start;j=n;j+)循环来实现每个字符的序号和哈夫曼编码的输出。将每个字符在哈夫曼树中的位置用shp+1o=chi+1保存到全局数组sh中用以输出哈夫曼树。 （6）显示哈夫曼树 （7）界面的优化3. 算法设计31抽象数据类型定义（1）树的抽象数据类型定义ADT Stack数据对象：D=ai|aiElemSet,i=1,2,.,n, n0数据关系：若D为空集，则称为空树。 若D仅为一个数据元素，则R为空集，否则R=H，H是如下的二元关系：（1）再D中存在唯一的称为根的数据元素root，它在关系H下无前驱。（2）若D-root空集，则存在一个划分D1，D2，Dm（m
8、0）。（3）对应于D-root的划分，H-root，X1，有唯一的一个划分H1，H2，Hm（m0）。基本操作：InitTree(&T)操作结果：构造空树T。DestroyTree(&T)初始条件：树T已存在。操作结果：树T被销毁。ClearTree(&T)初始条件：树T已存在。操作结果：将树T清为空栈。TreeEmpty(T)初始条件：树T已存在。操作结果：若树T为空，则返回TRUE，否则FALSE。TreeDepth(T)初始条件:树T已存在。操作结果：返回T的深度。Root（T）初始条件：树T已存在。操作结果：返回树T的根。32程序划分本程序包括四个部分：（1）主程序部分void main
9、()初始化；构造哈夫曼树；求哈夫曼编码；哈夫曼编码输出；哈夫曼树输出（2）哈夫曼树部分实现哈夫曼树的抽象数据类型（3）求哈夫曼编码部分实现求哈夫曼编码算法的数据类型（4）打印哈弗曼树4. 详细设计41数据类型的定义（1）哈夫曼树类型/哈夫曼树类型 typedef struct/构造树 char data;/结点权值 int weight;/权重 int parent;/双亲结点 int lchild;/左孩子 int rchild;/右孩子 HTNode; HTNode ht60;（2）求哈夫曼编码类型typedef struct char cd30;/存放当前结点的哈弗曼编码 int sta
10、rt;/cdstartcdn存放哈弗曼码 HCode; HCode hcd30;42主要的算法描述（1）主函数int main() int n; printf(请输入要输入的字符数量n:);/读入字符的个数 while(scanf(%d,&n),n!=-1)/初始化 printf(请输入n个字符和n个权值n); CodeInput(n,ht);/输入数据函数，将读入n个字符和权重 CreateHT(ht,n);/构造哈弗曼树 CreateHCode(ht,hcd,n);/哈弗曼编码算法 CodeOutput(n,hcd);/打印哈弗曼编码，将打印出编码，和每一个字符的编码 return 0;（
11、2）构造哈夫曼树void CreateHT(HTNode ht,int n)/构造一棵哈夫曼树 int i,k,lnode,rnode; int min1,min2; 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为最小权值的两个结点位置 lnode=rnode=-1; for (k=0;k=i-1; k+)/在ht中查找权值的最小的两个结点 if (htk.parent=-1)/只在尚未构
12、造的二叉树的结点中查找 if (htk.weightmin1) min2=min1;rnode=lnode; min1=htk.weight; lnode=k; else if (htk.weightmin2) min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode; hti.rchild=rnode;/ht作为双亲结点 （3）利用哈夫曼编码算法哈夫曼编码void CreateHCode(HTNode ht,H
13、Code 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+;/start指向哈弗曼编码最开始的位置 hcdi=hc; （4）打印哈夫曼编码并确定每个编码对应的哈夫曼树坐标打印哈夫曼编码 void CodeOut
14、put(int n,HCode hcd) int i, j, p=0, q=0; char zh2020,x20,y20; printf(所有字符的哈弗曼编码n); for (i=0;in;i+) for(j=hcdi.start;j=n;j+) printf(%c,hcdi.cdj); printf(n); for (i=0;in;i+) printf(序号%d %c: , i, chi+1); for(p=0,q=0,j=hcdi.start;j=n;j+) printf(%c,hcdi.cdj ); if(hcdi.cdj = 0) p+; q=0;else if(hcdi.cdj =
15、1)p+; q+=2; shpq=chi+1; printf(%d,%d)n,p,q);printf(n); 43 流程图（1）主函数流程如图4.3-1 4.3-1 主函数流程图（2）构造哈夫曼流程图，如图4.3-2开始Htk.weightmin2结束Htk.weightmunlk=kMin2=htk.weightRnode=k;Htlnode.parent=i;Htrnode.parent=i;Hti.weight=htlnode.weight+htrnode.weight;Hti.lchild=lnode;Hti.rchild=rnode;K+;4.3-2构造哈弗曼树流程图 （3）哈弗曼编
16、码流程图，如图4.3-3Int f,c;Hcode hc;开始结束Hcdi=hc;i+;f!=-1i=0;Hc.start=n;c=i;inHc.start+;Hc.cdhc.start-=1;Htf.lchild=c;C=f;F=htf.parent;Hc.cdhc.start-=0; 4.3-3 哈弗曼编码流程图（4）打印哈弗曼编码流程图，如图4.3-4 Int i=0,j;开始inJ=hcdi.start结束i+;Printf(“%c”,hcdi.cdj);j+;printf(“序号%d %c:”,i,chi+1);j=hcdi.start;inprintf(“n”);i=0;print
17、f(“%c”,hcdi.cdi);i+;j=nPrintf(“n”);j=n5. 测试分析测试数据及结果如下：JDKHSGAF结果分析：首先确定要输入的字符数量n为8，然后分别输入这8个字符和这8个字符的权值，且输入的这8个字符分别为B、C、D、E、F、G、H、I而这8个字符对应的权值分别为13、22、32、103、21、15、47、57。其次根据输出的结果可知：所有字符的哈夫曼为011。其中序号0表示字符A，其哈夫曼编码为0010；序号1表示字符S，其哈夫曼编码为110；序号2表示字符D，其哈夫曼编码为010；序号3表示字符F，其哈夫曼编码为0011；序号4表示字符G，其哈夫曼编码为111；
18、序号5表示字符H，其哈夫曼编码为10；序号6表示字符J，其哈夫曼编码为000；序号7表 ICFEHDBG示字符K，其哈夫曼编码为011，这个8个字符 对应的哈夫曼树如右图。 0 1 0 1 0 1 0 1 0 1 0 1 0 16. 课程设计总结6.1课程设计过程中出现的技术难点和解决方法：（1）输入的字符个数不确定，可跟据情况输入。 (2）哈夫曼树的类型。(3）哈夫曼编码类型。（4）构造哈夫曼树算法。（5）计算哈夫曼编码算法。（6）哈夫曼树坐标算法6.2解决方法:(1）通过向老师虚心学习请教（2）和同学们细心交流，认真讨论。（3）上网参考，吸取别人的精华。6.3课程设计期间的主要收获：通过这
19、次课程设计使我们充分的理解了用哈夫曼树再编码问题中基本原理的应用，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编码问题的程序。在刚开始编程的时候，我们感到很茫然，无从下手。但是困难是可以解决的，只要通过努力，向老师虚心学习请教，再难的题目也可以自己动手完成。由于本课题中的许多知识点都没有学过都要靠自己到课外的资料中去查找。在用的时候难免出现这样那样的错误。回顾起此次课程设计，至今感慨颇多，从拿到题目到完成整个编程，从理论到实践，虽然只有几天，但可以学到很多的东西，不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我们懂得了理论与
20、实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体。通过这次的数据结构课程设计，我们也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才还有一个比较满意的成果。4. 成员分工队长：刘海澍 分工：收集资料，算法分析，编写代码，PPT制作，流
21、程分析与编写 队员：周弘杰 分工：收集资料，算法分析，编写代码 ，PPT制作与介绍 队员：徐铭瑶 分工：收集资料，算法分析，程序调试，PPT播放，制作流程图，总结 参考文献1 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，19972 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20084 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#include #includechar ch60;/字符 char sh2020;/树节点 /哈夫曼树类型 typed
22、ef struct/构造树 char data;/结点权值 int weight;/权重 int parent;/双亲结点 int lchild;/左孩子 int rchild;/右孩子 HTNode; HTNode ht60;/哈夫曼编码类型 typedef struct char cd60;/存放当前结点的哈弗曼编码 int start;/cdstartcdn存放哈弗曼码 HCode; HCode hcd60;/构造哈夫曼树 void CreateHT(HTNode ht,int n) int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;
23、i+)/所有结点的相关域置初值-1 hti.parent=hti.lchild=hti.rchild=-1; for (i=n;i2*n-1;i+)/构造哈弗曼树 min1=min2=32767;/lnode和rnode为最小权值的两个结点位置 lnode=rnode=-1; for (k=0;k=i-1; k+)/在ht中查找权值的最小的两个结点 if (htk.parent=-1)/只在尚未构造的二叉树的结点中查找 if (htk.weightmin1) min2=min1;rnode=lnode; min1=htk.weight; lnode=k; else if (htk.weight
24、min2) min2=htk.weight; rnode=k; htlnode.parent=i; htrnode.parent=i; hti.weight=htlnode.weight+htrnode.weight; hti.lchild=lnode; hti.rchild=rnode;/ht作为双亲结点 /哈夫曼编码算法 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!=
25、-1)/循环知道树的根结点 if(htf.lchild=c) hc.cdhc.start-=0;/处理左孩子结点 else hc.cdhc.start-=1;/处理右孩子结点 c=f; f=htf.parent; hc.start+;/start指向哈弗曼编码最开始的位置 hcdi=hc; /输入数据函数 void CodeInput(int n) int i; printf(请输入n个权值n);for (i=0;in;i+) scanf(%d,&hti.weight);/打印哈夫曼编码 void CodeOutput(int n,HCode hcd) int i, j, p=0, q=0;
26、char zh2020,x20,y20; printf(所有字符的哈弗曼编码n); for (i=0;in;i+) for(j=hcdi.start;j=n;j+) printf(%c,hcdi.cdj); printf(n); for (i=0;in;i+) printf(序号%d %c: , i, chi+1); for(p=0,q=0,j=hcdi.start;j=n;j+) printf(%c,hcdi.cdj ); if(hcdi.cdj = 0) p+; q=0;else if(hcdi.cdj = 1)p+; q+=2; shpq=chi+1; printf(%d,%d)n,p,
27、q);printf(n); /主函数 int main() int n, j,i;/for(i=0;i20;i+)/for(j=0;j0&n+60) printf(请输入n个字符n); for(j=0;j=n;j+) scanf(%c,&chj); getchar(); /printf(请输入n个权值n); CodeInput(n);/输入数据函数，将读入n个字符和权重 CreateHT(ht,n);/构造哈弗曼树 CreateHCode(ht,hcd,n);/哈弗曼编码算法 CodeOutput(n,hcd);/ void TreeOutput(sh);printf(打印树:n);print
28、f( *n);/1printf( / n);printf( %c %cn,sh21,sh22);/2printf( / / n);printf( %c %c %c %cn,sh31,sh32,sh33,sh34);/3printf( / / / / n);printf(%c %c %c %c %c %c %c %cn,sh41,sh42,sh43,sh44,sh45,sh46,sh47,sh48);printf(.);/ for (i=0;in;i+)/ / printf(序号%d %c: , i, chi+1);/ for(j=hcdi.start;j5)MessageBox(N不可以小于0
29、或大于5);void CMyNewDlg:OnChangeEdit2() /第二个编辑框的输入/从编辑框得到一个字符串并输入数组中CString edit2; GetDlgItemText(IDC_EDIT2,edit2); for(int i = 0; iedit11)MessageBox(输入字符超限);void CMyNewDlg:OnChangeEdit3() /第三个编辑框的输入/从编辑框得到一个字符串并输入数组中CString edit3; GetDlgItemText(IDC_EDIT3,edit3); for(int i = 0; iedit3.GetLength(); i+) chi = edit3.GetAt(i);