数据结构实验报告

题目与内容
 哈夫曼(Huffman)树与哈夫曼码
 1．输入一个文本，统计各字符出现的频度，输出结果；
 2．使用二叉链表或三叉链表作存储结构，构造哈夫曼(Huffman)树；
 3．确定和输出各字符的哈夫曼码；
       4.输入一个由0和1组成的代码序列，翻译并输出与之对应的文本；
       
二、  数据结构及存储结构
在这个程序中我用了三叉链表tree作为哈夫曼树的结构：左、右儿子和父亲
节点；并且在开始，我还用此结构生成了单链表，用来存储读取的字符。编码的时候，我把编码放在栈结构stack中，然后逆序输出即为哈夫曼编码。存放叶节点时用到了指针数组。
struct tree(){
 char data;
 int m,sign;
 struct tree *lchild,*rchild,*parent;
}
struct stack{
 int data;
 struct stack *next;
}

算法设计思想
先调用frequency函数读取字符，创建链表来存储字符及其相关信息；同时把字符放进数组中进行备份，因为后面编码时要用到这些字符（它们就是叶节点）。然后遍历这个链表输出个字符的频度。接着调用ctree函数来生成哈夫曼树。在ctree函数中，首先对刚才那个链表按照频度排序，变成频度递增链表；然后取其前两个节点作为新建哈夫曼树的左右儿子（注：左儿子的频度<=右儿子的频度），再把它们从链表中删除，并且把新建的哈夫曼树的根结点插入到链表中。这样重复操作，就生成了哈夫曼树。然后调用ccode函数编码。我采用的是从叶到根的编码方式。先从数组中取出数据（即为一个叶节点），看其m的值（0/1），放进stack栈中，然后向根遍历，接着把栈中的数据取出输出，即为编码。最后调用translate函数进行译码。先读取01序列放进新创建的一个链表（队列形式）中，然后从根到叶进行遍历：从链表中取出一个数据，是0则到左子树，1则到右子树，如果其左右子树为空，则输出字符data，再取下一个数据从根重新遍历。这样就得到译码了。

心得体会
这次编程，从开始编到测试成功，我一共花了四天。这主要是因为之前我花了不少时间看书，把数据结构和存储结构都想好了，还看了大量程序，不管是相关还是不相关的。例如，有一个困扰我很久的问题：当询问是否继续时，输入y就继续，否则跳出；以前用getchar要等按了回车才进行判断，如果按了好几个y，则后面几个y被当成以后的输入处理了，这样就会出错。然而我在一个程序中看到了getche这个指令解决了这个问题，它不需等回车就进行处理。另外在定义哈夫曼树结构时，我加了个sign变量来标志它是左子树还是右子树，这样后面编码时就很方便。这次编程使我认识到：要重视细节，虽然很小，但是它会使程序不能运行或出错。这个程序中我由于把‘y’写成y，结果浪费了我半天的时间去查错。

五、  程序清单
#include <stdio.h>
#include <conio.h>
struct tree{         /*定义哈夫曼树的结构*/
 char data;            /*存放字符*/
 int m,sign; /*m存放字符出现的频率 sign是左(0)或右(1)儿子的标志*/
 struct tree *lchild,*rchild,*parent;    /*左儿子 右儿子 父节点*/
};
struct stack{           /*定义栈的结构*/
 int data;
 struct stack *next;
};
struct tree * ps[50],*root,*head;
 /*数组存放字符 root为二叉树的根结点 head为链表的头节点*/
