数据结构课程设计56189new

1、课 程 设 计 书786645655学院 计算机学院 专业 信息与计算科学 5667789907yuiiiii2班 题目 利用树进行哈弗曼编码 教师 贺全兵 学生 傅登林12071030203 王瑶 12071030216 摘要：哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，哈弗曼编码在信息论中应用举例“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的

2、编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。 利用哈弗曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本，但是，这要求发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，对于双工通道（即可以双向传输的信道），每端都要有一个完整的编码译码系统，因此可以设计一个编码译码系统解决这样一个问题。关键字：树、哈弗曼编码、编码译码系统分工：程序设计及编写：王瑶、傅登林程序调试及实现：王瑶、傅登林时间复杂度分析：王瑶、傅登林实验报告书写：王瑶、傅登林15目录第一章 课程设计的内容及要求1第二章 功能说

3、明2第三章 详细设计33.1 创建哈弗曼树33.2 编码43.3 译码4第四章 程序实现54.1 源码分析54.2 调试结果84.3 调试分析11第五章 课程设计心得12第六章 参考文献13第一章 课程设计的内容及要求利用哈弗曼编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本，但是，这要求发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，对于双工通道（即可以双向传输的信道），每端都要有一个完整的编码译码系统，因此可以设计一个编码译码系统解决这样一个问题。第二章 功能说明系统分为三个模块：（1）、编码：读取字符建立哈夫曼树对文本进行哈弗曼编码并输出编码

