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

1、软 件 学 院课程设计报告书课程名称 数据结构 设计题目 赫夫曼编码系统 专业班级 学 号 姓 名 指导教师 2012 年 1 月目录1 设计时间32 设计目的33设计任务34 设计内容34.1需求分析34.2总体设计44.3详细设计64.4测试与分析10测试10分析114.5 附录115 总结与展望16参考文献181 设计时间 2012年1月2日到2012年1月6日2 设计目的1) 巩固赫夫曼树的算法；2) 实现赫夫曼树的建立；3) 赫夫曼编码的生成；4) 赫夫曼文件的译码；3设计任务设计时间一周，对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。电报通

2、信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。设计实现的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编码文件的译码。 4 设计内容 4.1需求分析哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。称为赫夫曼编码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，WiLi恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种字符出现

3、的频率作权，构造一棵赫夫曼树。哈弗曼编码使用一张特殊的编码表将源字符进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。哈弗曼译码输入字符串可以把它编译成

4、二进制代码，输入二进制代码时可以编译成字符串。假设输入字符 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);赋值语句 变量名=表达式；循

5、环语句 for(赋初值表达式序列；条件；修改表达式序列)结束语句 return表达式；类型定义Typedef int status（2）、赫夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedef structchar aN; int start; HCode;进行赫夫曼编码译码之前建立赫夫曼二叉树，新建立赫夫曼树，建立赫夫曼编码，进行主函数时，输入A到F所有的字符，并输入其权值，将其进行编码；将data的权值赋给ht,判断结点是否大于1，输出根结点及权值。比较i<2*N-1;若是调用调用SELECT函数算出算出父亲结点然后输出两子

6、结点及父亲结点。开始N>1将data和weigth赋给HT输出根结点和权值调用SELECT函数计算根结点函数双亲为两结点之和输出两子结点和双亲结点是否为根结点？左子树为空此时编码为0I<2*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; /建立结构

7、体 HCode hcdN; /建立结构体 for (i=0;i<n;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）、

8、赫夫曼树的存储结构描述为：#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;i<2*n-1;i+) H

9、Ti.parent=HTi.lchild=HTi.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i<2*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.weight<m1) /若权值小于最小的左结点的权值 m2=m1;s2=s1; m1=HTk.weight;s1=k; else if (HTk.weight<m

10、2) m2=HTk.weight;s2=k;HTs1.parent=i;HTs2.parent=i; /两个最小节点的父节点是iHTi.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;i<n;i+) /根据哈夫曼树求哈夫曼编码 h.start=n;c=i;p=HTi.parent; while (p!=-1) /循序直

11、到树根结点结束循环 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;i<n;i+) /输出data中的所有数据，即A-F

12、 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")

13、;for (i=0;stringi!='#'i+) /#为终止标志for (j=0;j<n;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); /把要进行译码的字符串

14、存入cd数组中while(cd0!='#')for (i=0;i<n;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测试与分析测试进行第一步时输出编码列表A-F,运行结果如下：进行第二步编码，输入字符 B

15、CD# 运行结果如下:进行第三步译码，输入二进制代码01100000# 运行结果如下：分析1、定义了六个字符，超过这六个字符就不能跳出。2、不以#结束，程序就会无限循环。4.5 附录#define N 50 / 叶子结点数#define M 2*N-1 / 赫夫曼树中结点总数typedef struct int data; /叶子结点的值int weight; / 叶子结点的权值int lchild, rchild, parent; / 左右孩子及双亲指针HTNode; / 树中结点类型typedef structchar aN; int start; HCode;typedef HTNode

16、 HuffmanTreeM+1; void CreateHffumanTree(HTNode HT,int n) /调用输入的数组HT,和结点数n int i,k,s1,s2; int m1,m2; for (i=0;i<2*n-1;i+) HTi.parent=HTi.lchild=HTi.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i<2*n-1;i+) /构造哈夫曼树 m1=m2=32767; /int的范围是-3276832767 S1=s2=-1; /s1和s2记录最小权值的两个结点位置 for (k=0;k<=i-1;k+) if (HT

17、k.parent=-1) /只在尚未构造二叉树的结点中查找 if (HTk.weight<m1) /若权值小于最小的左节点的权值 m2=m1;s2=s1; m1=HTk.weight;s1=k; else if (HTk.weight<m2) 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 H