int size;            /*标志字符个数*/
/*************************统计各字符出现的频度***********************/
void frequency(){
 struct tree *r,*p,*q;  
 int n,l,j=1;
 /*录入第一个字符并创建链表*/
 clrscr();             /*清屏*/
 head=NULL;
 printf("Input the text end of ENTER:\n");
 n=getchar();
 if(n!=''''\n''''){
  p=(struct tree*)malloc(sizeof(struct tree));
  p->data=n;
  p->m=1;
  p->sign=-1;
  p->lchild=NULL;
  p->rchild=NULL;
  p->parent=NULL;
  head=p;
  ps[0]=p;     /*把字符(后面的叶节点)放进数组备份*/
  n=getchar();

 }
 /*录入其它字符*/
 while(n!=''''\n''''){
  l=0;r=p;
  for(q=head;q!=NULL&&l==0;q=q->parent){
   if(q->data==n) {    /*检查是否和已经录入的字符相同*/
    q->m++;    /*如果相同则此字符的频度变量加1*/
    l=1;
   }
   r=p;
  }
  if(l==0){      /*如果不同则录入并加入链表*/
   p=(struct tree*)malloc(sizeof(struct tree));
   p->data=n;
   p->m=1;
   p->sign=-1;
   p->lchild=NULL;
   p->rchild=NULL;
   p->parent=NULL;
   r->parent=p;
   ps[j]=p;     /*把字符(后面的叶节点)放进数组备份*/
   j++;
  }
  n=getchar();
 }
 /*输出字符的频度*/
 p=head;
 size=0;
 printf("\nFrequency as follows:\ncharacters frequency\n");
 while(p!=NULL){
  printf("%c  %d\n",p->data,p->m);
  p=p->parent;
  size++;         /*统计字符的个数*/
 }
}
/****************************生成树**********************************/
void ctree(){ 
 struct tree *t,*r,*p,*e,*q;
 int n;
 /****给链表排序生成频度递增链表*****/
   for(p=head;p->parent!=NULL;p=p->parent){
      for(q=p->parent;q!=NULL;q=q->parent){
            if(p->m>q->m){
             n=q->m;       /*交换信息*/

     q->m=p->m;
              p->m=n;
    n=q->data;
    q->data=p->data;
    p->data=n;
         }
   }
 }
 /***********生成哈夫曼树***********/
 p=head;
 while(p!=NULL&&p->parent!=NULL){
 /*取递增链表前两个为左右儿子生成哈夫曼树*/
  q=p->parent->parent;    /*然后把它们从链表中删掉*/
  t=(struct tree*)malloc(sizeof(struct tree));
  t->lchild=p;       /*频度:左儿子<=右儿子*/
  t->rchild=p->parent;
  t->m=p->m+p->parent->m;
  t->rchild->parent=t;
  t->rchild->sign=1;
  t->lchild->parent=t;
  t->lchild->sign=0;
  t->sign=-1;
  root=t;          /*root为根结点*/
  root->parent=NULL;
  if(q!=NULL){        /*判断链表是否为空*/
   head=q;  
   r=head;
   e=head;     /*把新生成的根结点插入到链表中去*/
   if(head->m>t->m){      /*判断是否为头节点*/
    t->parent=q;
    head=t;
   }
   else{
    r=r->parent;
    while(r!=NULL&&r->m<t->m){
     e=r;
     r=r->parent;
    }
    t->parent=r;
    e->parent=t;
   }
   p=head;
   root=t;
  }

  else break;        /*如果链表为空则结束*/
 }
}
/******************************编码******************************/
void ccode(){      
 struct tree *p,*q;
 int j; 
 printf("\ncodes as follows:\ncharacters code\n");
 for(j=0;j<size;j++){      /*做size(叶节点个数)次循环*/
  head=NULL;
  p=ps[j];          /*从叶到根求编码*/
  printf("%c  ",p->data);
  while(p->parent!=NULL){       /*把编码存入栈中*/
   q=(struct stack *)malloc(sizeof(struct stack));
   q->data=p->sign;
   q->next=head;
   head=q;
   p=p->parent;
  }
  q=head;           /*输出编码*/
  while(q!=NULL){
   printf("%d",q->data);
   q=q->next;
  }
  printf("\n");
 }
}
/******************************译码******************************/
char translate(){
 struct tree *r,*p,*q;
 int n;
 char c;
 /*读取01序列*/
Error: printf("\nInput codes consist of 0 and 1 (end of ENTER):\n");
 n=getchar();
 if(n!=''''\n''''){          /*读取第一个字符*/
  p=(struct tree*)malloc(sizeof(struct tree));
  p->data=n;
  p->next=NULL;
  head=p;
  r=head;
  n=getchar();
 }
 while(n!=''''\n''''){          /*读取其它字符*/

  p=(struct tree*)malloc(sizeof(struct tree));
  p->data=n;
  p->next=NULL;
  r->next=p;
  r=p;
  n=getchar();
 }
 p=head;
 while(p!=NULL){        /*判断是否右非法字符*/
  if(p->data!=''''0''''&&p->data!=''''1''''){
   printf("There are illeage characters in your codes!\n");
   goto Error;
  }
  p=p->next;
 }
 printf("\nThe text of the codes is:");
 p=head;
 q=root;
 while(p!=NULL){         /*由根到叶遍历*/
  if(q->lchild==NULL&&q->rchild==NULL){  /*判断是否叶节点*/
   putchar(q->data);
   q=root;
  }
  else {           /*往下遍历*/
   if(p->data==''''0'''') q=q->lchild;
   else q=q->rchild;
   if(q->lchild==NULL&&q->rchild==NULL){
    putchar(q->data);
    q=root;
   }
  }
  p=p->next;
 }
 printf("\n\nInput codes again(y/n)?");     /*询问是否继续译码*/
 c=getche();
 printf("\n\n");
 return(c);          /*返回是否继续的标志*/
}
/******************************主程序******************************/
void main(){
 char c,a;
 
 do{
  frequency();

  ctree();
  ccode();
  c=translate();      /*translate子函数返回值赋给c*/
  for(;c==''''y''''||c==''''Y'''';){      /*判断是否继续译码*/
   c=translate();
  }
  printf("\nInput text again(y/n)?");
  a=getche();
 }
 while(a==''''y''''||a==''''Y'''');        /*判断是否循环*/
 clrscr();
 getchar();
}