1、哈夫曼编译码实验报告实验三 使用二叉链表实现二叉树的存储验证和设计相关算法题目：编制一个哈夫曼编码和译码程序班级：计科0603 姓名：李汉刚 学号：20064140303 完成日期：2008-5-23一、实验目的1、掌握树、森林和二叉树的概念和它们的特性以及它们之间是怎样相互转换的，理解二叉树的三种遍历：先序遍历、中序遍历和后序遍历，和树的两种遍历：先序遍历和后序遍历。2、理解二叉树的基本运算算法实现以及它的非递归运算算法和层次遍历算法，了解二叉树的线索化及其它的应用。3、掌握树和二叉树的几种存储结构以及它的构造，学会使用二叉链表实现二叉树的存储验证和设计相关算法。二、实验环境1、操作系统：W
2、indows XP2、编程环境：VisualC+6.0或者Dev-Cpp三、实验内容1、建立一棵哈夫曼编码树，数据的输入和输出，采用文件操作。文件内容：输入文件为字符和频度,文件名input.txt。 A 0.3 B 0.2 C 0.05 D 0.05 E 0.1 F 0.3输出文件为编码文件，格式如下，文件名output.txt。A 10 B 00 C 0110 D 0111 E 010 F 112、编码指定字符串，请输入一个字符串：ABFEDEFAD 输出码流：1000110100111010111001113、译码指定码流为字符串，请输入一个码流：110101*100I11输出字符串：F
3、EAEEBABD4、编码结果以文本方式存储在文件中，用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“0”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择“0”为止。5、数据测试(后面运行结果)。四、实验步骤(一)、概要设计利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信心传输时间，降低传输成本。但是，这要求在发送器端通过一个编码系统对待传输数据预先编码，在接受端将传来的数据进行译码(复原)。对于双工信道(即可以可以双向传输信息的通道)，每端都需要一个完整的编/译码系统。1、抽象数据类型定义如下：ADT Huffman数据对象：D=
4、ai | 1in，n0，ai 属ElemType类型数据关系：R=| ai，ajD，1in，1jn，其中每个元素只有已过去前驱，可以有零个和多个后继，有且只有一个元素没有前驱基本运算：Inithuffman(t,n)：初始化哈夫曼树：建立一棵哈夫曼树t。Createhcode(t, hcd, n)：对建立哈夫曼树进行编码并储存在数组hcd中。Encoding(t,hcd,n)：将字符进行编码。Decoding(t,hcd,n)：将码流进行译码。Readhuffman(t)：读取哈夫曼树的数据。Writehuffman(savecode,save)：存储savecode,save数组中哈夫曼编码
5、的数据。2、主程序int main（）初始化哈夫曼树 ; for( ; ; )switch (返回菜单函数代码)case 1: 建立哈夫曼编码 ; break ;case 2: 输出哈夫曼编码 ; break ;case 3: 编码 ; break ;case 4: 译码 ; break ;case 0: 退出 ;default : 输入菜单代码有误，请重新输入 ; break ;return 0 ;3、模块间调用流程图主函数模块 初始化函数模块读取文件中数据 菜单1：建立哈夫曼树编码2：输出哈夫曼树编码3：编码4：译码0：退出 菜单代码 1 2 3 4 0退出译码函数模块编码函数模块输出编码
6、函数模块建立编码函数模块 模块流程图(二)、详细设计1、头文件定义及预定义#include#include#include#define W 6#define N 50#define M 100#define V 10002、定义数据类型typedef struct /*定义哈夫曼树类型*/char data ; /*结点值*/float weight ; /*频度*/int parent ; /*双亲点*/int lchild ; /*左孩子结点*/int rchild ; /*右孩子*/Hufffman ;typedef struct /*定义存放哈夫曼编码类型*/char cd N ;
7、/*存放当前结点的哈夫曼码*/int start ; /*cd start cd n存放哈夫曼码*/Hcode ;Huffman tM; /定义一个哈夫曼树类型数组Hcode hcdV; /定义一个哈夫曼编码类型数组3、函数声明char menu() ; /*声明菜单函数*/void Inithuffman(Huffman t,int n); /*声明初始化哈夫曼树*/void Createhcode(Huffman t,Hcode hcd,int n); /*声明建立哈夫曼树编码*/void Printhuffman() ; /*输出哈夫曼树编码*/void Encoding(Huffman
8、 t,Hcode hcd,int n) ; /*声明编码函数*/void Decoding(Huffman t,Hcode hcd,int n) ; /*声明译码函数*/void Readhuffman(Huffman t) ; /*声明读取数据函数*/void Writehuffman(char savecodeWW,char save) ; /*声明存储编码数据函数*/4、函数定义void Inithuffman(Huffman t,int n) /定义初始化哈夫曼树 int i,k,lnode,rnode; /定义临时变量 float min1,min2; Readhuffman(t);
9、 /读取数据 for(i=0;i2*n-1; i+) ti.parent=ti.lchild=ti.rchild=-1; /初始化结点相关域置处置为-1 for(i=n;i2*n-1; i+) min1=min2=1.0; /lnode和rnode为最小频度的两个结点位置 lnode=rnode=-1; for(k=0; k=i-1;k+) /在h中找权值最小的两个结点 if(tk.parent= =-1) /在尚未构造的二叉树的结点中查找 if(tk.weightmin1) /在t树中找到最小频度的两个结点 min2=min1; rnode=lnode; min1=tk.weight; ln
10、ode=k; else if(tk.weightmin2) min2=tk.weight; rnode=k; ti.weight=tlnode.weight+trnode.weight; /将两个最小频度结点的频度相加构成一个新的结点的频度， ti.lchild=lnode; /新结点作为它们的双亲节点; ti.rchild=rnode; tlnode.parent=i; trnode.parent=i; void Createhcode(Huffman t,Hcode hcd,int n) /定义建立哈夫曼树编码函数 int i,j,k,s,f,c; /定义临时变量; Hcode hc; c
11、har saveW,savecode1W; char savecode2WW=0; for(i=0; i=0;s-,j+) savecode2ij=savecode1s; /将码流放入到一个二维字符数组中 savei=ti.data; /将字符放到一个一维数组中 printf(哈夫曼编码已建立成功n); Writehuffman(savecode2,save); /将编码写入到输出文件中; printf(please enter any key to continue. ); getch(); system(cls);void Printhuffman() /输出哈夫曼树编码 int i=0;
12、 char saveW; char savecodeWW; FILE *fp; /定义一个文件指针*fp; fp=fopen(output.txt,r); /打开文件if(fp= =NULL) printf(找不到文件!n); return; printf(哈夫曼编码:n); while(!feof(fp) fscanf(fp,%c %sn,&savei,&savecodei); /读取该文件的数据 printf(%c %sn,savei,savecodei); /将数据输出到终端显示屏上; i+; ; fclose(fp); /关闭文件void Encoding(Huffman t,Hcod
13、e hcd,int n) /定义编码函数 char codeV,saveV; int i=0,j,k,s,f,c; Hcode hc; int sign=0; /标记字符是否是可编码，1为可编码 Printhuffman(); /调用输出哈夫曼编码函数 printf(请输入一个字符串:); scanf(%s,code);/输入字符 printf(输出码流:); while(codei!=0) /找到每个字符所对应的结点; for(j=0;j=0;s-) /输出编码 printf(%c,saves); if(j= =n&sign= =0) printf(无); i+; sign=0; print
14、f(nplease enter any key to continue.); getch(); system(cls);void Decoding(Huffman t,Hcode hcd,int n) /定义译码函数 char codeV; int i=0,k; Printhuffman(); /调用输出哈夫曼编码函数 printf(请输入一个码流:); /输入编码 scanf(%s,code); k=2*n-2; /指向头结点 while(codei!=0) /直到编码编译完 if (codei= =0) k=tk.lchild; /指向当前结点的左孩子 else if(codei= =1)
15、 k=tk.rchild; /指向当前结点的右孩子 else printf(无); k=2*n-2; /重新指向头结点 if (tk.data) /该结点有值 printf(%c,tk.data); /则该段编码能成功译码 k=2*n-2; /重新指向头结点 i+; if(!tk.data&k!=2*n-2) printf(无); printf(nplease enter any key to continue.); getch(); system(cls);void Readhuffman(Huffman t) /定义读取数据函数 int i=0; FILE *fp; /定义一个文件指针*f
16、p; fp=fopen(input.txt,r); /打开文件 if(fp= =NULL) printf(初始化文件出错，找不到文件!n); printf(please enter any key to continue.); getch(); exit(0); while(!feof(fp) fscanf(fp,%c %fn,&ti.data,&ti.weight); /读取该文件的数据 i+; ; fclose(fp); /关闭文件 void Writehuffman(char savecodeWW,char save) /定义存储字符编码函数 int i; FILE *fp; /定义一个
17、文件指针*fp if(fp=fopen(output.txt,w)= =NULL) /将文件打开 printf(cannot open filen); return; for(i=0;iW;i+) fprintf(fp,%c %sn,savei,savecodei); /将数据写入到文件中 fclose(fp); /关闭该文件int menu() /声明菜单函数 int x; printf(*nnnn); printf(ttt哈夫曼编(译)码系统nnn); printf(tt 1: 建立哈夫曼编码n); printf(tt 2: 输出哈夫曼编码n); printf(tt 3: 编码n); pr
18、intf(tt 4: 译码n); printf(tt 0: 退出nnn); printf(tt 请输入你的选择(04):); scanf(%d,&x); system(cls); return x;int main() Inithuffman(t,W); /初始化哈夫曼树 for( ; ; ) switch (menu() case 1: Createhcode(t,hcd,W); break ; case 2: Printhuffman();printf(please enter any key to continue.); getch();system(cls); break ; case
19、 3: Encoding(t,hcd,W); break ; case 4: Decoding(t,hcd,W); break ; case 0: exit(0); default : printf(输入菜单代码有误，请重新输入n); break ; return 0; 5、函数调用关系图mainInithuffmanReadhuffmanmenuEncodingDecodingCreatehcodePrinthuffmanWritehuffman函数调用图五、程序调试1、实验最开始出现错误的地方是在菜单函数，最初用的是用返回字符作为菜单码。在输入字符后，按回车的同时多输入了一个字符 n，相当
20、于连续输入两个字符，这样导致在选择实现功能时调用不正确。最后把菜单码换成整型，这样就避免了调用错误。2、读取文件，在读取频度ti.weight时，因为它是浮点类型数据，所以不能用fread函数来读取。然后用fscanf（fp, “%c %f”,&ti.data,&ti.weight）函数来读取浮点类型数据，同时又遇到了一个问题，float类型和double类型的区别，最开始用的是double类型来定义频度的，所以在读取数据时读不出来，调试了好几次，试着把double类型换成float类型，这样却能读取数据。3、在创建编码和编码的过程中，遇到了一些编码的问题，编出来的码流和预计的恰好相反，在接受
21、码流的时候要逆序，因为每个字符的编码是逆序编码的。还有在译码的过程中也犯了一点错误，当码流为字符 0时, if (codei= =0)写成了if (codei= =0)，这样导致了所有译过来的字符都是F，主要是因为是0而不是0，所以没有执行该语句，这样导致译码不正确。4、当循环到根节点的时候编码结束，用while(f!=-1)来结束，把它写成了while(f= =-1)，这样导致不是到根节点结束从而编码错误。5、在输出字符到显示屏幕上时也犯了一点错误，把printf(“%s”,.)写成了printf(“s%”,.)，这样导致的结果是输出的是ssss而不是码流。六、实验结果1、哈夫曼编(译)码系
22、统的主界面：2、建立哈夫曼编码：3、输出哈夫曼编码：4、编码：5、译码：七、实验总结本次实验的目的是学会使用二叉链表实现二叉树的存储验证和设计相关算法。这次实验和以往的几次实验有些不同，这次实验用到了二叉树的思想，在实现的时候比以往的实验要难一些，树的存储结构也有些变化，遍历方式等有有点不一样。这次实验，我先写了一个实验方案，然后按照方案的算法结构直接填写代码，由于是第一次，所以写实验方案的时候想了很久，不断的修改，最后按方案写程序。这样做确实和以往的实验有些不一样，思路清晰，知道该怎么实现，每一步都考虑到了，而以往的实验是直接开始写程序，没有大体结构，没有思路，直接一步步的写，错了删，然后又写，很浪费时间。这次却不一样，有了方案，有了思路，只需要添加代码进行调试，还节省了很多时间。虽然，在调试的过程中遇到了很多麻烦和问题，但是都没有像以往的实验那样错误很多，在调试的过程中也相当于复习了一遍所学的知识，受益匪浅啊。参考文献严蔚敏 数据结构题集(C语言版) 清华大学出版社 2007年李春葆 数据结构教程(第2版) 清华大学出版社 2007年
