课程设计报告哈夫曼编码译码系统(树应用)

1、目录1. 课题简介（黑体小4）12. 设计方案1 3. 具体设计1 3.1 程序原理1 3.2关键代码段源码及分析2 4. 测试11 4.1测试过程中遇到的问题记录11 4.2测试结果11 5. 总结11 设计体会12 参考文献12 1 1. 实验目的数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法） 。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率， 它通常与一组算法的集合相对应，通过这组算法集

2、合可以对数据结构中的数据进行某种操作。在当今信息时代， 信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。 比如人们在外出工作时找最短路径，在银行查询存款、 通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、 计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、 编译原理及人工智能等的重要基础，广泛的应用于信息学、 系统工程等各种领域。

3、学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。 通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2 2. 课题简介. 问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间， 降低传输成本。 这要求

4、在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码 （复原）。 对于双工信道（即可以双向传输信息的信道） ，每端都需要一个完整的编/ 译码系统。试为这样的信息收发站编写一个赫夫曼码的编/ 译码系统。. 基本要求一个完整的系统应具有以下功能：(1) i ：初始化（ initialization） 。从终端读入字符集大小n，以及 n 个字符和n 个权值，建立赫夫曼树，并将它存于文件hfmtree 中。(2) e： 编码 （encoding） 。 利用已建好的赫夫曼树 （如不在内存，则从文件 hfmtree中读入） ，对文件 tobetran中的正文进行编码，然后将结果存入文

5、件codefile中。(3) d ：译码（ decoding） 。利用已建好的赫夫曼树将文件codefile 中的代码进行译码，结果存入文件textfile中。3. 设计方案1)问题分析哈夫曼树的定义1. 哈夫曼树节点的数据类型定义为：typedef struct /赫夫曼树的结构体char ch; int weight; /权值int parent,lchild,rchild; htnode,*hfmtree; 2）所实现的功能函数如下3 1、void hfmcoding(hfmtree &ht,hfmcode &hc,int n)初始化哈夫曼树，处理inputhuffman

6、(huffman hfm)函数得到的数据，按照哈夫曼规则建立2 叉树。此函数块调用了 select （）函数。2、void select(hfmtree &ht,int a,int *p1,int *p2) /select函数，选出 ht树到 a 为止，权值最小且parent 为 0 的 2 个节点 2 、 int main() 主函数： 利用已建好的哈夫曼树 （如不在内存， 则从文件 hfmtree.txt中读入）对文件中的正文进行编码，然后将结果存入文件codefile.txt中。如果正文中没有要编码的字符， 则键盘读入并存储到tobetran文件中。读入 tobetran中将要编

7、码的内容，将编码好的哈夫曼编码存储到codefile 中。3、encoding 编码功能：对输入字符进行编码4、decoding 译码功能： 利用已建好的哈夫曼树将文件codefile.txt中的代码进行译码， 结果存入文件 textfile.dat 中。 print() 打印功能函数：输出哈夫曼树，字符，权值，以及它对应的编码。 5.主函数的简要说明，主函数主要设计的是一个分支语句，让用户挑选所实现的功能。使用链树存储，然后分别调用统计频数函数，排序函数，建立哈夫曼函数，编码函数，译码函数来实现功能。2) 系统结构图（功能模块图）4 4. 具体设计源代码：#include #include

8、#include #include #include typedef struct /赫夫曼树的结构体char ch; int weight; /权值int parent,lchild,rchild; htnode,*hfmtree; typedef char *hfmcode; void select(hfmtree &ht,int a,int *p1,int *p2) /select函数，选出 ht树到 a 为止，权值最小且parent 为 0 的 2 个节点 int i,j,x,y; for(j=1;j=a;+j) if(htj.parent=0) x=j; break; for

9、(i=j+1;i=a;+i) if(hti.weighthtx.weight&hti.parent=0) x=i; /选出最小的节点 5 for(j=1;j=a;+j) if(htj.parent=0&x!=j) y=j; break; for(i=j+1;i=a;+i) if(hti.weighty) *p1=y; *p2=x; else *p1=x; *p2=y; void hfmcoding(hfmtree &ht,hfmcode &hc,int n) /构建赫夫曼树 ht ，并求出 n 个字符的赫夫曼编码hc int i,start,c,f,m,w; 6

