软件设计译码器

《软件设计译码器》由会员分享，可在线阅读，更多相关《软件设计译码器（23页珍藏版）》请在装配图网上搜索。

1、湖南商学院计算机软件设计课程设计(实习)报告题目 哈夫曼编/译码器 姓 名: 学 号: 专 业: 班 级: 指导教师: 职 称:计算机与电子工程学院2011年11月课程设计(实习)评审表姓 名 学 院计算机与电子工程学院 学 号 专业班级 题 目 哈夫曼编/译码器评审意见评审成绩指导教师签名职称评审时间 年 月 日课程设计(实习)作品验收表题目 哈夫曼编/译码器参与人员姓 名 班 级 学 号 设计任务与要求： 设计哈夫曼编/译码器系统，实现编码、译码功能。作品完成情况： 成功运行，实现了编码译码功能。 验收情况： 验收教师签名：_ 年 月 日注：1. 除“验收情况”栏外，其余各栏均由学生在作品

2、验收前填写。2. “验收情况”栏由验收小组按实际验收的情况如实填写。目录1 课程设计任务与要求 11.1 课程设计任务11.2 问题分析12 系统总体设计42.1总体设计思想、设计方案的选择52.2 系统结构图53 系统详细设计53.1 确定所需模块53.2 各子模块功能描述53.3 模块间调用关系54 系统实现与测试54.1系统测试用例的设计54.2系统测试结果65 课程设计总结6参考文献6附录6哈夫曼编/译码器1 课程设计任务与要求 1.1 课程设计任务此次课程设计要求设计一个哈夫曼编/译码器，实现如下功能：一、在本程序中，用户通过键盘进行人机交互，可以在键盘上输入字符集大小，字符可以出现

3、重码，字符输入顺序不受限制。二、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。 三、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。 四、在本程序中，用户对给定的原字符串进行编码，对给定的编码串进行译码。 1.2 问题分析哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则

4、编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。分析此次设计，是关于实现利用哈夫曼算法编码和译码功能的问题，要求能重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。2 总体设计2.1总体设计思想、设计方案的

5、选择 哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。 2.1.1建立模型2.1.2数据结构a. typedef struct int weight; int parent,lchild,rchild; HTNode,* HuffmanTree;

6、 /动态分配数组存储赫夫曼树 typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表b. int min(HuffmanTree t,int i) / -求赫夫曼编码-c. void select(HuffmanTree t,int i,int &s1,int &s2) /-slect函数-d. void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/ w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCe. void Initialization() /-初始化赫

7、夫曼链表-f. void InputCode() /-获取报文并写入文件-g. void Encoding() /-编码函数-h. void Decoding() /-译码函数-i. void Code_printing() /-打印编码的函数-j. void coprint(HuffmanTree start,HuffmanTree HT) /-打印赫夫曼树的函数-k. void main() /-主函数-2.2 系统结构图 main()Initialization（）初始化函数Input()输入待编码字符函数Encoding（）编码函数Decoding（）译码函数Code_printing

8、()打印编码函数Tree_printing()打印哈夫曼树图2.2 哈夫曼编/译码器结构框图3 详细设计3.1 确定所需模块 一个完整的系统应具有以下功能模块： I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。 W：输入（Input）。从终端读入需要编码的字符串s，将字符串s存入文件Tobetran.txt中。 E：编码（Encoding）与译码（Decoding）。编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBe

9、Tran中的正文进行编码，然后将结果存入文件CodeFile中。译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。打印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。 T：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 Q：退出程序。返回WINDOWS界面。3.2 主要子模块功能描述3.2.1初始化模块算法程序从文件abc

10、.txt中自动获取26个英文字母的权值。3.2.2编码算法 a.对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值w1,w2,，wN构成n棵二叉树的集合F=T1,T2,，Tn把它们保存到结构体数组HTn中,其中Ti是按它们的ASC码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。 b.在HT1.i中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。 c.哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。 3.2.3译码算法 译码的过程

