数据结构课程设计报告——哈夫曼编译码器.

1、数据结构课程设计报告专业班级：信息 0802 姓名：赵思宇 学号： 0909081029 指导老师：李登 日期： 2010 年 7 月19、实验内容哈夫曼编 / 译码器 利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时 间，降低传输成本。 但是， 这要求在发送端通过一个编码系统对待传数据预先编 码，在接收端将传来的数据进行译码（复原） 。对于双工信道（即可以双向传输 信息的信道），每端都需要一个完整的编 /译码系统。试为这样的信息收发站写一 个哈夫曼编 /译码系统。一个完整的系统应具有以下功能：（1） I :初始化（Initialization ）。从终端读入字符集大小n,以及

2、n个字符和 n 个权值，建立哈夫曼树，并将它存于文件 hfmTree 中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文 件 htmTree 中读入）,对文件 ToBeTran 中的正文进行编码,然后将结果存入文件 CodeFile 中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件 CodeFile中的代 码进行译码，结果存入文件 TextFile 中。（4）P:印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printin

3、g）。将已在内存中的哈夫曼树以直观的方 式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件 TreePri nt 中。二、实验目的学习数据结构与算法的最终目的是解决实际的应用问题， 特别是非数值计算 类型的应用问题。本课程设计要求同学独立完成一个较为完整的应用需求分析， 在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、 理论和方法的理解； 训练综合运用所学知识处理实际问题的能力， 使同学的程序 设计与调试水平有一个明显的提高。三、实验思想及分析一个完整的系统应具有以下功能：I:初始化（Initialization）。从终端读入字符集大小n，以及n个字符和

4、n个 权值，建立赫夫曼树，并将它存于文件 hfmTree 中。 对赫夫曼树初始化。 根据书本算法 6.12 ，对树进行从叶子到根的逆向求每个字符的赫夫曼编码。 更新赫夫曼树，并存到 hfmTree.txt 中。算法6.12流程图如下:图1算法6.12流程图E：编码(Encoding)。利用已建好的哈夫曼树，对文件 ToBeTran中的正文 进行编码，然后将结果存入文件 CodeFile中。 将终端输入须要编码的语句逐字在已建好的赫夫曼树中查找。 当在树中找到相匹配字符时，将该字符对应的赫夫曼编码用strcat() 统一存到code数组。 最后将 code 数组中的编码在终端输出并存储到 Cod

5、eFile.txt 中。D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件 Textfile 中。 从 CodeFile.txt 中获取须要译码的编码组。 将编码逐一读入，并在赫夫曼中根据左 0右 1去查找字符。 将译好的语句在终端输出，并存至 Textfile.txt 中。P:打印表(TreePrint)。将已建立好的赫夫曼树的存储情况在终端以表格的形式罗列出来，使树的调用看起来更直观。T：打印图(TreePrint)。将已建好的赫夫曼树以直观的图形在终端输出。 根据树的先序遍历算法，依次访问各个结点。 根据P打印出来的表，分析其所在的层次

6、。 根据层次的大小， 在终端输出相应长度的长条， 来完成凹入表的输出。四、程序代码：#include#include#includetypedef structchar elem;int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;/ 动态分配数组存储赫夫曼树typedef char *HuffmanCode;/ 动态分配数组存储赫夫曼树编码表void Initialization();void Encoding();void Decoding();void HuffmanCoding(int);void Select(int,int

