《数据结构课程设计》

实验报告

                           赫夫曼编码

实验课程名称        数据结构课程设计       

专  业 班 级        11级计科（2）班       

学  生 姓 名           王琦                

学        号         114090102036          

指  导 教 师           冯   韵             

      实 验 时 间 ：  2013 年 9 月 24 日

 2013至 20##学年第 1 学期第 1 至 9 周

目    录

 

一、概述.............................................. 1

二、系统分析.......................................... 1

三、概要设计.......................................... 2

四、详细设计.......................................... 4

4.1 赫夫曼树的建立................................. 4

4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法  5

4.1.2 统计字符串中字符的种类以及各类字符的个数.... 7

4.1.3构造赫夫曼树............................... 8

4.2赫夫曼编码..................................... 10

4.2.1赫夫曼编码算法............................ 10

4.2.2建立正文的编码文件........................ 11

五、运行与测试....................................... 12

六、总结与心得....................................... 13

一、概述

    本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出 电文字符串。

    在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时 间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

二、系统分析

    赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。

    通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。

    假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为∑W i L i 。 若将此对应到二叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。那么，∑W i L i 恰好为二叉 树上带权路径长度。

    因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树， 此构造过程成为赫夫曼编码。

  根据设计要求和分析，要实现设计，必须实现以下方面的功能：

（1） 赫夫曼树的建立；

（2） 赫夫曼编码的生成；

（3） 编码文件的译码；

三、概要设计

      void main()

void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)//编码部分

char *decode(HuffmanCode Hc)//译码

void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[]) //生成Huffman树

void select(HufmanTree HT,int k,int &s1,int &s2) //找寻parent为0,权最小的两个节点

其流程图如下：

 

四、详细设计

4.1 赫夫曼树的建立

    由赫夫曼算法的定义可知，初始森林中共有 n 棵只含根节点的二叉树。算法的第二步是：将当前森林 中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新 节点。显然要进行 n-1 次合并，所以共产生 n-1 个新节点，它们都是具有两个孩子分支结点。由此可 知，最新求得的赫夫曼树中一共有2n-1 个结点，其中n 个结点是初始森林的n 个孤立结点。并且赫夫 曼树中没有度数为1 的分支结点。我们可用一个大小为2n-1 的一维数组来存储赫夫曼树中的结点。因 此，赫夫曼树的存储结构描述为：

  #define n 100

  #define m 2*n-1

  typedef struct{

  int weight;

  int lchild,rchild,parent;

}HTNode; T

  typedef HTNode HuffmanTree[m+1];

 

4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法

  void select(HuffmanTree T,int k,int *s1,int *s2)

{//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为S1和S2

 int i,j;

 int min1=100;

 for(i=1;i<=k;i++)//查找s1

  if(T[i].weight<min1 && T[i].parent==0)

  {

   j=i;min1=T[i].weight;

  }

  *s1=j;

  min1=32767;

  for(i=1;i<=k;i++)//查找s2,不和s1相同

   if(T[i].weight<min1 && T[i].parent==0 && i!=(*s1))

   {

    j=i;

    min1=T[i].weight;

   }

   *s2=j;

}

4.1.2 统计字符串中字符的种类以及各类字符的个数

　　假设电子文件字符串全是大写字母，那么该算法的实现思想是：先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。应为大写字母的ASCII码与整数1~26个元素之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组元素中。具体实现如下：

int jsq(char *s,int cnt[],char str[])

{

 //统计各字符串中各种字母的个数以及字符的种类

 char *p;

 int i,j,k;

 int temp[27];

 for(i=1;i<=26;i++)

  temp[i]=0;

 for(p=s;*p!='\0';p++)

 {//统计各种字符个数

  if(*p>='A' && *p<='Z') {

   k=*p-64;

   temp[k]++;

  }

 }

 j=0;

 for(i=1,j=0;i<=26;i++)//统计有多少种字符

  if(temp[i]!=0) {

   j++;

   str[j]=i+64;//将对应的数组送到数组中

   cnt[j]=temp[i];//存入对应数组的权值

  }

  return j;

}

4.1.3构造赫夫曼树

void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt[],char str[])