18、T,HCode hcd,int n) int i,p,c; HCode h; for (i=0;i<n;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 (HTN

19、ode HT,HCode hcd,int n) /输出赫夫曼编码的列表 int i,k; printf(" 输出赫夫曼编码:n"); for (i=0;i<n;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) /

20、编码函数char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要进行编码的字符串存入string数组中printf("n输出编码结果:n");for (i=0;stringi!='#'i+) /#为终止标志for (j=0;j<n;j+)if(stringi=HTj.data) for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.ak);break; /输出完成后跳出当前for循环Void HffumanCodeTrans

21、late(HTNode ht,HCode hcd,int n) /译码函数char cdMAXSIZE;int i,j,l,k,m,x;scanf("%s",cd); /把要进行译码的字符串存入cd数组中while(cd0!='#')for (i=0;i<n;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);fo

22、r(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;i<n;i+) /把初始化的数据存入HT结构体中 HTi.data=stri;HTi.weight=bi; CreateH

23、ffumanTree(HT,n);CreateHffumanCode (HT,hcd,n);DipHffumanCode(HT,hcd,n);printf("请输入要进行编码的字符串(以#结束):n");HffumanCode (HT,hcd,n);printf("请输入编码(以#结束):n");HffumanCodeTranslate (HT,hcd,n);5 总结与展望通过这次的课程设计，让我在程序编写上有了很大的，提高感觉到了程序设计真的很锻炼人，自己要学会慢慢的摸索路径，这样形成自己编程时的特色。一个成功的程序，要经过之前对课题的反复思考。这次我

24、运用的是数组存储类型，结构简单而且方便。通过运用for的多重循环，提高运行的效率。在编写这个程序之前，我复习之前学习的基本知识，赫夫曼最小路径的求法，赫夫曼编码及译码的范围，程序结构等相关问题。在编写过程中遇到了很多问题，经过寻求老师的帮助，以及借鉴别人的程序，最后终于编出自己的程序。在这次课程设计过程中，提高了我自己动手编写程序的能力以及综合运用知识的能力，体会到了学以致用，获得自己动手的劳动成果，高兴之外我也发现了自己的许多不足之处，对数据结构的内容基础不扎实，以及在语法上出现了许多问题，我会在在以后的日子里改进，在下一次课程设计是写出好的设计。#include <stdio.h&g

25、t;#include <string.h>#include <process.h>#include <malloc.h>typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配赫夫曼树typedef char * *HuffmanCode;/动态分配数组存储赫夫曼编码表int x1024,y1024,count;void SelectDifferentChar(int w,int &n);/将输入的字符串中相同的字符删

26、去 void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w,int n);void Select(HuffmanTree HT,int n,int &s1,int &s2);void ScanfCrunode(int w,char z,int &n);/读入结点，并将权值存到*w数组中void PrintHuffmanCode(HuffmanCode HC,int w,int n ,float eve);void Everage(float &eve,int w,int n,Huffman

27、Code HC);void main() HuffmanTree HT; HuffmanCode HC; int w1024,n; char z1024; float eve=0; ScanfCrunode(w,z,n); SelectDifferentChar(w,n); HuffmanCoding(HT,HC,w,n); Everage(eve,w,n,HC); PrintHuffmanCode(HC,w,n,eve);void ScanfCrunode(int w,char z,int &n)/读入结点，并将权值存到*w数组中int i; gets(z); count=n=str

