哈夫曼(huffman)编译码器课程设计

1兰州商学院陇桥学院工学系课程设计报告设计题目：哈夫曼（huffman）编译码器系别：专业(方向)：年级、班：学生姓名：学生学号：指导教师：年月日2目录哈夫曼(huffman)编译码器..........................................................................................3一、编译码器开发的背景..........................................................................................3二、系统的分析与设计................................................................................................3（一）系统功能要求.............................................................................................3（二）系统模块结构设计.....................................................................................4三、系统的设计与实现................................................................................................6（一）main().........................................................................................................6（二）运算.............................................................................................................71.权值运算quanzhi().................................................................................72.印二叉树函数huffmantree()...............................................................73.编译码运算huffmancode().......................................................................94.输出运算shuchu()..................................................................................9四、系统测试..............................................................................................................10（一）测试主函数...............................................................................................10（二）测试印二叉树函数...................................................................................10（三）测试译码运算函数.................................................................................11五、总结......................................................................................................................12六、附件（代码、部分图表）..................................................................................133哈夫曼(huffman)编译码器一、编译码器开发的背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。二、系统的分析与设计（一）系统功能要求一个完整的系统应具有以下功能：1)I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。2)E：编码（Encoding）。利用以建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3)D：译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。4)P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在4终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。5)T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。（二）系统模块结构设计通过对系统功能的分析，哈夫曼（huffman）编译码器功能如图（1）所示。图（1）哈夫曼（huffman)编译码器功能图通过上图的功能分析，把整个系统分为四个模块：1.初始化模块，该模块主要实现：输入二叉树的结点数，以及要加密的句子，建立哈夫曼树。2.输出二叉树模块，该运算模块主要实现：将输入的字符串中每初始化输出二叉树编译码输出代码选择操作哈夫曼（huffman）编译码器5个字符出现的次数当作权值，建立二叉树，将二叉树的parent,weight,lchild,rchild输出。3.译码模块，该操作主要实现：对编码后的代码进行译码，然后输出。4.输出模块，该操作主要进行表头的输出。图２流程图开始用户选择y=1y=2y=3建立二叉树，输出二叉树输入叶子节点数对输入的句子进行编码结束否否是输入句子退出系统输出每个字符的编码6三、系统的设计与实现（一）main()输出1.输出二叉树操作2.进行输出二叉树操作3.退出编译码操作系统，并让用户选择所进行的操作，对其调用。该模块的具体代码如下所示：voidmain(){inti,n,s=1;hnodetypehuffnode[maxnode];while(s){shuchu();scanf(%d,&i);switch(i){case1:{haffmantree(huffnode,&n);break;}case2:{haffmancode();break;}case3:s=0;break;}}}分析：首先输出一个主菜单，方便用户进行操作，用switch语句调用函数使用户对其进行选择要执行的操作（1.输出二叉树操作，2.进行编译码操作，3.退出程序）。7（二）运算该模块的具体代码如下所示：1.权值运算quanzhi()分析：此函数用于对一串字符进行求权值运算，利用循环将一串字符中每个字符的个数设定为权值。voidquanzhi(intt[maxleaf],chars[maxleaf],intn)//求权值函数，将句子中的字符出现的个数当作权值{inti,j,h;for(i=0;in;i++){for(j=0;jn;j++)if(s[i]==s[j])h++;t[i]=h;}}2.印二叉树函数huffmantree()voidhaffmantree(hnodetypehuffnode[maxnode],int*m){inti,j,n,k;intm1,m2,x1,x2;chars[maxleaf],t[maxleaf];printf(输入叶子结点个数：);scanf(%d,&n);for(i=0;i2*n-1;i++)//数组huffnode[]初始化{huffnode[i].weight=0;huffnode[i].parent=-1;huffnode[i].lchild=-1;huffnode[i].rchild=-1;}printf(输入要编译的句子的\n);8for(i=0;in;i++){printf(第%d个结点,i+1);scanf(%d,&huffnode[i].weight);getchar();}printf(印二叉树：\n);for(i=0;in;i++){quanzhi(t,s,n);k=huffnode[i].weight;}for(i=0;in-1;i++){//构造哈夫曼树m1=m2=maxvalue;x1=x2=0;for(j=0;jn+i;j++){//选取最小和次小两个权值if(huffnode[j].parent==-1&&huffnode[j].weightm1){m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;}elseif(huffnode[j].parent==-1&&huffnode[j].weightm2){m2=huffnode[j].weight;x2=j;}}//将找出的两棵子树合并为一颗子树huffnode[x1].parent=n+i;huffnode[x2].parent=n+i;huffnode[n+i].weight=huffnode[x1].weight+huffnode[x2].weight;huffnode[n+i].lchild=x1;huffnode[n+i].rchild=x2;}for(i=0;i2*n-1;i++){printf(%4d,k);printf(%4d,huffnode[i].lchild);printf(%4d,huffnode[i].rchild);9printf(%4d\n,huffnode[i].parent);}*m=n;}3.编译码运算huffmancode()voidhaffmancode(){hnodetypehuffnode[maxnode];hcodetypehuffcode[maxleaf],cd;inti,j,c,p,n=0;haffmantree(huffnode,&n);for(i=0;in;i++){cd.start=n-1;c=i;p=huffnode[c].parent;while(p!=-1){if(huffnode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=huffnode[c].parent;}for(j=cd.start+1;jn;j++)huffcode[i].bit[j]=cd.bit[j];huffcode[i].start=cd.start;}for(i=0;in;i++){printf(第%d个译码为：,i+1);for(j=huffcode[i].start+1;jn;j++)printf(%4d,huffcode[i].bit[j]);printf(\n);}}4.输出运算shuchu()voidshuchu(){10printf(*****