{//构造赫夫曼树HT

 int i,s1,s2;

 for(i=1;i<=2*num-1;i++)//初始化HT，左右孩子，双亲，权值都为0

 { HT[i].lchild=0; HT[i].rchild=0;

   HT[i].parent=0; HT[i].weight=0;

 }

 for(i=1;i<=num;i++)//输入num个叶节点的权值

  HT[i].weight=cnt[i];

 for(i=num+1;i<=2*num-1;i++)//从numd后面开始新建结点存放新生成的父节点

 {

  select(HT,i-1,&s1,&s2);//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2

  HT[s1].parent=i;HT[s2].parent=i;//将s1和s2的parent赋值

  HT[i].lchild=s1; HT[i].rchild=s2;//新结点的左右孩子

  HT[i].weight=HT[s1].weight+ HT[s2].weight;//新结点的权值

 }

 for(i=0;i<=num;i++)//输入字符集中的字符

  HC[i].ch=str[i];

 i=1;

 while(i<=num)

  printf("字符 %c,次数为: %d\n",HC[i].ch,cnt[i++]);

}

4.2赫夫曼编码

  要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：

typedef struct{

 char ch;

char bits[n+1];

int start ;

}CodeNode;

typedef CodeNode HuffmanCode[n];

 

4.2.1赫夫曼编码算法

void HuffmanEncoding(HuffmanTree HT,HuffmanCode HC)

{//根据赫夫曼树HT 求赫夫曼编码表ＨＣ

int c,p,i;

char cd[n];

int start; cd[num]='\0';

for(i=1;i<=num;i++)

{

 start=num;

c=i;

while((p=HT[c].parent)>0)//直至上诉到ht[c]是树根为止

{//若HT[c]是HT[p]的孩子，则生成0；否则生成代码1

cd[--start]=(HT[p].lchild= =c)? '0':'1' :

c=p;

}//end of while

strcpy(HC[i].bits,&cd[start]);

HC[i].len=num-start;

}

 }

 

4.2.2建立正文的编码文件

     建立编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成赫夫曼树时保保存的 字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完毕为止。

 具体算法如下：

viod  coding(huffmanCode HC,char *str)

{

 int i,j;

FILE *fp;

 fp =fopen(“codefile.tex”,”w”);

 while(*str){//对电文中字符逐一生成编码并写入文件

for(i=1;i<=num;i++)

if(HC[i].ch= =*str){

 for(j=0;j<=HC[i].len;j++) f

putc (HC[i].bits[j],fp);

break;

} str++;

}

 fclose(fp);

}

 五、运行与测试

运行结果为

　　

 

 

六、总结与心得

     本次编写过程中出现了较多的问题，比如开始对赫夫曼树的理解不是很清楚，导致在编写过程中某些代码错误而没能及时修改，在最后进行修改时遇到了较多的麻烦。但是经过这次对赫夫曼树的学习后，我了解到赫夫曼编码(Huffman Coding)是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据的无损耗压缩。总之受益匪浅。

 

第二篇：数据结构课程设计实验报告(赫夫曼编码)(1) 2

数据结构课程设计

哈夫曼编码

学    院：计算机科学与技术学院

 专    业：计算机科学与技术    

学    生：              

学    号：         

指导教师：           

20##年4月16日

                  

                   目录

一、课程设计的目的、功能及要求--------------1

二、主要功能模块流程图----------------------2

三、算法的基本思想--------------------------3

四、系统测试--------------------------------6

五、结论------------------------------------7

六、源程序----------------------------------8

一、课程设计的目的、功能及要求

目的：

1.  解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2.  件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；

3.  .合运用所学的理论知识和方法独立分析和解决问题的能力；

4.  用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

功能：

   1首先读入待压缩源文件；

     2然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huffman 树的权值；

     3频度表建好后，就可以根据算法建立Huffman 树，对出现的每种字符进行Huffman编码；

     4此时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件，并且计算压缩率。

要求：

1、核心数据结构用到的结构体要采用动态内存分配和链表结构。

2 、不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。

3 、对系统进行功能模块分析、画出总流程图和各模块流程图。

4    、用户界面要求使用方便、简洁明了、美观大方、格式统一。

4