11、是分解电文中字符串，从根出发，按字符0,或1确定找左孩子或右孩子，直至叶子结点，便求的该子串相应字符并输出接着下一个字符。4 系统实现与测试4.1系统测试用例的设计 此次测试举例为对输入的英文HAPPYNEWYEAR应用创建的哈夫曼编译码器进行编码再译码。声明：程序预先将Huffman编码解码所需的26个字母和权值保存在根目录下的abc.txt文件下。a.按照程序提示输入i对Huffman进行初始化。b.初始化后程序对abc.txt文件中的数据进行读取并运行编码函数进行哈夫曼编码。然后将字母、权值和哈夫曼编码存在根目录下的htmTree.txt文件中。在屏幕显示出字符、权值、编码。c.输入w进

12、入待编码字符输入窗口，并键入字符串（注意单词间无空格）“happynewyear”。 d.可以看出所获得的字符串已经存入根目录下的tobetran.txt文件中。 e.输入e进行编码、译码和打印编码功能。f.输入t打印哈夫曼树。g.输入q退出程序。4.2系统测试结果5 课程设计总结通过这次课程设计使我充分的理解了哈夫曼编译码问题的基本原理，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编译码程序。虽然这个程序不是最好的，但是总体还是一个比较能体现数据结构知识点能力的程序，当然只是相对于我这个初学者来说。在刚开始编程的时候，我感到很茫然，无从下手，很多细节没有注意，特别是在

13、编写格式和符号代码上，曾多次编译出错。但是困难是可以解决的，只要通过努力，虚心学习请教，再难的题目也可以自己动手完成。通过这次的数据结构课程设计，我也深刻了解到这门学问的博大精深，要积极进取，不断学习，不断积累知识。同时我也认识到自己的不足和缺点，做什么事都需要细心和耐心，并坚持下去，这样才能有一个比较满意的结果。6 软件使用说明书参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M

14、北京：中国铁道出版社，2003附录 #include #include #include #include #include #include #include const int UINT_MAX=10000;typedef struct int weight; int parent,lchild,rchild;HTNode,* HuffmanTree; typedef char *HuffmanCode; HuffmanTree HT;HuffmanCode HC;int *w,i,j;const int n=26;char *z;int flag=0;int numb=0;int min

15、(HuffmanTree t,int i) int j,flag; int k=UINT_MAX; for(j=1;j=i;j+) if(tj.weights2) j=s1; s1=s2; s2=j; void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1

16、,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i