28、len(z); if(n<=1) printf("wrong datan"); exit(0); for(i=0;i<n;i+) wi=zi;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w,int n)/赫夫曼编码int m,i,s1,s2,start,f,c; char *cd; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元没用 for(i=1;i<=n;i+) HTi.weight=wi-1; HTi.

29、parent=0; HTi.rchild=0; HTi.lchild=0; for(;i<=m;i+) HTi.weight=0; HTi.parent=0; HTi.rchild=0; HTi.lchild=0; for(i=n+1;i<=m;i+) Select(HT,i-1,s1,s2); HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(c

30、har *)malloc(n*sizeof(char); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd);void Select(HuffmanTree HT,int n,int

31、&s1,int &s2)int i,j,k; k=32767;/无符号整数最大值 for(i=1;i<=n;i+) if(HTi.weight<k&&HTi.parent=0) j=i; k=HTi.weight; s1=j; k=32767; for(i=1;i<=n;i+) if(HTi.weight<k&&HTi.parent=0&&i!=s1) j=i; k=HTi.weight; s2=j;void SelectDifferentChar(int w,int &n) int i,j,d=0

32、,k; for(i=0;i<n;i+) yi=wi; for(i=0;i<n;i+) for(j=i+1;j<n;j+) if(wi=wj) wj=-1; for(i=0;i<n;i+) if(wi!=-1) xd=wi; d+; k=n; n=d; for(i=0;i<n;i+) d=0; for(j=0;j<k;j+) if(xi=yj) d+; wi=d; if(n<=1) printf("wrong datan"); exit(0); void Everage(float &eve,int w,int n,Huffm

33、anCode HC)int sum=0,i; for(i=0;i<n;i+) sum+=wi; for(i=0;i<n;i+) eve+=(float)wi/sum)*strlen(HCi+1);void PrintHuffmanCode(HuffmanCode HC,int w,int n ,float eve)int i,j,k;for(i=0;i<n;i+) printf("%c编码为:",xi); puts(HCi+1); printf(" 出现次数为%d",wi); printf("n"); printf(

34、"平均编码长度为:%.2fn",eve); printf("译文如下n"); for(i=0;i<count;i+) for(j=0;j<n;j+) if(yi=xj) for(k=0;k<strlen(HCj+1);k+) printf("%c",HCj+1k); printf("n");参考文献1徐孝凯.数据结构简明教程M. 清华大学出版社，1995年2严蔚敏.数据结构【M】.清华大学出版社.2002年3 参考网址# include<stdio.h> #include<std

35、lib.h> #define MAXLEN 100 typedef struct Huffmantree char ch; /*键值*/ int weight,mark; /*weight为权值,mark为标志域*/ struct Huffmantree *parent,*lchild,*rchild,*next; Hftree,*linktree; /*整理输入的字符串，合并相同的项，并求出每个字符在数组中出现的次数 */ linktree tidycharacter(char character) int i=0; linktree tree,ptr,beforeptr,node;