5．     所有程序需调试通过。

5．

二、主要功能模块流程图

 

三、算法的基本思想

（1）构造Hufffman树的方法—Hufffman算法

构造Huffman树步骤：

I.   根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令起权值为wj。

II. 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和

III.     在森林中删除这两棵树，同时将新得到的二叉树加入森林中。

IV. 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

（2）Huffman编码：数据通信用的二进制编码

思想：根据字符出现频率编码，使电文总长最短

编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。

流程图：

部分程序：

（1）  构造哈夫曼树

void HaffmanTree(HNodeType HuffNode[MAXNODE])              

 {

int i,j,m1,m2,x1,x2;

for(i=0;i<MAXNODE;i++)

{

    HuffNode[i].parent=-1;

    HuffNode[i].lchild=-1;

    HuffNode[i].rchild=-1;

}

for(i=0;i<num-1;i++)

{

    m1=m2=MAXVALUE;

    x1=x2=0;

    for(j=0;j<num+i;j++)

    {

        if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)

        {

            m2=m1;

            x2=x1;

            m1=HuffNode[j].weight;

            x1=j;

       }

        else

            if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)

            {

                m2=HuffNode[j].weight;

                x2=j;

            }

    }

    HuffNode[x1].parent=num+i;

    HuffNode[x2].parent=num+i;

    HuffNode[num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;

    HuffNode[num+i].lchild=x1;

    HuffNode[num+i].rchild=x2;

}

}

（2）哈夫曼编码

LinkList  Bianma(LinkList l,Code code[MAXNODE]) //写编码文件

{

LinkList p,q,p1,p2;

int i,j;

p=l->next ;

q=new LNode;

q->next=NULL;

p1=new LNode;

p2=q;

while(p)

{  

    for(i=0;i<num;i++)

        if(p->data==code[i].data)

        {  

            j=0;

            while(code[i].bit[j]!='\0')

            {

                p1->data=code[i].bit[j];

                j++;

                p2->next=p1;

                p2=p1;

                p1=new LNode;

            }

        }

    p=p->next ;

}

p2->next=NULL;

return q;

}

SeqStack Init()

{

SeqStack s;

s=new StackNode;

s->top=-1;

return s;

}

void HaffmanCode(HNodeType HuffNode[MAXNODE],HCodeType HuffCode[MAXLEAF]) //哈夫曼编码算法

{

int i,j,c,p;

HCodeType cd;

for(i=0;i<num;i++)

{

    cd.start=MAXBIT-1;

    c=i;

    p=HuffNode[c].parent ;

    while(p!=-1)

    {

        if(HuffNode[p].lchild==c)

            cd.bit[cd.start]='0';

        else

            cd.bit[cd.start]='1';

        cd.start --;

        c=p;

        p=HuffNode[c].parent;

    }

    for(j=cd.start+1;j<MAXBIT;j++)

        HuffCode[i].bit[j]=cd.bit[j];

    HuffCode[i].start=cd.start ;

}

}

四、系统测试

1、主界面

2、输入并保存编码

五、结论

   本次课程设计的目的是：把一个随机输入的字符串中不同字符作为叶子结点元素，把其在该字符串中出现的次数作为权值构造一个赫夫曼树，并得到各个叶子结点的赫夫曼编码和整个输入的字符串的赫夫曼编码。在写代码前，首先，对问题进行了分析，明确了目标，列出了大的框架，然后逐渐细化，划分出不同的功能模块，由具体的子函数去实现，先在纸上编写代码，写好后进行了反复的逻辑推理，发现并解决逻辑问题，然后，上机调试，方法是：一个一个功能模块分开进行调试，主要看调试的模块能否达到预期的结果，这样可以缩小排错的范围，便以纠错和提高编程的效率，当每个功能模块都调试好后，就把各个部分组合起来，再进行调试，主要检查各函数接口是否正确，当达到预期的结果，调试结束，编程部分完成，然后按实验要求完成实验报告。

由于写代码前做了充分的准备工作，所以写起代码来比较顺利，使编程的效率有不少的提高并且最终达到实验预期的结果。

心得体会：