4、（2）、译码：提示输入需要译码的字符利用建好的哈夫曼树进行译码 （3）、退出：退出系统，程序运行结束。第三章 详细设计3.1创建哈弗曼树开始初始化哈弗曼链表具有2n-1个结点i=1iweight=countiP=p-nextFor(i=n;iParent-LChildhc.cdhc.start-=1hc.cdhc.start-=0p=p-nexti=n时结束开始3.3译码P!=Rootp=p-RchildCoodi=0p=p-Lchildif(htc.lchild=1)c=2*n-2结束第4章 程序实现4.1 源码分析#include#include#include#include#inclu

5、de#include#include#defineUP50#defineDOWN90#defineLEFT60#defineRIGHT55#defineENTER40#defineN50#defineM2*N-1#defineSIZE6typedefstruct/定义结构体存放哈夫曼码chardata; floatweight;intparent,lchild,rchild;HTNode;intchoice;intkey()unionREGSlf;lf.h.ah=0;int86(0x16,&lf,&lf);returnlf.h.ah;structimformationcharch;floatf

6、re;imforSIZE=a,0.3,b,0.2,c,0.1,d,0.2,e,0.1,f,0.1; /给相关字符设置初值typedefstructcharcdN;intstart;HCode;voidCreateHT(HTNodeht,intn)inti,k,lnode,rnode;floatmin1,min2;for(i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=-1;for(i=n;i2*n-1;i+)/构造哈夫曼树min1=min2=1.1;/使用两个最小权值的结点为左孩子和右孩子lnode=rnode=-1;for(k=0;k=i-1;k

7、+)if(htk.parent=-1)if(htk.weightmin1) min2=min1;rnode=lnode; min1=htk.weight;lnode=k;elseif(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;getchar();voidCreateHCode(HTNodeht,HCodehcd,intn)inti,f,j,c;

8、HCodehc;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+;hcdi=hc;voidhuffmancode(HTNodeht,HCodehcd,intn)charbM,*p;inti,j,m,k;printf(pleaseinputthewords:n);scanf(%s,b);m=strlen

9、(b);for(i=0,p=b;im;i+,p+)for(j=0;jn;j+)if(htj.data=*p)for(k=hcdj.start;k=n;k+)printf(%c,hcdj.cdk);getch();printf(n);voidwords(HTNodeht,intn)intc;charcode1000,*p;printf(pleaseinputnumbers:n);scanf(%s,code);for(p=code,c=2*n-2;*p!=0;p+)if(*p=0)c=htc.lchild;if(htc.lchild=-1)printf(%c,htc.data);c=2*n-2;c

10、ontinue;elseif(*p=1)c=htc.rchild;if(htc.lchild=-1)printf(%c,htc.data);c=2*n-2;continue;getch();printf(n);mainmenu()cleardevice();setbkcolor(3);/设置当前背景颜色setcolor(2);/设置当前画笔颜色rectangle(40,60,600,440);line(40,100,600,100);outtextxy(240,80,Huffman);rectangle(150,145,350,195); setfillstyle(1,12);floodfil

11、l(160,150,14);outtextxy(152,150,a.Printhuffmancode);outtextxy(152,200,b.Printwords);outtextxy(152,250,c.Quit);voidchange(char*select,intn1,intn2,intx0,intlen,inty0,intwid1,intwid2) /完成两个窗口间的互换setviewport(x0,y0+wid2*n1,x0+len,y0+wid1+wid2*n1,1);clearviewport();setcolor(2);/设置当前背景颜色settextstyle(4,0,10

12、);outtextxy(2,5,selectn1);setviewport(x0,y0+wid2*n2,x0+len,y0+wid1+wid2*n2,1);clearviewport();setfillstyle(1,12);setcolor(2);rectangle(0,0,len,wid1);floodfill(30,5,1);setcolor(1);settextstyle(4,0,10);outtextxy(2,5,selectn2);voidmain()intn=SIZE,i,a,j,n1=0,n2=0;floatsum=0;char*select3=a.Printhuffmanco

13、de,b.Printwords,c.Quit;HTNodehtM;HCodehcdN;FILE*fp;charbM;intgraphdriver=DETECT,graphmode;initgraph(&graphdriver,&graphmode,TC+);registerbgidriver(EGAVGA_driver);cleardevice();setbkcolor(1);setviewport(0,0,639,479,1);clearviewport();setbkcolor(1);setcolor(2); rectangle(250,200,390,280);/在图形界面上画一个矩形框

14、setfillstyle(1,5);floodfill(300,240,14);settextstyle(4,0,10);outtextxy(252,202,ENTER); outtextxy(200,10,THEHUFFMANCODETRANSLATOR);line(0,30,640,30); getchar();setfillstyle(1,1);floodfill(300,240,14);outtextxy(252,205,ENTER);delay(300);cleardevice();fp=fopen(C:conf.txt,wb);for(i=0;iSIZE;i+)fwrite(&im

15、fori,sizeof(structimformation),1,fp);for(i=0;iSIZE;i+)sum+=imfori.fre;if(sum!=1)printf(ERROR!n);getch();exit(0); for(i=0;iSIZE;i+)fread(&imfori,sizeof(structimformation),1,fp);printf(%c:%.1fn,imfori.ch,imfori.fre);fclose(fp);for(i=0;iSIZE;i+)hti.data=imfori.ch;hti.weight=imfori.fre;CreateHT(ht,n);Cr

16、eateHCode(ht,hcd,n);cleardevice(); for(;) mainmenu(); do choice=key(); if(choice=DOWN) n1=n2; if(n2=2) n2=0; elsen2+; change(select,n1,n2,150,200,145,50,50);if(choice=UP)n1=n2;if(n2=0)n2=2;elsen2-;change(select,n1,n2,150,200,145,50,50); while(choice!=ENTER); switch(n2) case0:closegraph();huffmancode

17、(ht,hcd,n); ;break; case1:closegraph();words(ht,n);break; case2;break; 4.2 调试结果：调试在Windows2003上使用TC3.0完成。这是主界面：这是点击译码所得到的界面：4.3 调试分析1.从叶子节点开始向上遍历树，获得哈弗曼编码； 2.根据哈弗曼编码遍历哈夫曼树直到叶子结点，得到译码；3.算法时间复杂度的分析：时间复杂度为O(n2); 4.算法空间复杂度的分析：空间复杂度为O（n）。第5章 课程设计心得这次课程设计让我更了解大一学到的C语言和这个学期的数据结构。课程设计题目不仅要求对课本知识有深刻的了解，同时要求程序设计者有较强的思维和动手能力以及更加了解编程的思想和编程的技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的就是严谨，要有严谨的态度以及严谨的思维更要有严谨的算法分析，往往出现错误很久都不能检查出来，但是经过百般的调试之后才发现仅仅是一个括号或一个词语拼写的错误，也或者是数据类型的错误，这些小错误都是可以避免的，但我们往往就是在这些小错误上出现问题。例如，在运行的时候系统提示一句话的说明语法错误，而且下面附带很多错误，但往往这样的错仅仅是一句话的问题，但我们把这句话改过来发现下面的错误也消失了。所以说，细节决定成败。除此之外，在课程设计中我