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

数据结构课程设计报告专业班级：信息0802姓名：赵思宇学号：0909081029指导老师：李登日期：2010年7月一、实验内容 哈夫曼编/译码器利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。一个完整的系统应具有以下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2）E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3）D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。（4）P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。二、实验目的 学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。本课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，使同学的程序设计与调试水平有一个明显的提高。三、实验思想及分析一个完整的系统应具有以下功能：n I：初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。 对赫夫曼树初始化。 根据书本算法6.12，对树进行从叶子到根的逆向求每个字符的赫夫曼编码。 更新赫夫曼树，并存到hfmTree.txt中。算法6.12流程图如下：开始传入参数：结点个数nI<=n? NY动态分配内存，声明哈夫曼树HT，并对其值进行初始化建哈夫曼树，依次在HT1.i-1中Select parent为0且weight最小的两个结点分配n个字符编码的头指针向量和求编码的工作区间从叶子到根逆向逐个字符求哈夫曼编码释放工作空间结束图1 算法6.12流程图n E：编码(Encoding)。利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 将终端输入须要编码的语句逐字在已建好的赫夫曼树中查找。 当在树中找到相匹配字符时，将该字符对应的赫夫曼编码用strcat()统一存到code数组。最后将code数组中的编码在终端输出并存储到CodeFile.txt中。n D：译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 从CodeFile.txt中获取须要译码的编码组。 将编码逐一读入，并在赫夫曼中根据左0右1去查找字符。 将译好的语句在终端输出，并存至Textfile.txt中。n P：打印表(TreePrint)。将已建立好的赫夫曼树的存储情况在终端以表格的形式罗列出来，使树的调用看起来更直观。n T：打印图(TreePrint)。将已建好的赫夫曼树以直观的图形在终端输出。 根据树的先序遍历算法，依次访问各个结点。 根据P打印出来的表，分析其所在的层次。 根据层次的大小，在终端输出相应长度的长条，来完成凹入表的输出。四、程序代码：#include<stdio.h> #include<stdlib.h>#include<string.h>typedef struct char 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 *,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(" n");printf(" 赫夫曼编/译码器 n");printf(" n");printf(" 08信息 <2> 赵思宇 n");printf(" n");doprintf("nnn");printf(" n");printf(" 操作菜单 n");printf(" n");printf(" I:初始化 (Initialization ) n");printf(" E:编 码 (Encoding ) n");printf(" D:译 码 (Decoding ) n");printf(" P:打印表 (PrintHufmFigue ) n");printf(" T:打印图 (TreePrint ) n");printf(" Q:退 出 (Initialization ) n");printf(" n");printf(" n");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!='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(HTNode); /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;i<=n;i+) fprintf(FhfmTreeP,"%c",HTi.elem);fputs(HCi,FhfmTreeP); fputs(style,FhfmTreeP); fclose(FhfmTreeP);printf("Every charactor has been coded and puted into E:hfmTree.txt!n");return;/-P147 算法6.12-void HuffmanCoding(int n) int i,m,s1,s2,start,c,f; /*weight存放n个字符的权值（均char *cd; >0），构造赫夫曼树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); /*在HT1.i-1选择parent为0HTs1.parent=i;HTs2.parent=i; 且weight最小的两个结点，其.HTi.lchild=s1;HTi.rchild=s2; 序号分别为s1,s2*/HTi.weight=HTs1.weight+HTs2.weight; /-从叶子到根逆向求每个字符的赫夫曼编码-HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /分配n个字符编码的头指针向量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) /从叶子到根逆向求编码 if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间strcpy(HCi,&cdstart);/从cd复制编码（串）到HCfree(cd);/释放工作空间return;/HuffanCoding/*函数功能：选出当前字符集中，两个最小值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.weight<HT(*s2).weight&&HTi.parent=0&&(*s2)!=0) if(HTi.weight<HT(*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<HT(*s1).weight) (*s2)=(*s1); (*s1)=i; else (*s2)=i; if(*s1)>(*s2) i=(*s1); (*s1)=(*s2); (*s2)=i; return; /*函数功能：将终端输入的字符串编译成用0/1表示的编码，并将相应信息存入TXT文档。 函数参数：temp1000,用于临时存储终端输入的字符串。 Code1000,用于存储0/1编码。 ToBeTran.txt,用于存储终端输入的字符串。 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");elsefputs(temp,FToBeTranP);fclose(FToBeTranP);TempLen=strlen(temp);for(i=0;i<TempLen;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=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; /-Decoding-void Decoding()int m,i,p=0;char q,*Decode,*Sentence;FILE* FDecodeP=NULL;if(NULL=(FDecodeP=fopen("E:CodeFile.txt","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=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");/* 函数功能：输出赫夫曼树中各结点的数据存储情况。 函数参数：无。函数返回值：无。*/void PrintHufmFigue()int i,m;char end='','0'printf("");printf("NumberElementWeightParentsLchildRchildHuffmanCode ");printf("");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("");m=2*n-1;for(i=n+1;i<=m-1;i+)printf("%6d%8c%6d%8d%8d%8d%20s",i,HTi.elem,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild,end);printf("");printf("%6d%8c%6d%8d%8d%8d%20s",m,HTm.elem,HTm.weight,HTm.parent,HTm.lchild,HTm.rchild,end);printf("");return;/*函数功能：将赫夫曼树以凹入表的形式在终端输出。函数参数： 无。函数返回值：无。*/void TreePrint()int MaxCode,MaxI=1,Floor,numb,i;numb=2*n-1;MaxCode=strlen(HC1);for(i=1;i<=n;i+)if(strlen(HCi)>MaxCode)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(w3<w2&&w2<w1)lay+;if(HTw.weight!=0)Visit(w,lay);if(HTw.lchild!=0)lay=diamonds-p;Turn(HTw.lchild,Visit);if(HTw.rchild!=0)q=-p;lay=diamonds-q;Turn(HTw.rchild,Visit);return;/-打印柱体-void putout(int lr,int count)for(;count>=1;count-)printf("");if(HTlr.lchild!=0)printf("%dn",HTlr.weight);elseprintf("%cn",HTlr.elem);printf("n");return;五、程序运行情况：I：初始化（Initialization）：图2. 输入I运行结果E：编码（Encoding）图3. 输入E运行结果D：译码（Decoding）图4. 输入D运行结果P：打印表（TreePrint）图5. 输入P运行结果图6. 输入P运行结果2 图7. 输入P运行结果3T：打印图（Initialization）图8. 输入T运行结果1 图9. 输入T运行结果2 图10. 输入T运行结果3分别打开htmTree.txt, CodeFile.txt，TxtFile.txt， ToBeTran.txt文件（如下图从上到下的顺序）查看内部存储信息均符合预期结果。 图11. 各文件的存储情况六、实验心得：经过此次课程设计，取获不少：1、 已基本形成了良好的编程思想。2、 基本能够将课堂中所学的算法及处理方法运用到实际的编程中。3、 编程讲究精益求精，在有限的时间尽量将程序完善的更好。