题目与内容
哈夫曼(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();
}