每一次的课程设计对我来说都是一个不小的提高，哲学上说：“实践是检验真理正确性的唯一标准”，尤其是学编程，自己不动手操作，只看书永远都编不出像Windows之类的东西，正如老师说的那样，课程设计非常锻炼人，每完成一个项目，不仅是知识体系的完善和知识的验证，更是编程技术的提升，当自己编的多了，就会开始摸索编程的捷径，想着用更高效的方法去完成一个个项目，就这样在一次次的锻炼中自己会从一个菜鸟迅速的成长，终将成为一个优秀的软件工程师。

一个成功的项目必须在写代码前，先要对课题有充分的思考和规划，否则即使完成了项目也会浪费很多的时间和精力，我认为科学合理的编程方法是我这次课程设计的最大收获。

六、源程序

#include<iostream>

#include<fstream>

#include"heads.h"

#define NULL 0

#define MAXVALUE 10000           //最大权值

#define MAXLEAF 100              //叶子结点个数

#define MAXNODE MAXLEAF*2-1      //哈夫曼树结点个数

#define MAXBIT 12                //最大长度

using namespace std;

int num;

int power(int x)//2的x次方

{

    int i;

    for(i=1;i<=x;i++)

    {

        i*=2;

    }

    return i;

}

float pration(int a,int b)//计算压缩率,a为压缩前字长，b为压缩后字长

{

    float s;

    s=(float)((float)b/(float)a);

    return s;

}

void Show(LinkList l) //输出

{

    LinkList p=l->next;

    while(p)

    {

        cout<<p->data ;

        p=p->next;

    }

    cout<<endl;

}

LinkList Create()    //写入字符串

{

    int total=0;

    int x=1,y;

    int p=0;

    LinkList l,p1,p2;

    l=new LNode;

    l->next=NULL;

    cout<<"请输入:"<<endl<<endl;

        cout<<"1.输入并存入文档\n2.从文档读取,并计算出压缩率!"<<endl<<endl;

        cout<<"请输入要进行的操作:"<<endl;

        int choose;

        cin>>choose;

        if(choose!=1&&choose!=2)

        {

            cout<<"输入错误,请重新输入!"<<endl;

            cin>>choose;

        }  

       if(choose==1)

        {

            ofstream outfile;

            outfile.open("code.txt",ios::out);

            if(!outfile)

            {

                cout<<"输出时打开code文档出错!"<<endl;

                exit(1);

          }

            cout<<"请输入所要编译的字符串,以#结束:"<<endl;

           p1=new LNode;

            p2=l;

            cin>>p1->data;   outfile<<p1->data;

           while(p1->data!='#')

            {

               p2->next=p1;

               p2=p1;

               p1=new LNode;

               cin>>p1->data;outfile<<p1->data;

            }

               p2->next=NULL;

               p2=l;

           

               return l;

       }

       else{

           ifstream infile("wenjian.txt",ios::in);

            if(!infile)

            {

                cout<<"输出时打开文档出错!\n或文档不存在!"<<endl;

                cout<<"请确认本目录下有相关文件后再重试!"<<endl;

                exit(1);

            }

            l=Read("wenjian.txt");

            p1=new LNode;

            p2=l;

               infile>>p1->data;

           while(infile.eof())

            {

               p2->next=p1;

               p2=p1;

               p1=new LNode;

              infile>>p1->data;

            }

            p1->data='#';

            p1->next=NULL;

            infile.close();

            printf("读取完成！\n");

            Show(l);

        

/*****************以下计算压缩率*******************/

           

                p2=l;

                while(p2)

                {

                    total++;

                    p2=p2->next;

                }

                for(;power(x)<total;)

                {

                    x++;

                    p=x;    //记录正常编码一个字符需要的比特位数

                }

               

                y=(total-1)*x;//正常所需的总比特数

                printf("y is %d\n",y);

            /***********编码后的位数计算********************/

                int c;

          FILE *fp;

          if((fp=fopen("Code.txt","rb"))==NULL)

          {

              printf("文件打开失败！\n");

              exit(0);

          }

            while(!feof(fp))

            {

                c=fgetc(fp);

                x=x+1;

            }

       

            printf("x is %d",x);

           

/*****************计算完成**************************/

            printf("压缩率为%4.2f%%",pration(y,x)*100);

            return l;

       }

      

}

