本文共 4613 字，大约阅读时间需要 15 分钟。

数据压缩中的编码问题实验

定义相关结构体和常量

#define _CRT_SECURE_NO_WARNINGS#include 
   
    #include 
    
     #define Minweight -1typedef 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;        }    }}

转载地址：http://ivbr.baihongyu.com/