数据结构--哈夫曼树

一、实验目的

1、掌握二叉树的逻辑结构、存储结构及基本操作；

2、熟练掌握哈夫曼树在实际问题中的应用；

3、针对计算机领域复杂工程问题，能够综合运用数据结构的基本理论和设计方法，设计出合理的算法。

二、实验内容

 “烽火连三月，家书抵万金”可见古人传递信息的不容易。古人用烽火台、信鸽、驿站等传送信息。现在我们有电话、互联网等媒介，信息传递非常方便快捷。我们所发送的信息都会先经过编码变成01串，再打包传输出去的。为了提高传输效率，通常利用哈夫曼树来进行编码，使得编码总长度最短且不出现二义性， 

请输入一行字符串，分别统计出各种字符的个数，作为其对应权值，建立哈夫曼树。

实现功能如下：

1. 统计各种字符出现次数
2. 以统计的次数作为权值建立哈夫曼树
3. 对哈弗曼树进行先序、中序、后序、层序等遍历
4. 求出哈弗曼树的高度
5. 求出各种字符的哈夫曼编码及总WPL（选做）
6. 显示编码后的字符串及压缩比（01串，选做）
7. 用编码表对任意输入的一行01串进行译码（选做）

三、算法描述

（采用自然语言描述）

先构造哈夫曼树，再存储数据，编码，打印哈夫曼树。

四、详细设计

五、程序代码

#include<stdio.h>

#include<string.h>

#define OK 1

#define ERROR 0

#define OVERFLOW -2

#define MAXSIZE 100

typedef int Status;

int num[256]={0},H[256]={0};

//哈夫曼树的存储表示

typedef struct\n{

  int weight;                //结点权值 

  int perent,lchild,rchild;   //结点的双亲，左孩子，右孩子的下标  } HTNode,*HuffmanTree;        //动态分配数组存储哈夫曼树 

 //构造哈夫曼树中的Select函数 

void Select(HuffmanTree HT,int n,int &s1,int &s2)  //s1,s2取地址 

 { float min1=99999,min2=99999;

   int i;

 for(i=1;i\u003C=n;i++)

  if(min1>HT[i].weight&&HT[i].perent==0)

  {min1=HT[i].weight;s1=i;}

  for(i=1;i\u003C=n;i++)

 if(min2>HT[i].weight&&HT[i].perent==0&&HT[i].weight!=min1)

 {min2=HT[i].weight;s2=i;}

 }

 //构造哈夫曼树

void CreateHuffmanTree(HuffmanTree &HT,int n)

 {    int i,m,s1,s2;      //初始化

   if(n\u003C=1)

 return;  

m=2*n-1;

  HT=new HTNode[m+1];

  for(i=1;i\u003C=m;++i)

   {

      HT[i].perent=0;

   HT[i].lchild=0;

   HT[i].rchild=0;

  }

  for(i=1;i\u003C=n;++i) 

  //    scanf(\"%d\",HT[i].weight);

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

   //开始构造哈夫曼树

  for(i=n+1;i\u003C=m;++i)

   {

     Select(HT,i-1,s1,s2);

    HT[s1].perent=i;

   HT[s2].perent=i;

     HT[i].lchild=s1;

      HT[i].rchild=s2;

     HT[i].weight=HT[s1].weight+HT[s2].weight;

    }

}

   //哈夫曼编码表的存储表示

 typedef char **HuffmanCode;     //动态分配数组存储哈夫曼编码表

 //根据哈夫曼树求哈夫曼编码,存储在编码表HC中 

  void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)

  {   int c,f,start,i;char *cd;    

    HC=new char*[n+1];    //分配存储n个字符编码的编码表空间 

  cd=new char[n];       //分配临时存放每个字符编码的动态数组空间 

    cd[n-1]='\\0';         //编码结束符 

  for(i=1;i\u003C=n;++i)     //逐个字符求哈夫曼编码 

    {

     start=n-1;

      c=i;f=HT[i].perent;

     while(f!=0)

      {

   --start;

 if(HT[f].lchild==c)  cd[start]='0';

            else cd[start]='1';

       c=f;f=HT[f].perent;

    }

   HC[i]=new char[n-start];

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

 }

  //delete cd;

   for(i=1;i\u003C=n;i++)

     printf(\"%s \",HC[i]);  }

///哈夫曼树的先序遍历

void PreHufOrder(TreeNode*p)   //先序遍历

{  

if(p!=NULL)

{

printf("%d ",p->data) ;

PreHufOrder(p->lChild) ;

PreHufOrder(p->rChild) ;

}

}

 

//中序遍历  

void InHufOrder(TreeNode*p)

{

   if(p!=NULL)

   {

   InHufOrder(p->lChild) ;

   printf("%d ",p->data) ;

   InHufOrder(p->rChild) ;

   }

}

//后续遍历

void PostHufOrder(TreeNode*p)

{

if(p!=NULL)

{

InHufOrder(p->lChild) ;

InHufOrder(p->rChild) ;

printf("%d ",p->data) ;

}

}

//清空树  

void ClearHufTree(TreeNode*p)

{

if(p!=NULL)

{

ClearHufTree(p->lChild) ;

ClearHufTree(p->rChild) ;

delete p ;

}

}

//打印哈夫曼树

 int main(){    //  统计字符串各字符的频率 

  char str;

  char str[20];

   int i,num[256]={0};

  printf(\"please input string:\");

  scanf(\"%s\",str);

PreHufOrder(TreeNode*p);

InHufOrder(TreeNode*p);

PostHufOrder(TreeNode*p);

  for(i=0;i\u003Cstrlen(str);i++)

  {

     num[(int)str[i]]++;    }

  for(i=0;i\u003C256;i++)  {

   if(num[i]!=0)     {

       printf(\"字符%c出现%d次\\n\",(char)i,num[i]);     }   }

//统计字符串各字符的频率 

   HuffmanCode HC; 

  HuffmanTree HT;  

  CreateHuffmanTree(HT,j);

     CreateHuffmanCode(HT,HC,j);

ClearHufTree(TreeNode*p);

  return 0;

}

• 测试和结果

测试用例：abcba

测试结果：2 2 1

3

七、用户手册

依次输入数据，运行程序，给出各种字符出现的次数及哈夫曼树的高度