void Write(LinkList l,char wenjian[])

{

    LinkList p1;

    ofstream outfile(wenjian,ios::out);

    p1=l->next ;

    while(p1)

    {

        outfile<<p1->data;

        p1=p1->next;

    }

    outfile<<"#";

    outfile.close();

}

LinkList Read(char wenjian[])  //读文件中字符串

{

    LinkList l,p1,p2;

    l=new LNode;

    l->next=NULL;

    p1=new LNode;

    p2=l;

    ifstream infile(wenjian,ios::in);

    if(!infile)

            {

                cout<<"打开文档出错!\n或文档不存在!"<<endl;

                cout<<"请确认本目录下有相关文件后再重试!"<<endl;

                exit(1);

            }

    infile>>p1->data;

    while(p1->data!='#')

    {

        p2->next=p1;

        p2=p1;

        p1=new LNode;

        infile>>p1->data;

    }

    p2->next=NULL;

    infile.close();

    return l;

}

void Create(HNodeType a[MAXNODE],LinkList l)      //统计字符个数,做出哈夫曼树的结点       

{

    LinkList p;

    int i;

    p=l->next ;

        //全局变量num在这里的作用

    while(p)

    {

        for(i=0;i<num;i++)

            if(a[i].data==p->data)

            {

                a[i].weight++;

                break;

            }

        if(i==num)

        {

            a[i].data=p->data;

            a[i].weight=1;

            num++;

        }

        p=p->next;

    }

    //printf("num is %d ",num);可以看到num在这里的作用

    for(i=0;i<num;i++)

    {

        a[i].lchild=NULL;

        a[i].rchild=NULL;

        a[i].parent=-1;

    }

}

void HaffmanTree(HNodeType HuffNode[MAXNODE])      //构造哈夫曼树

{

    int i,j,m1,m2,x1,x2;

    for(i=0;i<MAXNODE;i++)

    {

        HuffNode[i].parent=-1;

        HuffNode[i].lchild=-1;

        HuffNode[i].rchild=-1;

    }

    for(i=0;i<num-1;i++)

    {

        m1=m2=MAXVALUE;

        x1=x2=0;

      for(j=0;j<num+i;j++)

        {

            if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)

            {

                m2=m1;

                x2=x1;

                m1=HuffNode[j].weight;

                x1=j;

            }

            else

                if(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)

                {

                    m2=HuffNode[j].weight;

                    x2=j;

                }

        }

        HuffNode[x1].parent=num+i;

        HuffNode[x2].parent=num+i;

        HuffNode[num+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;

        HuffNode[num+i].lchild=x1;

        HuffNode[num+i].rchild=x2;

    }

}

//哈夫曼编码

LinkList  Bianma(LinkList l,Code code[MAXNODE]) //写编码文件

{

    LinkList p,q,p1,p2;

    int i,j;

    p=l->next ;

    q=new LNode;

    q->next=NULL;

    p1=new LNode;

    p2=q;

    while(p)

    {  

        for(i=0;i<num;i++)

            if(p->data==code[i].data)

            {  

                j=0;

                while(code[i].bit[j]!='\0')

            {

                    p1->data=code[i].bit[j];

                    j++;

                    p2->next=p1;

                    p2=p1;

                    p1=new LNode;

                }

            }

        p=p->next ;

    }

    p2->next=NULL;

   

    return q;

}

SeqStack Init()

{

    SeqStack s;

    s=new StackNode;

    s->top=-1;

    return s;

}

void HaffmanCode(HNodeType HuffNode[MAXNODE],HCodeType HuffCode[MAXLEAF]) //哈夫曼编码算法

{

    int i,j,c,p;

    HCodeType cd;

    for(i=0;i<num;i++)

    {

        cd.start=MAXBIT-1;

        c=i;

        p=HuffNode[c].parent ;

        while(p!=-1)

        {

            if(HuffNode[p].lchild==c)

                cd.bit[cd.start]='0';

            else

                cd.bit[cd.start]='1';

            cd.start --;

            c=p;

            p=HuffNode[c].parent;

       }

        for(j=cd.start+1;j<MAXBIT;j++)

            HuffCode[i].bit[j]=cd.bit[j];

        HuffCode[i].start=cd.start ;

    }

}