17、+) 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); strcpy(HCi,&cdstart); free(cd); void Initialization() flag=1; int num2; cout下面初始化哈夫曼链表endl; w=(int*)malloc(n*sizeof(int); z=(char*)malloc(n*sizeof(char); c

18、outn依次显示n个字符与其权值和编码nendl; char base2;/?ifstream fin(abc.txt); for(i=0;ibase; *(z+i)=*base;/? finnum2; *(w+i)=num2; HuffmanCoding(HT,HC,w,n); cout字符setw(6)权值setw(11)编码endl; for(i=1;i=n;i+) coutsetw(3)*(z+i-1); coutsetw(6)*(w+i-1)setw(12)HCiendl; cout下面将哈夫曼编码写入文件endl.endl; FILE *htmTree; char r= ,0; i

19、f(htmTree=fopen(htmTree.txt,w)=NULL) cout不能打开文件 endl; return; for(i=0;in;i+) fputc(*(z+i),htmTree); fputs(r,htmTree); for(i=0;in;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout已将字符与对应编码写入根目录下文件htmTree.txt中endlendl;void Inp

20、utCode() FILE *tobetran; char str100; if(tobetran=fopen(tobetran.txt,w)=NULL) cout不能打开文件endl; return; cout请输入你想要编码的字符endl; gets(str); fputs(str,tobetran); cout获取报文成功endl; fclose(tobetran);cout.endl报文存入根目录下的tobetran.txt文件中endl;void Encoding() cout下面对目录下文件tobetran.txt中的字符进行编码endl; FILE *tobetran,*code

21、file; if(tobetran=fopen(tobetran.txt,rb)=NULL) cout不能打开文件endl; if(codefile=fopen(codefile.txt,wb)=NULL) cout不能打开文件endl; char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) cout不能打开文件endl; break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) cout字符错误，无法编码!endl;

22、 break; cout编码完成endl;cout编码写入目录下的codefile.txt中endlendl; fclose(tobetran); fclose(codefile); free(tran);void Decoding() cout下面对根目录下文件codefile.txt中的字符进行译码endl; FILE *codef,*txtfile; if(txtfile=fopen(Textfile.txt,w)=NULL) cout不能打开文件endl; txtfile=fopen(Textfile.txt,w); if (codef=fopen(codefile.txt,r)=NU

23、LL) cout不能打开文件endl; codef=fopen(codefile.txt,r); char *work,*work2,i2; int i4=0,i,i3; unsigned long length=10000; work=(char*)malloc(length*sizeof(char); fgets(work,length,codef); work2=(char*)malloc(length*sizeof(char); i3=2*n-1; for(i=0;*(work+i-1)!=0;i+) i2=*(work+i); if(HTi3.lchild=0) *(work2+i4

24、)=*(z+i3-1); i4+; i3=2*n-1; i-; else if(i2=0) i3=HTi3.lchild; else if(i2=1) i3=HTi3.rchild; *(work2+i4)=0; fputs(work2,txtfile); cout译码完成endl;cout内容写入根目录下的文件textfile.txt中endlendl; free(work); free(work2); fclose(txtfile); fclose(codef); void Code_printing() cout下面打印根目录下文件CodePrin.txt中编码字符endl; FILE

25、* CodePrin,* codefile; if(CodePrin=fopen(CodePrin.txt,w)=NULL) cout不能打开文件endl; return; if(codefile=fopen(codefile.txt,r)=NULL) cout不能打开文件endl; return; char *work3; work3=(char*)malloc(51*sizeof(char);if(fgets(work3,51,codefile)=NULL) cout不能读取文件endl; else do fputs(work3,CodePrin); puts(work3); while(

26、strlen(work3)=50&fgets(work3,51,codefile)!=NULL); free(work3); cout打印结束endlendl; fclose(CodePrin); fclose(codefile);void coprint(HuffmanTree start,HuffmanTree HT) if(start!=HT) FILE * TreePrint; if(TreePrint=fopen(TreePrint.txt,a)=NULL) cout创建文件失败rchild,HT); coutsetw(5*numb)weightweight); coprint(HT

27、+start-lchild,HT); numb-; fclose(TreePrint); void Tree_printing(HuffmanTree HT,int w) HuffmanTree p; p=HT+w; cout下面打印哈夫曼树endl; coprint(p,HT); cout打印工作结束endl;void main() coutendl; cout 此程序实现哈夫曼编码解码功能 endl; char choice; while(choice!=q) coutn*endl; cout 哈夫曼编码解码 endl; cout* endl; cout(i)初始化哈夫曼表 endl; c

28、out(w)输入待编码的字符 endl; cout(e)进行编码、译码、打印编码 endl; cout(t)打印哈夫曼树 endl; cout(q)离开 endl; if(flag=0)coutn请先初始化哈夫曼链表,输入iendl;cout(程序将从根目录下的abc.txt文件中读出26个字母及其权值并对字母进行编码)choice; switch(choice) case i: Initialization(); break; case w: InputCode(); break; case e: Encoding(); Decoding(); Code_printing(); break; case t: Tree_printing(HT,2*n-1); break; case q: break; default: cout输入命令错误 endl; free(z); free(w); free(HT);