1、利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信心传输时间，降低传输成本。但是，这要求在发送器端通过一个编码系统对待传输数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以可以双向传输信息的通道），每端都需要一个完整的编/译码系统。1、抽象数据类型定义如下：ADT Huffman数据对象：D= ai | 1in，n0，ai 属ElemType类型数据关系：R=| ai，ajD，1in，1jn，其中每个元素只有已过去前驱，可以有零个和多个后继，有且只有一个元素没有前驱基本运算：Inithuffman（t,n）：初始化哈夫曼树：建立一棵哈夫曼树t。Createhcode（t
2、, hcd, n）：对建立哈夫曼树进行编码并储存在数组hcd中。Encoding（t,hcd,n）：将字符进行编码。Decoding（t,hcd,n）：将码流进行译码。Readhuffman（t）：读取哈夫曼树的数据。Writehuffman（savecode,save）：存储savecode,save数组中哈夫曼编码的数据。2、主程序int main（）初始化哈夫曼树 ;for（ ; ; ）switch （返回菜单函数代码）case 1: 建立哈夫曼编码 ; break ;case 2: 输出哈夫曼编码 ;case 3: 编码 ;case 4: 译码 ;case 0: 退出 ;default
3、 : 输入菜单代码有误，请重新输入 ;return 0 ;3、模块间调用流程图主函数模块初始化函数模块读取文件中数据菜单1：建立哈夫曼树编码2：输出哈夫曼树编码3：编码4：译码0：退出菜单代码 1 2 3 4 0译码函数模块编码函数模块输出编码函数模块建立编码函数模块 模块流程图（二）、详细设计1、头文件定义及预定义#includestdlib.hconio.h#define W 6#define N 50#define M 100#define V 10002、定义数据类型typedef struct /*定义哈夫曼树类型*/char data ; /*结点值*/float weight ;
4、 /*频度*/int parent ; /*双亲点*/int lchild ; /*左孩子结点*/int rchild ; /*右孩子*/Hufffman ;typedef struct /*定义存放哈夫曼编码类型*/char cd N ; /*存放当前结点的哈夫曼码*/int start ; /*cd start cd n存放哈夫曼码*/Hcode ;Huffman tM; /定义一个哈夫曼树类型数组Hcode hcdV; /定义一个哈夫曼编码类型数组3、函数声明char menu（） ; /*声明菜单函数*/void Inithuffman（Huffman t,int n）; /*声明初始
5、化哈夫曼树*/void Createhcode（Huffman t,Hcode hcd,int n）; /*声明建立哈夫曼树编码*/void Printhuffman（） ; /*输出哈夫曼树编码*/void Encoding（Huffman t,Hcode hcd,int n） ; /*声明编码函数*/void Decoding（Huffman t,Hcode hcd,int n） ; /*声明译码函数*/void Readhuffman（Huffman t） ; /*声明读取数据函数*/void Writehuffman（char savecodeWW,char save） ; /*声明存
6、储编码数据函数*/4、函数定义void Inithuffman（Huffman t,int n） /定义初始化哈夫曼树 int i,k,lnode,rnode; /定义临时变量 float min1,min2; Readhuffman（t）; /读取数据 for（i=0;i2*n-1; i+） ti.parent=ti.lchild=ti.rchild=-1; /初始化结点相关域置处置为-1 for（i=n; min1=min2=1.0; /lnode和rnode为最小频度的两个结点位置 lnode=rnode=-1; for（k=0; k=i-1;k+） /在h中找权值最小的两个结点 if（
7、tk.parent= =-1） /在尚未构造的二叉树的结点中查找 if（tk.weightmin1） /在t树中找到最小频度的两个结点 min2=min1; rnode=lnode; min1=tk.weight; lnode=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; tr
8、node.parent=i; void Createhcode（Huffman t,Hcode hcd,int n） /定义建立哈夫曼树编码函数 int i,j,k,s,f,c; /定义临时变量; Hcode hc; char saveW,savecode1W; char savecode2WW=0; i=0;s-,j+） savecode2ij=savecode1s; /将码流放入到一个二维字符数组中 savei=ti.data; /将字符放到一个一维数组中 printf（哈夫曼编码已建立成功n）; Writehuffman（savecode2,save）; /将编码写入到输出文件中;ple
9、ase enter any key to continue. getch（）; system（clsvoid Printhuffman（） /输出哈夫曼树编码 int i=0; char saveW; char savecodeWW; FILE *fp; /定义一个文件指针*fp; fp=fopen（output.txt,r /打开文件if（fp= =NULL）找不到文件!n return;哈夫曼编码: while（!feof（fp） fscanf（fp,%c %sn,&savei,&savecodei）; /读取该文件的数据 printf（,savei,savecodei）; /将数据输出到
10、终端显示屏上; i+; ; fclose（fp）; /关闭文件void Encoding（Huffman t,Hcode hcd,int n） /定义编码函数 char codeV,saveV; int i=0,j,k,s,f,c; int sign=0; /标记字符是否是可编码，1为可编码 Printhuffman（）; /调用输出哈夫曼编码函数请输入一个字符串: scanf（%s,code）;/输入字符输出码流: while（codei!=0） /找到每个字符所对应的结点; for（j=0;jj+） if（codei= =tj.data） /将该结点进行编码 sign=1; hc.star
11、t=n; c=j; f=tj.parent; while （f! if（tf.lchild= =c） /当前结点是双亲的左孩子结点 hc.cdhc.start-= /哈夫曼编码为0 ; /哈夫曼编码为1 ; /再对双亲结点进行同样的操作 savek+=hc.cdhc.start+1; for（s=k-1;s-） /输出编码%c,saves）; if（j= =n&sign= =0） printf（无 sign=0;nplease enter any key to continue.void Decoding（Huffman t,Hcode hcd,int n） /定义译码函数 char code
12、V; int i=0,k;请输入一个码流: /输入编码 k=2*n-2; /指向头结点） /直到编码编译完 if （codei= =） k=tk.lchild; /指向当前结点的左孩子 else if（codei= = k=tk.rchild; /指向当前结点的右孩子 else k=2*n-2; /重新指向头结点 if （tk.data） /该结点有值,tk.data）; /则该段编码能成功译码 if（!tk.data&k!=2*n-2）void Readhuffman（Huffman t） /定义读取数据函数 input.txt if（fp= =NULL）初始化文件出错，找不到文件!plea
13、se enter any key to continue. exit（0）; fscanf（fp,%c %fnti.data,&ti.weight）; /关闭文件 void Writehuffman（char savecodeWW,char save） /定义存储字符编码函数 int i; /定义一个文件指针*fp if（fp=fopen（w）= =NULL） /将文件打开cannot open filen return;W;i+） fprintf（fp, /将数据写入到文件中 /关闭该文件int menu（） /声明菜单函数 int x;*nnnnttt哈夫曼编（译）码系统nnntt 1:
14、建立哈夫曼编码ntt 2: 输出哈夫曼编码ntt 3: 编码ntt 4: 译码ntt 0: 退出nnntt 请输入你的选择（04）:%dx）; return x; Inithuffman（t,W）; /初始化哈夫曼树 for（ ; switch （menu（） case 1: Createhcode（t,hcd,W）; case 2:printf（system（ case 3: Encoding（t,hcd,W）; case 4: Decoding（t,hcd,W）; case 0: default :输入菜单代码有误，请重新输入n return 0; 5、函数调用关系图mainInithuf
15、fmanReadhuffmanmenuEncodingDecodingCreatehcodePrinthuffmanWritehuffman函数调用图五、程序调试1、实验最开始出现错误的地方是在菜单函数，最初用的是用返回字符作为菜单码。在输入字符后，按回车的同时多输入了一个字符 n，相当于连续输入两个字符，这样导致在选择实现功能时调用不正确。最后把菜单码换成整型，这样就避免了调用错误。2、读取文件，在读取频度ti.weight时，因为它是浮点类型数据，所以不能用fread函数来读取。然后用fscanf（fp, “%c %f”,&ti.weight）函数来读取浮点类型数据，同时又遇到了一个问题，
16、float类型和double类型的区别，最开始用的是double类型来定义频度的，所以在读取数据时读不出来，调试了好几次，试着把double类型换成float类型，这样却能读取数据。3、在创建编码和编码的过程中，遇到了一些编码的问题，编出来的码流和预计的恰好相反，在接受码流的时候要逆序，因为每个字符的编码是逆序编码的。还有在译码的过程中也犯了一点错误，当码流为字符 0时, if （codei= =）写成了if （codei= =0），这样导致了所有译过来的字符都是F，主要是因为是而不是0，所以没有执行该语句，这样导致译码不正确。4、当循环到根节点的时候编码结束，用while（f!=-1）来结束
17、，把它写成了while（f= =-1），这样导致不是到根节点结束从而编码错误。5、在输出字符到显示屏幕上时也犯了一点错误，把printf（“%s”,.）写成了printf（“s%”,.），这样导致的结果是输出的是ssss而不是码流。六、实验结果1、哈夫曼编（译）码系统的主界面：2、建立哈夫曼编码：3、输出哈夫曼编码：4、编码：5、译码：七、实验总结本次实验的目的是学会使用二叉链表实现二叉树的存储验证和设计相关算法。这次实验和以往的几次实验有些不同，这次实验用到了二叉树的思想，在实现的时候比以往的实验要难一些，树的存储结构也有些变化，遍历方式等有有点不一样。这次实验，我先写了一个实验方案，然后按
18、照方案的算法结构直接填写代码，由于是第一次，所以写实验方案的时候想了很久，不断的修改，最后按方案写程序。这样做确实和以往的实验有些不一样，思路清晰，知道该怎么实现，每一步都考虑到了，而以往的实验是直接开始写程序，没有大体结构，没有思路，直接一步步的写，错了删，然后又写，很浪费时间。这次却不一样，有了方案，有了思路，只需要添加代码进行调试，还节省了很多时间。虽然，在调试的过程中遇到了很多麻烦和问题，但是都没有像以往的实验那样错误很多，在调试的过程中也相当于复习了一遍所学的知识，受益匪浅啊。参考文献严蔚敏 数据结构题集（C语言版） 清华大学出版社 2007年李春葆 数据结构教程（第2版） 清华大学出版社 2007年