10、 int p1,p2; char *cd,z; if(n=1) return; m=2*n-1; ht=(hfmtree)malloc(m+1)*sizeof(htnode); for(i=1;i=n;+i) /初始化 n 个叶子结点 printf(请输入第 %d字符信息和权值： ,i); scanf(%c%d,&z,&w); while(getchar()!=n) continue; hti.ch=z; hti.weight=w; hti.parent=0; hti.lchild=0; hti.rchild=0; for(;i=m;+i) /初始化其余的结点 hti.ch=0

11、; hti.weight=0; hti.parent=0; hti.lchild=0; hti.rchild=0; 7 for(i=n+1;i=m;+i) /建立赫夫曼树 select(ht,i-1,&p1,&p2); htp1.parent=i;htp2.parent=i; hti.lchild=p1;hti.rchild=p2; hti.weight=htp1.weight+htp2.weight; hc=(hfmcode)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char); cdn-1=0; for(i

12、=1;i=n;+i) /给 n 个字符编码 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); 8 strcpy(hci,&cdstart); free(cd); int main() char code100,h100,hl100; int n,i,j,k,l; ifstream input_file; /文件输入输出流ofstream output_fi

13、le; char choice,str100; hfmtree ht; hfmcode hc; coutn; cout 网工 12102班 q201217030221 李海霞 n; while(choice!=q&choice!=q) /当 choice 的值不为q 且不为 q时循环 cout *赫夫曼编码 / 译码器*n; cout i.init e.encoding d.decoding q.exitn; coutchoice; if(choice=i|choice=i) /初始化赫夫曼树 coutn; hfmcoding(ht,hc,n); for(i=1;i=n;+i) cou

14、thti.ch:hciendl; output_file.open(hfmtree.txt); if(!output_file) coutcant oen file!endl; return 1; for(i=1;i=n;i+) output_file(hti.chhci); output_file.close(); cout 赫夫曼树已经创建完毕，并且已经放入hfmtree.txt文件中!endl; else if(choice=e|choice=e) /进行编码，并将字符放入 tobetran.txt ，码值放入 codefile.txt中 printf(请输入字符： ); gets(st

15、r); output_file.open(tobetran.txt); if(!output_file) coutcant oen file!endl; return 1; 10 output_filestrendl; output_file.close(); output_file.open(codefile.txt); if(!output_file) coutcant oen file!endl; return 1; for(i=0;istrlen(str);i+) for(j=0;j=n;+j) if(htj.ch=stri) output_filehcj; break; output

16、_file.close(); coutn; cout 编码完毕，并且已经存入codefile.txt文件！ n; input_file.open(codefile.txt); /从 codefile.txt中读入编码，输出在终端if(!input_file) coutcant oen file!code; 11 cout 编码码值为： codeendl; input_file.close(); else if(choice=d|choice=d) /读入 codefile.txt中的编码进行译码，将译出来的字符放入textfile.txt中 input_file.open(codefile.t

17、xt); if(!input_file) coutcant oen file!h; input_file.close(); output_file.open(textfile.txt); if(!output_file) coutcant oen file!endl; return 1; k=0; while(hk!=0) /先用编码中的前几个和字符的编码相比较，然后往后移 for(i=1;i=n;i+) l=k; for(j=0;jstrlen(hci);j+,l+) hlj=hl; hlj=0; 12 if(strcmp(hci,hl)=0) output_filehti.ch; k=k+

18、strlen(hci); break; output_file.close(); input_file.open(textfile.txt); if(!input_file) coutcant oen file!h; couthendl; input_file.close(); cout 译码结束，字符已经存入textfile.txt文件中！ endl; else if(choice=q|choice=q) /退出程序 exit(0); else /如果选了选项之外的就让用户重新选择 cout 您没有输入正确的步骤，请重新输入！endl; coutendl; 13 return 0; 5. 测试5.1 测试过程中遇到的问题在程序测试过程中出现了很多的错误，有些是比较常见的语法错误，有些是头文件的问题， 就比如说 st