題目與內容
哈夫曼(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 frequencyn");
while(p!=NULL){
printf("%c %dn",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 coden");
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("nnInput codes again(y/n)?"); /*詢問是否繼續譯碼*/
c=getche();
printf("nn");
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();
}