定义相关结构体和常量

#define _CRT_SECURE_NO_WARNINGS
#include 
   
    
#include 
    
     
#define Minweight -1
typedef struct Node* ElementType;
struct Node {
    int Weight;
    char Key;
};
typedef struct HfTNode* HuffmanTree;
struct HfTNode {
    ElementType Data;
    HuffmanTree Left, Right;
};
typedef struct Heapstruct* MinHeap;
struct Heapstruct {
    HuffmanTree* Elements;
    int Size;
    int Capacity;
};
typedef struct SNode* PtrToSNode;
struct SNode {
    ElementType Data;
    PtrToSNode Next;
};
typedef PtrToSNode Stack;
Stack CreateStack(void);
int IsEmpty_Stack(Stack);
void Push(Stack, ElementType);
ElementType Pop(Stack);
ElementType GetStackTop(Stack);

创建堆结构

MinHeap CreateMinHeap(int MaxSize) {
    MinHeap H;
    H = (MinHeap)malloc(sizeof(struct Heapstruct));
    H->Elements = (HuffmanTree*)malloc(sizeof(HuffmanTree) * (MaxSize + 1));
    H->Size = MaxSize;
    H->Capacity = MaxSize;
    
    // 初始化第一个元素
    H->Elements[0] = (HuffmanTree)malloc(sizeof(struct HfTNode));
    H->Elements[0]->Data = (ElementType)malloc(sizeof(struct Node));
    H->Elements[0]->Data->Weight = Minweight;
    
    return H;
}

堆操作函数

int IsEmpty_MinHeap(MinHeap H) {
    return H->Size == 0;
}
int IsFull_MinHeap(MinHeap H) {
    return H->Size == H->Capacity;
}
void Insert_MinHeap(MinHeap H, HuffmanTree Item) {
    int i;
    if (IsFull_MinHeap(H)) return;
    
    i = ++H->Size; // i相当于子结点下标，i/2相当于父结点下标
    for (; H->Elements[i / 2]->Data->Weight > Item->Data->Weight; i /= 2) {
        H->Elements[i] = H->Elements[i / 2];
    }
    H->Elements[i] = Item;
}

删除堆中的最小元素

HuffmanTree Delete_MinHeap(MinHeap H) {
    HuffmanTree Item, MinItem;
    int Parent, Child;
    
    if (IsEmpty_MinHeap(H)) return NULL;
    
    MinItem = H->Elements[1];
    Item = H->Elements[H->Size--];
    
    for (Parent = 1; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if (H->Elements[Child]->Data->Weight > H->Elements[Child + 1]->Data->Weight)
            Child++;
        
        if (H->Elements[Child]->Data->Weight > Item->Data->Weight)
            break;
        else
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = Item;
    
    return MinItem;
}

哈弗曼编码的构建过程

void MinMaking(MinHeap H, int Root) {
    int Parent, Child;
    HuffmanTree Item;
    
    Item = H->Elements[Root];
    for (Parent = Root; Parent * 2 <= H->Size; Parent = Child) {
        Child = Parent * 2;
        if (Child + 1 < H->Size && H->Elements[Child]->Data->Weight > H->Elements[Child + 1]->Data->Weight)
            Child++;
        
        if (H->Elements[Child]->Data->Weight > Item->Data->Weight)
            break;
        else
            H->Elements[Parent] = H->Elements[Child];
    }
    H->Elements[Parent] = Item;
}

主函数实现

int main() {
    Stack S;
    int MaxSize;
    
    HuffmanTree T;
    S = CreateStack();
    
    do {
        printf("输入关键字个数\n");
        scanf("%d", &MaxSize);
        getchar();
        if (MaxSize <= 1) {
            printf("不必为%d个关键字编码\n", MaxSize);
        } else
            break;
    } while (1);
    
    MinHeap H = CreateMinHeap(MaxSize);
    
    for (int i = 1; i <= MaxSize; i++) {
        H->Elements[i] = (HuffmanTree)malloc(sizeof(struct HfTNode));
        H->Elements[i]->Left = NULL;
        H->Elements[i]->Right = NULL;
        H->Elements[i]->Data = (ElementType)malloc(sizeof(struct Node));
        
        printf("输入关键字及出现频率\n");
        scanf("%c %d", &H->Elements[i]->Data->Key, &H->Elements[i]->Data->Weight);
        getchar();
    }
    
    T = Huffman(H);
    
    // 打印哈弗曼树的编码
    PrintPath(T);
}

哈弗曼树编码生成函数

void PrintPath(HuffmanTree T) {
    HuffmanTree PtoT;
    HuffmanTree Root;
    char Word[10];
    int i = 0;
    
    while (T->Data->Key != -1) {
        PtoT = T;
        Root = PtoT;
        i = 0;
        
        while (1) {
            if (!PtoT->Left && !PtoT->Right) {
                Word[i++] = PtoT->Data->Key;
                Word[i] = '\0';
                printf("%s\n", Word);
                PtoT->Data->Key = -1;
                
                if ((!Root->Left || Root->Left->Data->Key == -1) &&
                    (!Root->Right || Root->Right->Data->Key == -1))
                    Root->Data->Key = -1;
                
                break;
            } else if (PtoT->Left && PtoT->Left->Data->Key != -1) {
                Word[i++] = '1';
                Root = PtoT;
                PtoT = PtoT->Left;
                continue;
            } else if (PtoT->Right && PtoT->Right->Data->Key != -1) {
                Word[i++] = '0';
                Root = PtoT;
                PtoT = PtoT->Right;
                continue;
            }
            
            PtoT->Data->Key = -1;
            break;
        }
    }
}