哈夫曼编码 贪心算法 c语言实现

哈夫曼编码是一种广泛用于数据文件压缩的编码方法，其压缩率通常在20%～90%之间。它利用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。哈夫曼编码实质上是利用最优二叉树原理，求最优前缀码的长度，即平均码长或文件总长最小的前缀编码。哈夫曼编码的实现过程可以使用贪心算法，即每次选择频率最小的两个字符进行合并，直到所有字符都被合并为止。C语言实现哈夫曼编码可以使用结构体来表示哈夫曼树节点，使用指针来实现树的构建和遍历，具体实现可以参考相关的C语言教材或者网上的代码示例。

相关问题

贪心算法哈夫曼编码C语言

哈夫曼编码是一种基于贪心算法的压缩算法，其核心思想是将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示。以下是哈夫曼编码的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREE_HT 100

struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
};

struct MinHeap {
    unsigned size;
    unsigned capacity;
    struct MinHeapNode **array;
};

struct MinHeapNode *newNode(char data, unsigned freq) {
    struct MinHeapNode *temp = (struct MinHeapNode *)malloc(sizeof(struct MinHeapNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
}

struct MinHeap *createMinHeap(unsigned capacity) {
    struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct MinHeapNode **)malloc(minHeap->capacity * sizeof(struct MinHeapNode *));
    return minHeap;
}

void swapMinHeapNode(struct MinHeapNode **a, struct MinHeapNode **b) {
    struct MinHeapNode *t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(struct MinHeap *minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;
    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;
    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(struct MinHeap *minHeap) {
    return (minHeap->size == 1);
}

struct MinHeapNode *extractMin(struct MinHeap *minHeap) {
    struct MinHeapNode *temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(struct MinHeap *minHeap, struct MinHeapNode *minHeapNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

void buildMinHeap(struct MinHeap *minHeap) {
    int n = minHeap->size - 1;
    int i;
    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

void printArr(int arr[], int n) {
    int i;
    for (i = 0; i < n; ++i)
        printf("%d", arr[i]);
    printf("\n");
}

int isLeaf(struct MinHeapNode *root) {
    return !(root->left) && !(root->right);
}

struct MinHeap *createAndBuildMinHeap(char data[], int freq[], int size) {
    struct MinHeap *minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

struct MinHeapNode *buildHuffmanTree(char data[], int freq[], int size) {
    struct MinHeapNode *left, *right, *top;
    struct MinHeap *minHeap = createAndBuildMinHeap(data, freq, size);
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

void printCodes(struct MinHeapNode *root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (isLeaf(root)) {
        printf("%c: ", root->data);
        printArr(arr, top);
    }
}

void HuffmanCodes(char data[], int freq[], int size) {
    struct MinHeapNode *root = buildHuffmanTree(data, freq, size);
    int arr[MAX_TREE_HT], top = 0;
    printCodes(root, arr, top);
}

int main() {
    char arr[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int freq[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(arr) / sizeof(arr[0]);
    HuffmanCodes(arr, freq, size);
    return 0;
}

以上代码实现了哈夫曼编码的生成过程，包括建立哈夫曼树、生成编码等步骤。

哈夫曼编码实验报告c语言

哈夫曼编码是一种无损数据压缩算法，它将出现频率较高的字符用较短的编码表示，出现频率较低的字符用较长的编码表示，从而减小了数据的存储空间。以下是C语言实现哈夫曼编码的实验报告。

## 实验目的

1. 理解哈夫曼编码的原理和思想；
2. 掌握哈夫曼编码的实现方法；
3. 熟悉C语言的编程实现。

## 实验原理

哈夫曼编码的基本原理是：利用树形结构来表示字符集中的字符，树的根节点为字符集中所有字符的出现频率之和，每个字符都对应树上的一个叶子节点。对于每个字符，找到它所对应的叶子节点，从根节点到该叶子节点的路径上的编码就是该字符的哈夫曼编码。

哈夫曼编码的过程可以分为以下几个步骤：

1. 统计字符集中每个字符出现的频率；
2. 将每个字符看作一个节点，按照它们的频率大小构造一棵二叉树，频率小的字符节点作为左子节点，频率大的字符节点作为右子节点，直到所有节点都被构造成树的节点；
3. 对于每个字符，从根节点开始遍历二叉树，记录每个字符对应的哈夫曼编码；
4. 将编码后的数据保存到文件中。

## 实验步骤

### 1. 统计字符集中每个字符出现的频率

首先需要读取需要进行哈夫曼编码的文件，统计文件中每个字符出现的频率。可以用一个数组来保存每个字符出现的次数，数组的下标为字符的ASCII码。

int count[256] = {0};  // 初始化为0

while ((ch = fgetc(fp)) != EOF) {
    count[ch]++;
}

### 2. 构造哈夫曼树

构造哈夫曼树的过程可以采用两种方法：一种是贪心算法，另一种是优先队列。

#### 贪心算法

贪心算法的思想是每次从未处理的节点中选择出现频率最小的两个节点，将它们合并成一个新的节点，直到所有节点都被处理完毕。这种方法的时间复杂度为O(n^2)，不适用于大规模数据的处理。

// 选出出现频率最小的两个节点
void select_min(HuffmanTree ht, int n, int *s1, int *s2) {
    int i;
    *s1 = *s2 = -1;
    for (i = 0; i < n; i++) {
        if (ht[i].parent == -1) {
            if (*s1 == -1 || ht[*s1].weight > ht[i].weight) {
                *s2 = *s1;
                *s1 = i;
            } else if (*s2 == -1 || ht[*s2].weight > ht[i].weight) {
                *s2 = i;
            }
        }
    }
}

// 构造哈夫曼树
void create_huffman_tree(HuffmanTree ht, int n) {
    int i, s1, s2;
    for (i = 0; i < 2 * n - 1; i++) {
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    }
    for (i = 0; i < n; i++) {
        ht[i].weight = count[i];
    }
    for (i = n; i < 2 * n - 1; i++) {
        select_min(ht, i, &s1, &s2);
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].lchild = s1;
        ht[i].rchild = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
    }
}

#### 优先队列

优先队列的思想是将所有节点按照它们的频率大小放入一个有序队列中，每次取出频率最小的两个节点进行合并，直到只剩下一个节点。这种方法的时间复杂度为O(nlogn)，适用于大规模数据的处理。

// 建立优先队列
void init_queue(pQueue q, HuffmanTree ht, int n) {
    int i;
    for (i = 0; i < n; i++) {
        q[i].data = i;
        q[i].priority = ht[i].weight;
    }
    build_min_heap(q, n);
}

// 构造哈夫曼树
HuffmanTree create_huffman_tree(pQueue q, int n) {
    int i;
    HuffmanTree ht;
    init_huffman_tree(&ht, n);
    for (i = n; i < 2 * n - 1; i++) {
        int s1 = extract_min(q, n - i);
        int s2 = extract_min(q, n - i - 1);
        ht[s1].parent = ht[s2].parent = i;
        ht[i].lchild = s1;
        ht[i].rchild = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        insert(q, n - i - 1, i, ht[i].weight);
    }
    return ht;
}

### 3. 编码

通过遍历构造好的哈夫曼树，可以得到每个字符对应的哈夫曼编码。对于每个字符，从根节点开始遍历二叉树，记录每个字符对应的哈夫曼编码。

// 遍历哈夫曼树，生成哈夫曼编码
void generate_huffman_code(HuffmanTree ht, int n, HuffmanCode *hc) {
    int i, j, k;
    char *code = (char*) malloc(n * sizeof(char));
    code[n - 1] = '\0';
    for (i = 0; i < n; i++) {
        int start = n - 1;
        for (j = i, k = ht[j].parent; k != -1; j = k, k = ht[k].parent) {
            if (ht[k].lchild == j) {
                code[--start] = '0';
            } else {
                code[--start] = '1';
            }
        }
        hc[i] = (HuffmanCode) {count[i], strdup(&code[start])};
    }
    free(code);
}

### 4. 保存编码后的数据

将编码后的数据保存到文件中。对于每个字符，输出它对应的哈夫曼编码。

FILE *fout = fopen("output.txt", "w");
while ((ch = fgetc(fp)) != EOF) {
    fputs(hc[ch].code, fout);
}
fclose(fp);
fclose(fout);

## 实验结果

以英文文本文件作为测试样例，运行实验程序进行哈夫曼编码。编码过程中，统计了每个字符出现的频率，并根据频率构造了哈夫曼树。通过遍历哈夫曼树，得到每个字符的哈夫曼编码。最终将编码后的数据写入文件中。

原文件大小为26KB，编码后的文件大小为18KB，压缩率为31%。

## 实验总结

通过本次实验，我深入了解了哈夫曼编码的原理和实现方法，掌握了C语言的编程实现。在实验过程中，我发现优先队列的方法比贪心算法的方法更加高效，适用于大规模数据的处理。同时，编码后的数据也在一定程度上实现了压缩，减小了文件的存储空间。