資料結構【完整代碼】之（C語言實作【哈夫曼樹的存儲結構與建立】）

本文包含兩個檔案的代碼和一張測試效果圖：

• HuffmanTree.h檔案： 哈夫曼樹的存儲結構與建立函數
• HuffmanCreatTest.cpp檔案： 用于測試
• 效果圖：（如下）

效果圖：

#include <stdio.h>
#include <stdlib.h>
 
typedef struct{
    int weight;
    int parent,lchild,rchild;
}HTNode, *HuffmanTree;
 
void Select(HuffmanTree HT, int n, int *s1, int *s2)
{
    int minum;      // 定義一個臨時變量儲存最小值?
    for(int i = 1; i <= n; i++)     // 以下是找到第一個最小值
    {
        if(HT[i].parent == 0)
        {
            minum = i;
            break;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(HT[i].parent == 0)
            if(HT[i].weight < HT[minum].weight)
                minum = i;
    }
    *s1 = minum;
    // 以下是找到第二個最小值，且與第一個不同
    for(int i = 1; i <= n; i++)     
    {
        if(HT[i].parent == 0 && i != *s1)
        {
            minum = i;
            break;
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(HT[i].parent == 0 && i != *s1)
            if(HT[i].weight < HT[minum].weight)
                minum = i;
    }
    *s2 = minum;
}
 
void CreateHuffmanTree(HuffmanTree &HT, int *w, int n)
{
    if(n <= 1){
        return;
    }   
    int m, i, s1, s2;
    m = 2 * n - 1;
    HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); // 配置設定空間
    for(i = 1; i <= m; i++){ //将1~m号結點初始化 
        HT[i].weight = w[i];
        HT[i].parent = 0;
        HT[i].lchild = 0;
        HT[i].rchild = 0;
    }
    printf("\n哈夫曼樹是: \n");
    int num = 1;
    for(i = n + 1; i <= m; i++){ //通過n-1次的【選擇】、【删除】、【合并】來建立哈夫曼樹   
        
        //【選擇】在HT[k](1<=k<=i-1)中選擇兩個：雙親域為0且權值最小的結點，并傳回它們在HT中的序号s1和s2
        Select(HT, i-1, &s1, &s2);
        
        //【删除】得到新結點i，從森林中删除s1，s2，即将s1和s2的雙親域由0改為i 
        HT[s1].parent = i;
        HT[s2].parent = i;

        // 【合并】将s1和s2的權值和作為一個新結點的權值依次存入到數組的第n+1之後的單元中，同時記錄這個新結點左孩子的下标s1，右孩子的下标為s2
        HT[i].lchild = s1;
        HT[i].rchild = s2;
        HT[i].weight = HT[s1].weight + HT[s2].weight;
        if(i <= m - 1){
            printf("%d (%d, %d)\n", HT[i].weight, HT[s1].weight, HT[s2].weight);
        }
        else{
            printf("T: (%d, %d)\n", HT[s1].weight, HT[s2].weight);
        }
    }
    printf("\n");
}      

#include "HuffmanTree.h"

int main()
{
    HuffmanTree HT;
    int n;
    printf("輸入葉子結點的數量：");
    scanf("%d", &n);
    int w[n+1]; 
 
    for(int i=1; i<=n; i++)
    {
        printf("\n輸入第%d個結點的權值：", i);
        scanf("%d", &w[i]);
    }
    CreateHuffmanTree(HT, w, n);
}