数据结构课程设计-赫夫曼编码.doc

软 件 学 院课程设计报告书课程名称 数据结构 设计题目 赫夫曼编码系统 专业班级 学 号 姓 名 指导教师 2012 年 1 月目录1 设计时间32 设计目的33设计任务34 设计内容34.1需求分析34.2总体设计44.3详细设计64.4测试与分析104.4.1测试104.4.2分析114.5 附录115 总结与展望16参考文献18 1 设计时间 2012年1月2日到2012年1月6日2 设计目的1) 巩固赫夫曼树的算法；2) 实现赫夫曼树的建立；3) 赫夫曼编码的生成；4) 赫夫曼文件的译码；3设计任务设计时间一周，对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。设计实现的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编码文件的译码。 4 设计内容 4.1需求分析 哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。称为赫夫曼编码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树。哈弗曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。假设输入字符 BCD 编码成二进制代码应与特殊的编码表上的二进制编码相同输出应为0010100000，若出现其他情况的结果，错误；假设输入二进制代码0010100000，则编译成字符串正确应为 BCD ， 若出先其他情况的结果，错误。4.2总体设计（1）、程序中用到的所有抽象数据类型的定义预定义常量#define N 50 #define M 2*N-1 #define MAXSIZE 100输入输出语句输入语句 scanf (格式串，变量1，变量2，。变量n);输出语句 printf(格式串，变量1，变量2，。变量n);赋值语句 变量名=表达式；循环语句 for(赋初值表达式序列；条件；修改表达式序列)结束语句 return表达式；类型定义Typedef int status（2）、赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedef struct char aN; int start; HCode;进行赫夫曼编码译码之前建立赫夫曼二叉树，新建立赫夫曼树，建立赫夫曼编码，进行主函数时，输入A到F所有的字符，并输入其权值，将其进行编码；将data的权值赋给ht,判断结点是否大于1，输出根结点及权值。比较i1将data和weigth赋给HT输出根结点和权值调用SELECT函数计算根结点函数双亲为两结点之和输出两子结点和双亲结点是否为根结点？左子树为空此时编码为0I2*N-1?I+编码为1结束否否否右子树为空是是否否是是是图4.2关系流程图4.3详细设计（1）、主函数void main() int n=6,i;char str=A,B,C,D,E,F; /初始化 int b=3,7,4,5,9,1; /初始化 HTNode HTM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入HT结构体中 hti.data=stri; hti.weight=bi; CreateHffumanTree(HT,n);CreateHffumanCode (HT,hcd,n);DipHffumanCode(HT,hcd,n);printf(请输入要进行编码的字符串(以#结束):n);HffumanCode (HT,hcd,n);printf(请输入编码(以#结束):n);HffumanCodeTranslate (HT,hcd,n);（2）、赫夫曼树的存储结构描述为： #define N 50 / 叶子结点数 #define M 2*N-1 / 赫夫曼树中结点总数 typedef struct int weight; / 叶子结点的权值 int lchild, rchild, parent; / 左右孩子及双亲指针 HTNode; / 树中结点类型 typedef HTNode HuffmanTreeM+1; （3）、赫夫曼树的算法void CreateHffumanTree(HTNodeHT,int n) /调用输入的数组HT,和结点数n int i,k,s1,s2; int m1,m2; for (i=0;i2*n-1;i+) HTi.parent=HTi.lchild=HTi.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 m1=m2=32767; / /int的范围是-3276832767 S1=s2=-1; /s1和s2记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (HTk.parent=-1) /只在尚未构造二叉树的结点中查找 if (HTk.weightm1) /若权值小于最小的左结点的权值 m2=m1;s2=s1; m1=HTk.weight;s1=k; else if (HTk.weightm2) m2=HTk.weight;s2=k; HTs1.parent=i;HTs2.parent=i; /两个最小节点的父节点是i HTi.weight=HTs1.weightHTts2.weight; HTi.lchild=s1;HTi.rchild=s2; /父节点的左节点和右节点（4）、赫夫曼编码void CreateHffumanCode(HTNode HT,HCode hcd,int n) int i,f,c; HCode h; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 h.start=n;c=i; p=HTi.parent; while (p!=-1) /循序直到树根结点结束循环 if (HTp.lchild=c) /处理左孩子结点 h.cdh.start-=0; else /处理右孩子结点 h.cdh.start-=1; c=p;p=HTf.parent; h.start+; /start指向哈夫曼编码h.cd中最开始字符 hcdi=h; Void DipHffumanCode (HTNode ht,HCode hcd,int n) /输出赫夫曼编码的列表 int i,k; printf( 输出赫夫曼编码:n); for (i=0;in;i+) /输出data中的所有数据，即A-F printf( %c:t,HTi.data); for (k=hcdi.start;k=n;k+) / /输出所有data中数据的编码 printf(%c,hcdi.ak); printf(n); voidHffumanCode (HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环（5）、赫夫曼译码Void HffumanCodeTranslate(HTNode ht,HCode hcd,int n) /译码函数char cdMAXSIZE;int i,j,l,k,m,x;scanf(%s,cd); /把要进行译码的字符串存入cd数组中while(cd0!=#)for (i=0;in;i+)M=0; /M为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(cdj=hcdi.cdk) /当有相同编码时M值加1M+;if(M=j) printf(%c,HTi.data);for(x=0;cdx-1!=#;x+) /把已经使用过的cd数组里的字符串删除cdx=cdx+j;4.4测试与分析4.4.1测试进行第一步时输出编码列表A-F,运行结果如下： 图4.4.1.1进行第二步编码，输入字符 BCD# 运行结果如下: 图4.4.1.2进行第三步译码，输入二进制代码01100000# 运行结果如下： 图4.4.1.2 图4.4.1.34.4.2分析1、定义了六个字符，超过这六个字符就不能跳出。2、不以#结束，程序就会无限循环。4.5 附录#define N 50 / 叶子结点数 #define M 2*N-1 / 赫夫曼树中结点总数 typedef struct int data; /叶子结点的值int weight; / 叶子结点的权值 int lchild, rchild, parent; / 左右孩子及双亲指针 HTNode; / 树中结点类型 typedef struct char aN; int start; HCode;typedef HTNode HuffmanTreeM+1; void CreateHffumanTree(HTNode HT,int n) /调用输入的数组HT,和结点数n int i,k,s1,s2; int m1,m2; for (i=0;i2*n-1;i+) HTi.parent=HTi.lchild=HTi.rchild=-1; / /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 m1=m2=32767; / /int的范围是-3276832767 S1=s2=-1; /s1和s2记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (HTk.parent=-1) /只在尚未构造二叉树的结点中查找 if (HTk.weightm1) /若权值小于最小的左节点的权值 m2=m1;s2=s1; m1=HTk.weight;s1=k; else if (HTk.weightm2) m2=HTk.weight;s2=k; HTs1.parent=i;HTs2.parent=i; /两个最小节点的父节点是I HTi.weight=HTs1.weight+HTs2.weight; HTi.lchild=s1;HTi.rchild=s2; /父节点的左节点和右节点nuvoid CreateHffumanCode(HTNode HT,HCode hcd,int n) int i,p,c; HCode h; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 h.start=n;c=i; p=HTi.parent; while (p!=-1) /循序直到树根结点结束循环 if (HTp.lchild=c) /处理左孩子结点 h.ah.start-=0; else /处理右孩子结点 h.ah.start-=1; c=p;p=HTp.parent; h.start+; /start指向哈夫曼编码h.cd中最开始字符 hcdi=h; Void DipHffumanCode (HTNode HT,HCode hcd,int n) /输出赫夫曼编码的列表 int i,k; printf( 输出赫夫曼编码:n); for (i=0;in;i+) /输出data中的所有数据，即A-F printf( %c:t,HTi.data); for (k=hcdi.start;k=n;k+) / /输出所有data中数据的编码 printf(%c,hcdi.ak); printf(n); voidHffumanCode (HTNode HT,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=HTj.data) for (k=hcdj.start;k=n;k+) printf(%c,hcdj.ak);break; /输出完成后跳出当前for循环Void HffumanCodeTranslate(HTNode ht,HCode hcd,int n) /译码函数char cdMAXSIZE;int i,j,l,k,m,x;scanf(%s,cd); /把要进行译码的字符串存入cd数组中while(cd0!=#)for (i=0;in;i+)m=0; /M为相同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(cdj=hcdi.ak) /当有相同编码时M值加1m+;if(M=j) printf(%c,HTi.data);for(x=0;cdx-1!=#;x+) /把已经使用过的cd数组里的字符串删除cdx=cdx+ j;void main() int n=6,i;char str=A,B,C,D,E,F; /初始化 int b=3,7,4,5,9,1; /初始化 HTNode HTM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入HT结构体中 HTi.data=stri; HTi.weight=bi; CreateHffumanTree(HT,n