36、/*链式 ,tree为头结点,beforeptr为ptr的前一结点,node为新申请的结点*/ tree=(linktree)malloc(sizeof(Hftree);/*创建单链表的头结点*/ if(!tree)return NULL; tree->next=NULL; /* 头结点为空,且后续结点为空*/ for(i=0;characteri!='0'&&characteri!='n'i+) /*遍历直到字符串结束为止*/ ptr=tree; beforeptr=tree; node=(linktree)malloc(sizeof(H

37、ftree); /*新申请结点node*/ if(!node)return NULL; node->next=NULL; node->parent=NULL; node->lchild=NULL; node->rchild=NULL; /*置空*/ node->mark=0; node->ch=characteri; node->weight=1; if(tree->next=NULL) tree->next=node; /*头结点的下一结点为空,连接node*/ else ptr=tree->next; while(ptr&

38、&ptr->ch!=node->ch) /*将指针移至链表尾*/ ptr=ptr->next; beforeptr=beforeptr->next; /*后移*/ if(ptr&&ptr->ch=node->ch) /*如果链表中某结点的字符与新结点的字符相同*/ ptr->weight=ptr->weight+1; /*将该结点的权加一*/ free(node); /*释放node结点的存储空间*/ else /*新结点与表中结点不相同,将新结点插入链表后*/ node->next=beforeptr->ne

39、xt; beforeptr->next=node; /*node连接在beforeptr之后*/ return tree; /*将整理完的字符串按出现次数从小到大的顺序排列 */ linktree taxisnode(linktree tree) linktree head,ph,pt,beforeph; /*head为新链表的表头结点*/ head=(linktree)malloc(sizeof(Hftree);/*创建新链表的头结点*/ if(!head)return NULL; head->next=NULL; /*新结点的头结点为空,后续结点也为空*/ ph=head; b

40、eforeph=head; while(tree->next) pt=tree->next;/*取被操作链表的首元结点*/ tree->next=pt->next; pt->next=NULL; /*取出pt所指向的结点*/ ph=head->next; beforeph=head; if(head->next=NULL) head->next=pt;/*创建当前操作链表首元结点*/ else while(ph&&ph->weight<pt->weight) /*将被操作结点插入相应位置*/ ph=ph->

41、next; beforeph=beforeph->next; pt->next=beforeph->next; beforeph->next=pt; free(tree); return head; /*用排完序的字符串建立霍夫曼树 */ linktree createHftree(linktree tree) linktree p,q,newnode,beforep; for(p=tree->next,q=p->next;p!=NULL&&q!=NULL;p=tree->next,q=p->next) tree->next

42、=q->next; q->next=NULL; p->next=NULL; newnode=(linktree)malloc(sizeof(Hftree);/*申请新结点作为霍夫曼树的中间结点*/ if(!newnode)return NULL; newnode->next=NULL; newnode->mark=0; newnode->lchild=p;/*取链表头结点后的两个结点作为新结点的左、右儿子*/ newnode->rchild=q; p->parent=newnode; q->parent=newnode; newnode-&

43、gt;weight=p->weight+q->weight; p=tree->next; beforep=tree; if(p!=NULL&&p->weight>=newnode->weight) /*将新结点插入原链表的相应位置*/ Newnode->next=beforep->next; beforep->next=newnode; else while(p!=NULL&&p->weight<newnode->weight) p=p->next; beforep=beforep-&

44、gt;next; newnode->next=beforep->next; beforep->next=newnode; return (tree->next); /*对霍夫曼树进行编码 */ void Huffmancoding(linktree tree) int index=0; char *code; linktree ptr=tree; code=(char *)malloc(10*sizeof(char);/*此数组用于统计霍夫曼编码*/ printf("字符以及它的相应权数-霍夫曼编码nn"); if(ptr=NULL) printf(

45、"霍夫曼树是空的!n"); exit(0); else while(ptr->lchild&&ptr->rchild&&ptr->mark=0) while(ptr->lchild&&ptr->lchild->mark=0) codeindex+='0' ptr=ptr->lchild; if(!ptr->lchild&&!ptr->rchild) ptr->mark=1; codeindex='0' printf(&q

46、uot;tw%c=%dttt",ptr->ch,ptr->weight); for(index=0;codeindex!='0'index+) printf("%c",codeindex); printf("n"); ptr=tree; index=0; if(ptr->rchild&&ptr->rchild->mark=0) ptr=ptr->rchild; codeindex+='1' if(!ptr->lchild&&!ptr->

47、;rchild) ptr->mark=1; codeindex+='0' printf("tw%c=%dttt",ptr->ch,ptr->weight); for(index=0;codeindex!='0'index+) printf("%c",codeindex); printf("n"); ptr=tree; index=0; if(ptr->lchild->mark=1&&ptr->rchild->mark=1) ptr->mark=1; ptr=tree; index=0; printf("n"); free(code); /*解码 */ void decode(linktree tree,char code) int i=0,j=0; char *ch