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