【数据结构】哈夫曼树的应用实验报告

数据结构哈夫曼树的应用实验报告

正文

一． 实验目的

了解二叉树的定义，理解二叉树的基本性质和存储结构，掌握哈夫曼树的构造，实现哈夫曼编码与译码算法。

二． 实验内容

从键盘输入一串电文字符与权值，输出对应的哈夫曼编码；从键盘输入一串二进制代码，输出对应的电文字符串。具体步骤如下：

1. 构造一棵哈夫曼树；
2. 实现哈夫曼编码；
3. 对哈夫曼编码生成的二进制串进行译码；
4. 要求程序中字符和权值是可变的，实现程序的灵活性。

三． 实验工具

DEV-C++

四． 实验代码

#include<stdio.h>
typedef struct {
  char data;
  int w,l,r,p;
}node;
typedef struct{
 char cd[50];
 int start;
}code;
int create (node *h){
  int i,k,n,m1,m2,p1,p2;
  printf("请输入元素个数为：");
  scanf("%d",&n);
  for(i=1;i<n+1;i++){
    getchar();
    printf("第%d个元素的节点值和权重：",i);
    scanf("%c %d",&h[i].data,&h[i].w);
  }
  for(i=1;i<=2*n-1;i++)
      h[i].p=h[i].l=h[i].r=0;
  for(i=n+1;i<=2*n-1;i++){
      m1=m2=32767;
      p1=p2=i;
      for(k=1;k<i;k++){
          if(h[k].p==0){
              if(h[k].w<m1){
                 m2=m1;
                 p2=p1;
                 m1=h[k].w;
                 p1=k;
              }
              else if(h[k].w<m2){
                  m2=h[k].w ;
                  p2=k;
              }
          }
      }
      h[p1].p=i;
      h[p2].p=i;
      h[i].w=m1+m2;
      h[i].l=p1;
      h[i].r=p2;
  }
  printf("success for hufftree!\n");
  return n;
}
void encoding(node h[],code co[],int n){
     code d;
     int i,k,f,c;
     for(i=1;i<n+1;i++){
         d.start=n+1;
         c=i;
         f=h[i].p;
         while(f!=0){
             if(h[f].l==c)
                  d.cd[--d.start]='0';
              else  d.cd[--d.start]='1';
              c=f;
              f=h[f].p;
             
         }
         co[i]=d;
     }
     printf("输出哈夫曼编码：\n");
     for(i=1;i<=n;i++){
         printf("%c:",h[i].data);
         for(k=co[i].start;k<=n;k++){
             printf("%c",co[i].cd[k]);
         }
         printf("\n");
     }
}
void decoding(node h[],code co[],int n){
   int f,m,k;
   char c,ch[200];
   printf("请输出电文（0或1），以‘#’为结束标志：\n");
   c=getchar();
   k=1;
   while(c!='#'){
      ch[k]=c;
      c=getchar();
      k++;
   }
   m=k;
   f=2*n-1;
   k=1;
   printf("输出哈夫曼编码：\n");
   while(k<m){
       while(h[f].l!=0){
           if(ch[k]=='0') f=h[f].l;
           if(ch[k]=='1') f=h[f].r;
           k++;
       }
       printf("%c",h[f].data);
       f=2*n-1;
   }
   printf("\n");
}
int main(){
    int flag=5,c;
    while(flag){
          printf("\n==========================\n");
          printf("\n|**哈夫曼编码与译码**    |\n");
          printf("\n|1:创建哈夫曼树          |\n");
          printf("\n|2:进行哈夫曼编码        |\n");
          printf("\n|3:进行哈夫曼译码        |\n");
		  printf("\n|4:退出程序              |\n");
		  printf("\n==========================\n");
          scanf("%d",&flag);
          if(flag==1){
               node h[200];
               code co[100];
               int n; //节点数
                 n=create(h);
               scanf("%d",&c);
               while(c){
                 if(c==2){
                    encoding(h,co,n);
                 }
                  if(c==3){
                    decoding(h,co,n);
                 }
                  if(c==4) { 
                     printf("退出系统。\n");
                  break;
                  }
                 scanf("%d",&c);
               }
          }
          else if(flag==4){
                printf("退出系统。\n");
                break;
          }
          else{
              printf("输入错误，请重新输入！\n");
          }
    }

    return 0;
}

五． 实验结果

六． 总结与思考

1：通过这个实验，让我加深了对哈夫曼树的理解。构造哈夫曼树的关键在于找最小树。
2：本实验并没有采用cpp代码，而是从网上搜了一个c的代码，并对其代码进行了一部分的更改。
3：通过部分实验代码的更改，使得本实验程序中字符和权值是可变的，实现了程序的灵活性。并且实验步骤2，3 的进行需要有步骤1 的前提，具有一定的健壮性。