void bianma(HCodeType HuffCode[MAXLEAF],HNodeType a[MAXNODE],Code code[MAXNODE])         //字符编码

{

    int i,j,k;

    for(i=0;i<num;i++)

    {  

        code[i].data=a[i].data;

        for(j=HuffCode[i].start+1,k=0;j<MAXBIT;j++,k++)

        {

            code[i].bit[k]=HuffCode[i].bit[j];

        }

        code[i].bit[k]='\0';

    }

}

int panduan(char a[MAXBIT],char b[MAXBIT])

{

    if(strcmp(a,b)==0)

        return 1;

    else

        return 0;

}

void bianma(Code code[MAXNODE],LinkList l)//读取编码

{

    int i,flag;

    SeqStack s;

    s=Init();

    LinkList p;

    p=l->next;

    while(p)

    {

        s->top++;

        flag=0;

      s->data[s->top]=p->data;

        s->data[s->top+1]='\0';

        for(i=0;i<num;i++)

            if(panduan(s->data,code[i].bit)==1)

            {

                cout<<code[i].data;

                flag=1;

                break;

            }

        if(flag)

        {  

            s=Init();

        }

        p=p->next;

    }

    cout<<endl;

}

void ShowTree(HNodeType node[MAXNODE])

{printf("输出");

    int i;

    cout.width(8);

    cout.setf(ios::left);

    cout<<"统计字符频率结果为:"<<endl;

    cout<<"频率    ";

    cout.width(8);

    cout<<"字符"<<endl;

    for(i=0;i<num;i++)

    {

        cout.width(8);

        cout<<node[i].weight;

        cout.width(8);

        cout<<node[i].data<<endl;

    }

    cout<<endl;

    cout<<"哈弗曼树编码为:"<<endl;

    cout<<"字符";

    cout<<"    ";

    cout<<"编码";

    cout<<endl;

}

void ShowCode(Code cood[MAXNODE])

{

    for(int i=0;i<num;i++)

        cout<<cood[i].data<<"\t"<<cood[i].bit<<endl;

}

void bianma(HNodeType node[MAXNODE],HCodeType code[MAXLEAF],Code CODE[MAXNODE])

{

    LinkList l,c;

    l=Create();                       //写字符串

    Write(l,"wenjian.txt");

    l=Read("wenjian.txt");

    cout<<"文件内容:"<<endl;

    Show(l);

    Create(node,l);                  //统计字符个数

    HaffmanTree(node);               //构造哈夫曼树

    ShowTree(node);                  //输出哈夫曼树

    HaffmanCode(node,code);          //哈夫曼编码算法

    bianma(code,node,CODE);          //字符编码

    ShowCode(CODE);                  //输出编码规则

    c=Bianma(l,CODE);

    cout<<"编码文件为:"<<endl;

    Show(c);           

    Write(c,"Code.txt");

}

void yima(Code CODE[MAXNODE])//译码

{

    LinkList l;

    l=Read("Code.txt");      //读取编码文件

    cout<<"译码的文件为:"<<endl;

    Show(l);             //显示编码文件

    cout<<"译码文件为:"<<endl;

    bianma(CODE,l);        //译码

}

int Menu_Select()

{

   int i;

    cout<<"1.编码信息\n2.译码信息\n0.退出程序"<<endl;

    cout<<"请选择要进行的操作:"<<endl;

    cin>>i;

    while(i<0||i>2)

    {

        cout<<"输入错误!请重新输入：";

        cin>>i;

    }

    return i;

}

int main()

{

    HNodeType node[MAXNODE];//哈夫曼节点数组

    HCodeType Huffcode[MAXLEAF];//

    Code code[MAXNODE];

    cout<<"*****************************************************************"<<endl;

    cout<<"**************欢迎进入Huffman树编码与译码系统********************"<<endl;

    while(1)

    {

        switch(Menu_Select())

        {

        case 1:bianma(node,Huffcode,code);break;

        case 2:yima(code);break;

        case 0: return 0;

        }

    }

    return 0;

}