哈夫曼编译码器课程设计报告(完整版).doc

XXX学院本科数据结构课程设计总结报告 设计题目：实验一、哈夫曼编/译码器 学生姓名：XXX 系 别：XXX 专 业:XXX 班 级:XXX 学 号：XXX 指导教师:XXX XXX 2012年 6 月 21日xxx学院课 程 设 计 任 务 书题目 一、赫夫曼编译码器 专业、班级 xxx 学号 xxx 姓名 xxx 主要内容、基本要求、主要参考资料等：1. 主要内容利用哈夫曼编码进行信息通信可大大提高信道利用率，缩短信息传输时间，降低传输成本。要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）.对于双工信道(既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。2。 基本要求 系统应具有以下功能：（1）C：编码（Coding)。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中,将以此建好的哈夫曼树存入文件HuffmanTree中（2）D：解码(Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。(3)P：打印代码文件（Print)。将文件codefile以紧凑格式显示在终端上,每行50个代码.同时将此字符形式的编码文件写入文件codeprint中。（4）T：打印哈夫曼树（Tree Printing).将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上,同时将此字符形式的哈夫曼树写入文件treeprint中。3。 参考资料:数据结构（C语言版) 严蔚敏、吴伟民编著； 数据结构标准教程 胡超、闫宝玉编著完 成 期 限： 2012年6月21 日 指导教师签名： 课程负责人签名: 2012年 6月 21 日一、设计题目(任选其一）实验一、哈夫曼编/译码器二、 实验目的1巩固和加深对数据结构的理解，提高综合运用本课程所学知识的能力；2 深化对算法课程中基本概念、理论和方法的理解；3 巩固构造赫夫曼树的算法；4 设计试验用程序实验赫夫曼树的构造。 三、运行环境(软、硬件环境）Windows xp sp3,Visual C+ 6。0英文版四、算法设计的思想（1）初始化赫夫曼树，输入文件tobetrans。txt中各字符及其权值，并保存于hfmtree.txt文件中（2)编码（Coding)。对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中（3）D：解码(Decoding）。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入textfile中。（4)P：打印代码文件（Print）.将文件codefile以紧凑格式显示在终端上，每行50个代码.同时将此字符形式的编码文件写入文件codeprint中.(5）T：打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼树写入文件treeprint中。五、 流程图六、 算法设计分析1.赫夫曼树节点的数据类型定义为:typedef struct /赫夫曼树的结构体char ch;int weight; /权值int parent，lchild,rchild； HTNode,*HuffmanTree；2。 void HuffmanCoding(HuffmanTree ，char ，int *，int）；建立赫夫曼树的算法,此函数块调用了Select（）函数。void select（HuffmanTree HT，int j,int *x,int *y);从已建好的赫夫曼树中选择parent为0,weight最小的两个结点。3利用已建好的哈夫曼树从文件hfmtree。txt中读入,对文件中的正文进行编码，然后将结果存入文件codefile.txt中。4。 coding 编码功能:对输入字符进行编码5。 Decoding译码功能： 利用已建好的哈夫曼树将文件codefile。txt中的代码进行译码,结果存入文件textfile。txt 中。6。 Print（） 打印功能函数：输出哈夫曼树以及对应的编码。七、源代码/#include stdio.h#include #include string。h/定义赫夫曼树结点的结构体typedef struct char ch； /增加一个域,存放该节点的字符int weight; int parent，lchild,rchild；HTNode，*HuffmanTree；typedef char *HuffmanCode； /指向赫夫曼编码的指针void tips（）; /打印操作选择界面void HuffmanCoding（HuffmanTree &，char *，int ,int）； /建立赫夫曼树的算法void select（HuffmanTree HT,int j,int *x，int *y）； /从已建好的赫夫曼树中选择parent为0，weight最小的两个结点void Init（)； void Coding（); /编码void Decoding（）； /译码void Print_code(); /打印译码好的代码void Print_tree(）； /打印哈夫曼树int Read_tree（HuffmanTree &）; /从文件中读入赫夫曼树void find（HuffmanTree &HT,char code，char *text，int i,int m）； /译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree（unsigned char T100100，int s,int *i，int j）； /将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; /全局变量int n=0； /全局变量，存放赫夫曼树叶子结点的数目int main（)char select；while（1） tips(）; scanf(”%c，&select); switch(select) /选择操作，根据不同的序号选择不同的操作 case 1:Init();break； case 2:Coding();break; case 3：Decoding（）;break； case 4：Print_code(）;break； case 5：Print_tree（);break； case 0：exit(1); default ：printf(Input error！n”); getchar()；return 0;void tips(） /操作选择界面printf( -n）;printf( - 请选择操作 -n）;printf(” -n);printf（” n);printf( -1初始化赫夫曼树 -n”)；printf（ -2编码 -n）；printf（ -3译码 -n);printf(” -4打印代码文件 -n)；printf（ -5打印赫夫曼树 -n）；printf( -0退出 -n）;printf(” -n）;/初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树,并将其存于文件hfmtree中void Init(） FILE fp；int i,n，w52; /数组存放字符的权值char character52； /存放n个字符printf（n输入字符个数 n:”）；scanf（”d”，n）; /输入字符集大小printf(输入%d个字符及其对应的权值：n”，n）;for （i=0；in；i+) char b=getchar(）； scanf(%c”,&characteri）； scanf（”%d，wi)； /输入n个字符和对应的权值 HuffmanCoding(HT,character，w,n)； /建立赫夫曼树if（(fp=fopen（”hfmtree.txt”,”w）=NULL) printf(”Open file hfmtree.txt error！n）；for (i=1；i=2*n1；i+） if（fwrite（&HTi,sizeof（HTNode），1,fp）！=1) /将建立的赫夫曼树存入文件hfmtree。txt中 printf(”File write error！n”)；printf（”n赫夫曼树建立成功，并已存于文件hfmtree.txt中n)；fclose（fp）;/建立赫夫曼树的算法void HuffmanCoding（HuffmanTree HT，char *character，int *w，int n）int m,i，x,y;HuffmanTree p；if（n=1） return;m=2n1;HT=（HuffmanTree）malloc(（m+1）sizeof(HTNode)）；for(p=HT+1,i=1；ich=character；p-weight=w；pparent=0;p-lchild=0;p-rchild=0；for(；i=m;+i，+p） p-ch=0;pweight=0;p-parent=0;p-lchild=0;prchild=0;for(i=n+1；i=m;+i） select（HT,i1,x，&y）； HTx。parent=i；HTy。parent=i; HTi。lchild=x；HTi.rchild=y； HTi。weight=HTx.weight+HTy。weight;/从HT1到HTj中选择parent为0，weight最小的两个结点，用x和y返回其序号void select（HuffmanTree HT,int j，int x，int *y）int i;/查找weight最小的结点for (i=1；i=j；i+） if (HTi.parent=0) *x=i；break；for (;i=j;i+） if （HTi。parent=0）&（HTi.weightHTx。weight） *x=i; HT*x。parent=1；/查找weight次小的结点for (i=1；i=j；i+) if (HTi.parent=0） y=i;break；for （;i=j；i+） if (（HTi.parent=0）&（i!=x)&（HTi。weightHT*y。weight)） y=i;/对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中void Coding（) FILE *fp,*fw；int i,f，c,start；char *cd；HuffmanCode HC；if（n=0） n=Read_tree（HT)；/从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数/求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中HC=（HuffmanCode）malloc(（n+1）sizeof（char*);cd=(char *）malloc（nsizeof(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 cdstart=1； HCi=（char *)malloc（n-start)*sizeof(char)）; strcpy(HCi，cdstart)；free(cd);if(fp=fopen(”tobetrans。txt,rb）)=NULL） printf(Open file tobetrans。txt error！n”)；if（fw=fopen（”codefile。txt”,”wb+)=NULL） printf（Open file codefile。txt error!n);char temp；fscanf(fp，”c，&temp); /从文件读入第一个字符while（!feof（fp) for（i=1；i=n；i+） if（HTi。ch=temp） break； /在赫夫曼树中查找字符所在的位置 for（int r=0;HCir！=0;r+) /将字符对应的编码存入文件 fputc(HCir，fw）; fscanf（fp,”c,temp）； /从文件读入下一个字符fclose（fw）；fclose(fp）;printf(n已将文件hfmtree。txt成功编码,并已存入codefile.txt中！nn)；/将文件codefile中的代码进行译码，结果存入文件textfile中void Decoding() FILE fp，fw；int m，i;char code，*text,p; if(n=0) n=Read_tree(HT）；/从文件hfmtree.txt中读入赫夫曼树，返回叶子结点数if(fp=fopen（codefile.txt”，”rb）)=NULL) printf(Open file codefile。txt error!n)； if(fw=fopen(textfile。txt”，wb+”)=NULL） printf(Open file textfile.txt error!n）;code=（char *)malloc（sizeof(char);fscanf（fp,c，code)； /从文件读入一个字符for(i=1；！feof（fp）;i+) code=(char *）realloc(code,（i+1）sizeof(char）)； /增加空间 fscanf(fp,%c”,codei）； /从文件读入下一个字符 codei-1=0;/ codefile。txt文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100sizeof(char）；p=text； m=2n1;if（*code=0) find(HT，code,text，HTm。lchild，m); /从根节点的左子树去找else find（HT，code，text,HTm.rchild，m）; /从根节点的右子树去找 for（i=0；pi!=0;i+） /把译码好的字符存入文件textfile.txt中 fputc（pi,fw);fclose（fp);fclose(fw);printf(”n已将codefile。txt文件成功译码，兵已存入textfile。txt文件!nn）;/将文件codefi1e以紧凑格式显示在终端上，每行50个代码.同时将此字符形式的编码文件写入文件codeprint中。void Print_code(）FILE *fp，*fw；char temp;int i; if(fp=fopen(codefile.txt，”rb”）)=NULL） printf（”Open file codefile.txt error！n”）;if(（fw=fopen(”codeprint.txt”,wb+）)=NULL) printf（”Open file codeprint.txt error!n）；printf(”n文件codefi1e显示如下:n”）;fscanf(fp,%c”，temp）； /从文件读入一个字符for (i=1；！feof(fp）;i+） printf（c，temp）; if（i50=0） printf(n）; fputc（temp，fw)； /将该字符存入文件codeprint.txt中 fscanf（fp,c,temp); /从文件读入一个字符printf(”nn已将此字符形式的编码写入文件codeprint.txt中!nn）；fclose（fp);fclose(fw)；/将已在内存中的哈夫曼树显示在屏幕上,并将此字符形式的哈夫曼树写入文件treeprint中。void Print_tree（）unsigned char T100100；int i，j,m=0；FILE *fp;if（n=0） n=Read_tree(HT)； /从文件hfmtree。txt中读入赫夫曼树，返回叶子结点数Convert_tree（T,0,m,2*n1)； /将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if（fp=fopen(”treeprint。txt”,”wb+”）)=NULL) printf(”Open file treeprint.txt error!n）; printf(n打印已建好的赫夫曼树：n”）;for(i=1;i=2*n1；i+） for (j=0；Tij!=0；j+） if（Tij= ） printf（ );fputc(Tij,fp)； else printf（”d”，Tij）；fprintf（fp，”%dn,Tij）； printf(”n);fclose(fp);printf(n已将该字符形式的哈夫曼树写入文件treeprint.txt中!nn”）;/从文件hfmtree。txt中读入赫夫曼树，返回叶子节点数int Read_tree（HuffmanTree HT) FILE *fp;int i，n;HT=(HuffmanTree)malloc(sizeof（HTNode)）; if（(fp=fopen（hfmtree.txt,r”）)=NULL） printf(Open file hfmtree.txt error！n)；for （i=1;!feof(fp）;i+） HT=(HuffmanTree)realloc（HT，（i+1）sizeof（HTNode)）; /增加空间 fread(&HTi,sizeof(HTNode)，1,fp）; /读入一个节点信息fclose（fp);n=（i1)/2；return n;/译码时根据01字符串寻找相应叶子节点的递归算法void find（HuffmanTree HT，char code,char text,int i,int m）if(*code！=0） /若译码未结束 code+； if（HTi。lchild=0&HTi.rchild=0） /若找到叶子节点 text=HTi。ch； /将叶子节点的字符存入text中 text+； if(*code=0） find(HT，code,text,HTm.lchild,m）; /从根节点的左子树找 else find（HT，code，text,HTm。rchild，m）； /从根节点的右子树找 else /如果不是叶子节点 if(*code=0) find（HT,code，text,HTi。lchild,m)； /从该节点的左子树去找 else find（HT,code，text，HTi。rchild，m）； /从该节点的右子树去找else text=0; /译码结束/将文件中的赫夫曼树转换成凹凸表形式的赫夫曼树打印出来void Convert_tree（unsigned char T100100,int s,int *i，int j）int k,l；l=+(*i）；for(k=0；ks；k+) Tlk= ;Tlk=HTj.weight；if（HTj。lchild） Convert_tree（T,s+1，i，HTj。lchild)；if(HTj。rchild) Convert_tree（T,s+1，i，HTj。rchild)； Tl+k=0；/八、运行结果分析截图说明：1、运行后界面如图（1）：图(1）选择要选择的操作序号可以运行各个步骤；2、初始化赫夫曼树:输入tobetrans.txt中各元素及其出现频率，如图（2）图(2）3、编码及译码，如图(3)图(3)4、打印编码文件，如图（4）图（4）5、打印赫夫曼树,如图（5）图（5）6、各步骤所存的文件内容如图(6)图（6)九、收获及体会课程设计是让我们充分利用我们专业课程所学知识的机会,也是我们迈向社会，从事工作前一个必不少的过程。通过这次课程设计，我深深体会到将知识运用到实践中的重要作用。我这两天的课程设计，是让我学会脚踏实地迈开这一步,也是为明天能稳健地在社会大潮中奔跑打下坚实的基础。我的课程设计题目是赫夫曼编译码器.最初做这个程序的时候，让我觉得完成这次程序设计真的是太难了，然后我查阅了课本，并去图书馆借了资料,在写这个程序的时候也参考了网上的设计流程,写完刚运行时出现了很多问题。尤其是编码错误，导致内存无法read,通过同组人员的交流请教，逐渐明白过来，然后经过不知道多少次修改才顺利运行。本次试验也让我明白了理论与实际相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。 通过对各个步骤各个流程的控制，逐渐让我产生了兴趣，在实际编写过程中，和同学们相互讨论让我学到的不仅仅是一些解决问题的方法,更是解决问题的思想.课程设计本身也是一种相互学习的过程，/ #include #include stdlib.h /为exit（)提供原型include 0），构造哈夫曼树HTint m， i， x, y;HuffmanTree p;if (n = 1) return；m = 2 * n - 1；HT = (HuffmanTree)malloc（m + 1) sizeof(HTNode); for (p = HT + 1， i = 1; i = n； +i， +p， +character， +w）p-ch = character; pweight = w; pparent = 0； p-lchild = 0； prchild = 0；for （; i = m; +i， +p)