前面我們介紹了哈夫曼樹的理論實現(xiàn)，現(xiàn)在介紹一下具體代碼實現(xiàn)报强。
我們先定義哈夫曼樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)灸姊。
struct haffManTreeNode // 哈夫曼樹的節(jié)點
{
char symbol; //存儲的符號
int weight; //權(quán)重
haffManTreeNode* lChild;
haffManTreeNode* rChild;
};
struct haffManTreeRoot //為了方便，特別定義一個根節(jié)點
{
haffManTreeNode* next;
};
haffManTreeNode* initHaffManTreeNode(char symbol,int weight)
{
//初始化一個樹節(jié)點
haffManTreeNode* tree = new haffManTreeNode;
tree->lChild = NULL;
tree->rChild = NULL;
tree->symbol = symbol;
tree->weight = weight;
return tree;
}
在有了樹節(jié)點之后秉溉，我們需要一個鏈表結(jié)構(gòu)來存儲不同節(jié)點的權(quán)值力惯，并將他們排序，用這些節(jié)點來構(gòu)成我們的哈夫曼樹召嘶。
struct haffManQueue //定義的鏈表結(jié)構(gòu)
{
haffManTreeNode* tree; //存儲哈夫曼樹的節(jié)點
int weight; //節(jié)點的權(quán)重
haffManQueue* next;
};
struct haffManQueueHead //為了方便父晶，定義一個頭鏈表，存儲鏈表大小
{
int size;
haffManQueue* next;
};
haffManQueue* initQueue()
{
//初始化鏈表節(jié)點
haffManQueue* queue = new haffManQueue;
queue->weight = 0;
queue->tree = NULL;
queue->next = NULL;
return queue;
}
在定義完了最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)后弄跌，我們需要獲得一個數(shù)組甲喝，用來存儲一段文本的單個字符出現(xiàn)次數(shù)（權(quán)重），這里铛只，我們利用數(shù)組下標實現(xiàn)這個功能埠胖。
void getWeight(string& str,int (&weight)[256])
{
//在這里，我們傳入一個數(shù)組淳玩，與文本字符串
//注：（1）我們需要傳入數(shù)組的引用直撤，因為我們需要用形參影響實參
//（2）我們傳入的數(shù)組大小為256位，正好是全部字符的個數(shù)
for(int i=0;i <= 255;i++)
{
//初始化數(shù)組
weight[i] = 0;
}
int count = str.length();
for(int i=0;i < count;i++)
{
//利用ascii碼唯一對應的數(shù)字來標注
weight[ (char)str[i] ]++;
}
}
接下來蜕着，我們擁有了這個權(quán)重數(shù)組谋竖，那么我們需要的就是按照哈夫曼樹的建立過程實現(xiàn)代碼。
//先定義插入函數(shù)承匣，可以更加簡單蓖乘。。悄雅。這里寫的有些復雜
//注：同樣驱敲，我們需要傳入head的引用，因為我們需要在函數(shù)中改變其中指針的值
void insertQueue(haffManQueueHead* (&head),haffManQueue* (&inserter),haffManQueue* (&address))
{
//在address指針后面插入inserter指針宽闲，若address為NULL众眨，則表示在表頭后插入
if(address == NULL)
{
inserter->next = head->next;
head->next = inserter;
}
else if(address->next == NULL)
{
address->next = inserter;
}
else
{
inserter->next = address->next;
address->next = inserter;
}
}
//定義取值函數(shù)，取出當前鏈表中權(quán)重最小的節(jié)點
haffManQueue* getQueueItem(haffManQueueHead* (&head))
{
if(head->size == 0)
{
return NULL;
}
haffManQueue* temp = head->next;
head->next = head->next->next;
head->size--;
return temp;
}
//由權(quán)重數(shù)組容诬，得到哈夫曼隊列
haffManQueueHead* initHaffManQueue(int (&weight)[256])
{
//建立表頭
haffManQueueHead* head = new haffManQueueHead;
head->next = NULL;
head->size = 0;
for(int i=0;i <= 255;i++)
{
if(weight[i] != 0)
{
if(head->size == 0)
{
//如果整個鏈表沒有元素娩梨，直接插入為第一個
haffManQueue* queue = initQueue();
queue->tree = initHaffManTreeNode((char)i,weight[i]);
queue->weight = queue->tree->weight;
head->next = queue;
head->size++;
}
else
{
haffManQueue* queue = initQueue();
queue->tree = initHaffManTreeNode((char)i,weight[i]);
queue->weight = queue->tree->weight;
//定義兩個指針，用來插入節(jié)點
haffManQueue* temp = head->next;
//指向當前節(jié)點的前一個元素览徒，因為是單向鏈表狈定，無法知道之前的元素地址
haffManQueue* preNode = NULL;
while(queue->weight > temp->weight && temp != NULL)
{
preNode = temp;
temp = temp->next;
}
insertQueue(head,queue,preNode);
head->size++;
}
}
}
return head;
}
//在得到哈夫曼隊列之后，我們便可以建立我們的哈夫曼樹了
haffManTreeRoot* creataHaffManTree(haffManQueueHead* (&head))
{
//初始化哈夫曼樹的根節(jié)點
haffManTreeRoot* root = new haffManTreeRoot;
root->next = NULL;
if(head->size == 0)
{
return root;
}
else
{
while(head->size != 1)
{
//當鏈表大小為一時，退出循環(huán)
haffManQueue* lChild = getQueueItem(head);
haffManQueue* rChild = getQueueItem(head);
haffManQueue* newNode = initQueue();
//用'\0'纽什，來填充新節(jié)點的符號位措嵌，權(quán)重為兩個子樹權(quán)重之和
newNode->tree = initHaffManTree('\0',lChild->weight+rChild->weight);
//將兩個節(jié)點作為新節(jié)點的子樹
newNode->tree->lChild = lChild->tree;
newNode->tree->rChild = rChild->tree;
newNode->weight = newNode->tree->weight;
//重新插入回鏈表，排序
if(head->size == 0)
{
head->next = newNode;
head->size++;
}
else
{
haffManQueue* temp = head->next;
haffManQueue* preNode = NULL;
while(newNode->weight > temp->weight && temp != NULL)
{
preNode = temp;
temp = temp->next;
}
insertQueue(head,newNode,preNode);
head->size++;
}
}
}
root->next = head->next->tree;
return root;
}
這就是我個人關(guān)于哈夫曼樹的實現(xiàn)過程芦缰。