7、 *,int *);void PrintHufmFigue();void putout(int,int);void Turn(int,void(* Visit)(int,int);void TreePrint();/ 全局函数 int ipt=1,n,q,p=0,code_num=0,TempLen=0,diamonds,lay;int w1=100000,w2=100000,w3=100000;HuffmanCode HC=NULL; HuffmanTree HT;int main()char key; system(color FC);printf(”l1n);prin tf(|赫夫曼编

8、/译码器| n);prin tf(| n);printf(|08 信息 赵思宇| n);printf(”n);doprintf(nnn);printf(”i1n);printf(|1操作菜单| n);printf(|1| n);printf(|1I：初始化(Initialization)| n);printf(|IE:编码(Encoding)| n);printf(|D: 译 码(Decoding)| n);printf(|1P：打印表(PrintHufmFigue )| n);printf(|1T:打印图(TreePrint)| n);printf(|1Q：退出(Initialization

9、)| n);printf(|1| n);prin tf(IIn);printf(nn);printf(Please Enter a key of the operation:); scanf(%c,&key);getchar();switch(key)case i:case I:Initialization();break;case e:case E:Encoding();break;case d:case D:Decoding();break;case p: case P:PrintHufmFigue();break;case t:case T:TreePrint();while(key!=

10、q&key!=Q);return 1;/* 函数功能：建立赫夫曼树并对其进行初始化。函数参数： FILE *FhfmTreeP ，将赫夫曼树的相关信息保存于此hfmTree.TXT 中。函数实现：实现了字符集和频度的实际统计，并可将信息保存到 hfmTree.TXT 中。 函数返回值：无*/void Initialization()int i,m;char style= ,0;printf(Please input the number of Node: );scanf(%d,&n);getchar();m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HT

11、Node); /0 号单元未用 for(i=1;i=n;i+)printf(Input characters and weight(just like a 30Enter):); scanf(%c%d,&HTi.elem,&HTi.weight); getchar();HTi.parent=HTi.lchild=HTi.rchild=0;HuffmanCoding(n);FILE* FhfmTreeP=NULL; if(NULL=(FhfmTreeP=fopen(E:hfmTree.txt,w) printf(Open hfmTree.txt failed!n);elsefor(i=1;i0)

12、，构造赫夫曼树 HT ，并求出m=2*n-1;n 个字符的赫夫曼编码 HC 。*/for(i=n+1;i=m;+i)HTi.elem=0;HTi.weight=HTi.parent=HTi.lchild=HTi.rchild=0;for(i=n+1;i=m;+i)Select(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(ch

13、ar*);向量cd=(char *)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)/建赫夫曼树/* 在 HT1.i-1选择 pare nt 为 0 且 weight 最小的两个结点，其 . 序号分别为 s1,s2*/分配n 个字符编码的头指针/分配求编码的工作空间/编码结束符/逐个字符求赫夫曼编码/从叶子到根逆向求编码if(HTf.lchild=c) cd-start=0; else cd-start=1;HCi=(char *)malloc(n

14、-start)*sizeof(char); strcpy(HCi,&cdstart);free(cd); return;/HuffanCoding/ 为第 i 个字符编码分配空间 /从 cd 复制编码（串）到 HC/释放工作空间/* 函数功能：选出当前字符集中，两个最小值s1,s2.函数参数： *s1,*s2, 用于存储选出的两个最小值。 函数返回值：无*/void Select(int n,int *s1,int *s2)int i;(*s1)=(*s2)=0;for(i=1;i=n;i+) if(HTi.weightHT(*s2).weight&HTi.parent=0&(*s2)!=0)

15、 if(HTi.weightHT(*s1).weight)(*s2)=(*s1);(*s1)=i;else (*s2)=i;if(*s1)=0|(*s2)=0)&HTi.parent=0)if(*s1)=0) (*s1)=i;else if(*s2)=0)if(HTi.weight(*s2) i=(*s1); (*s1)=(*s2); (*s2)=i;return;/*函数功能：将终端输入的字符串编译成用0/1 表示的编码，并将相应信息存入 TXT 文档。函数参数： temp1000, 用于临时存储终端输入的字符串。Code1000,用于存储0/1编码。ToBeTran.txt, 用于存储终端

16、输入的字符串。CodeFile.txt ，用于存储编译后的 0/1 编码。函数返回值：无*/void Encoding()int i,j,all;char temp1000,code10000;printf(Please put in the sentence you want to Encoding:);/scanf(%s,temp);getchar();gets(temp);code0=0;FILE* FToBeTranP=NULL;if(NULL=(FToBeTranP=fopen(E:ToBeTran.txt,w)printf(Open ToBeTran.txt failed!n);e

17、lsefputs(temp,FToBeTranP);fclose(FToBeTranP);TempLen=strlen(temp);for(i=0;iTempLen;i+)all=0;for(j=1;j=n;j+)if(tempi=HTj.elem) strcat(code,HCj); all=1;if(all=0)printf(Some charactor in the sentence are not matching!); code_num=strlen(code); printf(Codes of the sentence are:n%sn,code);FILE* FCodeFileP

18、=NULL; if(NULL=(FCodeFileP=fopen(E:CodeFile.txt,w) printf(Open CodeFile.txt failed!n);elsefputs(code,FCodeFileP);fclose(FCodeFileP);printf(And have put into E:CodeFile.txt!n); return;/Decodingvoid Decoding()int m,i,p=0;char q,*Decode,*Sentence;FILE* FDecodeP=NULL;if(NULL=(FDecodeP=fopen(E:CodeFile.t

19、xt,r) printf(Open E:CodeFile.txt failed!n);elseFILE *TxtFile=NULL;if(NULL=(TxtFile=fopen(E:TxtFile.txt,w)printf(Open E:TxtFile.txt failed!n);elseSentence=(char*)malloc(TempLen*sizeof(char);Decode=(char*)malloc(code_num*sizeof(char);fgets(Decode,code_num+1,FDecodeP);m=2*n-1;for(i=0;Decodei-1!=0;i+) q

20、=Decodei;if(HTm.lchild=0)Sentencep=HTm.elem;p+;m=2*n-1;i-;else if(q=0) m=HTm.lchild;else if(q=1) m=HTm.rchild;Sentencep=0;fputs(Sentence,TxtFile);printf(Codes have been Encoded and get a sentence:n%sn,Sentence); printf(And have been put into TxtFile.txt!n);/* 函数功能：输出赫夫曼树中各结点的数据存储情况。函数参数：无。函数返回值：无。*/

21、void PrintHufmFigue() int i,m;char end=,0;printf(”|1111111)；printf( | Number | Element | Weight | Parents | Lchild | Rchild | HuffmanCode | );printf(|1111111”)；for(i=1;i=n;i+)printf( |%6d|%8c|%6d|%8d|%8d|%8d|%20s|,i,HTi.elem,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild,HCi)；printf( |1111111); m=2*n-1

22、;for(i=n+1;i=m-1;i+)%20s |%20s |);prin tf(”I %6d|%8c|%6d|%8d|%8d|%8d|,i,HTi.elem,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild,end);printf(” |111111);printf( |%6d|%8c|%6d|%8d|%8d|%8d|,m,HTm.elem,HTm.weight,HTm.parent,HTm.lchild,HTm.rchild,end);printf( 11111111return;/*函数功能：将赫夫曼树以凹入表的形式在终端输出。 函数参数： 无。函

23、数返回值：无。*/void TreePrint()int MaxCode,MaxI=1,Floor,numb,i; numb=2*n-1;MaxCode=strlen(HC1); for(i=1;iMaxCode) MaxCode=strlen(HCi);MaxI=i;Floor=MaxCode+1; diamonds=Floor+10; lay=diamonds;Turn(numb,putout);return;void Turn(int w,void(* Visit)(int,int)p+;w3=w2;w2=w1;w1=w; if(w3w2&w2=1;count-)printf(” );

24、if(HTlr.lchild!=0)printf(%dn,HTlr.weight); elseprintf(%cn,HTlr.elem); printf(n);return;操作菜单CInit ialiwat ion (Encoding(Decoding(TreePrintCInit ialiwat ion 化码码表图出缶口力.F EI:E:D:p:T:Q:五、程序运行情况：I :初始化(Initialization ):贰 E:HuffManCppl.exe6 4 3 2 27 8 6 12 32 1 A B c DEl 03F21G15H47157JIK5L32M20N57063Pl 5Q

25、IR48S51180U23U8U18KI16Z1E: SJif mTree -txt!图2.输入I运行结果功目重重重重重重重重重重重重重重重重重重重重重重重重重重重入 的数戎取戎取戎取戎取戎取戎取戎取戎取戎取戎取戎取取取取取取存 一爲及及及及及及及及及及及及及及及及及及及及及及及及及及及已 入入壬rW-WOmWWWWWWWWW-WH 兀 入入入入入入入入入入入入入入入入入入入入入入入入入入码沙 *- F .JI .b .- .* .- * .t * .J.h .- .b .- * JI .Jt .h .-卜 F- I-_ 卜.h 卜.卜.卜.h化码码表图出A口 女 E EI:E:D:p:T:Q

26、:化码码表图岀 A口 1 女 EE I:E:D:p;T:Q:E：编码(Encoding )朋 E:HuffanCpp1. exe操作菜单Ini t i aliza t :Lon DecodingIni t i aliza t :Lon 请撅入要执征的功链9请输入你要编译的句子:THIS PEOGRAM IS M FfiUOEITE编译的句子为：00101000011110111001101010101101011011001111111000011111111110111111111011001111Bl01010011010001110010已存入 E： CodeFile .txt!图3.输

27、入E运行结果D :译码(Decoding)c* E: HuffanCppl. eze操作菜单 (Encoding 己被存入TxtFile .txt?图4.输入D运行结杲P:打印表(TreePrint)c* E:HuffanCpp1. exe操作菜单初始化 编码 讦璽 打印表 0=请输入要执行的功能号码字符权重双亲左孩子右孩子哈夫曼编码11U647UUM2A64450011003B1333001011004C223700001105D32390&11010fiE480R0107F2136001111108G1533n1011 019H474100001010I574300100011J12800111101110012K531001111011013L3239001101114n2皿36111111图5.输入P运行结果g E:HuffManCpp1.exe15N57430