|
|
上學(xué)期學(xué)的數(shù)據(jù)結(jié)構(gòu)，當(dāng)時(shí)老師給的題目是：
從一文件中讀取字符，分別統(tǒng)計(jì)該文件中英文字符ABCD...等26個(gè)字母出現(xiàn)的概率，并以各自的概率為權(quán)值，為26個(gè)字符建立一棵赫夫曼樹，并對每個(gè)字符進(jìn)行哈弗曼編碼和哈弗曼解碼。
當(dāng)時(shí)課堂檢測時(shí)老師要求文件內(nèi)容為ＡＡＡＡＡＢＢＢＣＤＦＧ（反正就是某一個(gè)字母頻率高，其他很多字母缺失），結(jié)果我的代碼運(yùn)行之后就出現(xiàn)階梯一樣的編碼結(jié)果。老師說我代碼哪里錯(cuò)了。可是這兩天我重新編碼（主要是當(dāng)初的代碼沒備份，電腦硬盤壞過一次換了資料都沒了），發(fā)現(xiàn)結(jié)果還是這樣的奇怪的階梯。然后我才想明白哈弗曼樹的目的是樹的帶權(quán)長度最小，那么沒有出現(xiàn)過的字母權(quán)都是０，所以它們的編碼長度是沒有意義的。出現(xiàn)這樣的結(jié)果應(yīng)該是正常的。如果一定要糾結(jié)這個(gè)問題，應(yīng)該再寫一部分判斷權(quán)是否為０，只統(tǒng)計(jì)并記錄權(quán)為非０的字母。這里只附上目前的代碼（沒加判斷權(quán)為０的這部分，往后看有空再加，這兩天要復(fù)習(xí)，就先不玩了）。
#include
#include
#include
#include
#define N 555
#define M 26
typedef struct Node{
float weight; //權(quán)值
int parent; //父節(jié)點(diǎn)的序號，為0的是根節(jié)點(diǎn)
int lchild,rchild; //左右孩子節(jié)點(diǎn)的序號，為0的是葉子節(jié)點(diǎn)
}HTNode,*HuffmanTree; //用來存儲赫夫曼樹中的所有節(jié)點(diǎn)
typedef char **HuffmanCode; //用來存儲每個(gè)葉子節(jié)點(diǎn)的赫夫曼編碼
void select_minium (HuffmanTree &HT , int i ,int * min1 , int * min2){
int j=0;int temp;
for (; j <= i;j ++){
if(HT[*min1].parent) //min1對應(yīng)的父節(jié)點(diǎn)必須為0
(*min1)=j;
else
if(HT[*min2].parent || *min1==*min2)//min2對應(yīng)的父節(jié)點(diǎn)必須為0且min1min2不相等
(*min2)=j;
else
if (HT[*min2].weight
temp=*min2;
*min2=*min1;
*min1=temp;
}
else if(!HT[j].parent){
if (HT[j].weight <= HT[*min1].weight){
//權(quán)值比最小的還小或相等時(shí)，將此時(shí)的min1賦給min2,此時(shí)的哈弗曼結(jié)點(diǎn)序號付給min1.
*min2 = *min1;
*min1 = j;
}
else if (HT[j].weight < HT[*min2].weight )
//權(quán)值比min1的大,但比min2的小，只需改變min2。。。。。。..
*min2 = j;
}
}
}
HuffmanTree create_HuffmanTree(float *wet,int n,HuffmanTree &HT){
//一棵有n個(gè)葉子節(jié)點(diǎn)的赫夫曼樹共有2n-1個(gè)節(jié)點(diǎn)
int total = 2*n-1;
HT = (HuffmanTree)malloc((total)*sizeof(HTNode));
if(!HT){
printf("HuffmanTree malloc faild!");
exit(-1);
}
int i;
//HT[0..n-1]中存放需要編碼的n個(gè)葉子節(jié)點(diǎn)
for(i=0;i
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
HT[i].weight=*wet;
wet++;
}//HT[n..2n-2]中存放的是中間構(gòu)造出的每棵二叉樹的根節(jié)點(diǎn)
for(;i
int min1=0;
int min2=0;
//用來保存每一輪選出的兩個(gè)weight最小且parent為0的節(jié)點(diǎn)
//每一輪比較后選擇出min1和min2構(gòu)成一課二叉樹,
//最后構(gòu)成一棵赫夫曼樹
select_minium(HT, i, &min1, &min2);//選出兩個(gè)weight最小且parent為0的節(jié)點(diǎn)min1,min2
HT[min1].parent=i;
HT[min2].parent=i;
HT[i].lchild=min1;
HT[i].rchild=min2;
//這里左孩子和右孩子可以反過來，構(gòu)成的也是一棵赫夫曼樹，只是所得的編碼不同
HT[i].weight=HT[min1].weight + HT[min2].weight ;
HT[i].parent =0;
}
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, float *wet ,int n){
printf("\nHuffmanCoding...\n");
//用來保存指向每個(gè)赫夫曼編碼串的指針
HC = (HuffmanCode)malloc((n+1)*sizeof(char *));
if(!HC){
printf("HuffmanCode malloc faild!");
exit(-1);
}
int i, start, c, f;
for(i = 0; i <= M; i++)
HC[i] = (char *)malloc((M +1)* sizeof(char));
//臨時(shí)空間，用來保存每次求得的赫夫曼編碼串
char cd[M]={0};
if (!cd){
printf("code malloc faild!");
exit(-1);
}
cd[n-1] = '\0'; //編碼結(jié)束符，亦是字符數(shù)組的結(jié)束標(biāo)志
//求每個(gè)字符的赫夫曼編碼
for (i = 0; i < n; ++ i){//逐個(gè)字符求哈弗曼編碼
start = n -1 ;//編碼結(jié)束符的位置
for (c = i, f = HT[i].parent;f != 0; c =f, f = HT[f].parent)
//從葉子到跟逆向求哈弗曼編碼
if (HT[f].lchild == c )
cd[ -- start] = '0';//左孩子則為0
else
cd[ -- start ] = '1';//右孩子為1
HC[i] = (char *)malloc((n - start+1) * sizeof (char ));//為第i個(gè)字符編碼分配空間
strcpy(HC[i],&cd[start]);//從cd復(fù)制編碼串到HC
printf("字母%c 的哈弗曼編碼為 %s\n",'A'+i,HC[i]);
}
//free ( cd );
}//HuffmanCoding
void Read_File(char str[N]){//讀取文件內(nèi)容，并將文件中的字符串放在字符數(shù)組str[N]中
FILE *fp;
if((fp=fopen("E:\\VSProjects\\HuffmanTree\\Huffuman\\text.txt","rt"))==NULL){
printf("\nConnot open file!");//如果打開不成功則顯示不能打開文件
getchar();
exit(1);//關(guān)閉所有文件，終止正調(diào)用的過程
}
fgets(str,N,fp);
printf("文件內(nèi)容：\n");
printf("\n%s\n\n",str);
}
void Count(int Cnt[M], float wet[M], char str[N]){
//統(tǒng)計(jì)str中ABCD...出現(xiàn)的次數(shù)放在Cnt[M]中，計(jì)算頻率作為權(quán)值放在wet[M]中
int i,all_number;
all_number=0;
for (i=0;i
Cnt[i]=0;//計(jì)數(shù)初值賦值0
for (i=0;str[i] != '\0';i++){
Cnt[str[i]-'A']++;
all_number++;
}//統(tǒng)計(jì)各個(gè)字母出現(xiàn)次數(shù)
for (i=0;i
wet[i]= ((float)Cnt[i])/all_number;
}//計(jì)算頻率作為權(quán)值放在wet[M]中
//打印輸出各個(gè)字母的出現(xiàn)次數(shù)和權(quán)值
for (i = 0 ; i < M ; i ++){
printf("字母%c 出現(xiàn)的次數(shù)是 %d ,權(quán)值為 %f \n", 'A' + i, Cnt[i] ,wet[i]);
}
}
void decode(HuffmanTree &HT ){//依次讀入電文，根據(jù)哈夫曼樹譯碼
int i,j=0;
char ch[N];
i=2*M-1-1; //從根結(jié)點(diǎn)開始往下搜索
printf("輸入發(fā)送的編碼：");
gets(ch);
printf("譯碼后的字符為");
while(ch[j]){
if(ch[j]=='0')
i=HT[i].lchild; //走向左孩子
else
i=HT[i].rchild; //走向右孩子
if(HT[i].lchild==0) { //tree[i]是葉結(jié)點(diǎn)
printf("%c",'A'+i);
i=2*M-1-1; //回到根結(jié)點(diǎn)
}
j++;
}
printf("\n");
}//decode
void main ( void ){
char str[N];//文件中的字符串放在字符數(shù)組str[N]中
int Cnt[M];//統(tǒng)計(jì)各個(gè)字母出現(xiàn)次數(shù)放在數(shù)組Cnt[M]中
float wet[M];//頻率作為權(quán)值放在wet[M]中
HuffmanTree HT[2*M-1];//哈弗曼樹的結(jié)點(diǎn)，一共有2*M -1=51個(gè)
HuffmanCode HC[M];//哈弗曼編碼
Read_File(str);
//讀取文件內(nèi)容，并將文件中的字符串放在字符數(shù)組str[N]中
Count(Cnt, wet, str);
//統(tǒng)計(jì)str中ABCD...出現(xiàn)的次數(shù)放在Cnt[M]中，計(jì)算頻率作為權(quán)值放在wet[M]中
create_HuffmanTree(wet, M, *HT );//創(chuàng)建哈弗曼樹
HuffmanCoding(*HT, *HC, wet , M);//哈弗曼編碼
decode( *HT );//哈弗曼譯碼
}
|
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
