(数据结构)哈夫曼编码实现(C语言)

这篇具有很好参考价值的文章主要介绍了(数据结构)哈夫曼编码实现(C语言)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

(数据结构)哈夫曼编码实现(C语言)

哈夫曼的编码:从一堆数组当中取出来最小的两个值,按照左下右大的进行绘制,将两个权值之和,放入队列当中,然后再进行取出两个小的,以此类推,直到全部结束,在根据图根节点,到叶子节点,每一个分支来得出编码,向左0,向右1,即可得到一个结果。文章来源地址https://www.toymoban.com/news/detail-605256.html

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

// 定义哈夫曼树结点的结构
struct Node {
    int frequency;
    char data;
    struct Node* left;
    struct Node* right;
};

// 创建一个新的哈夫曼树结点
struct Node* newNode(int frequency, char data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->frequency = frequency;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

struct MinHeap {
    int size;
    int capacity;
    struct Node** array;
};

// 创建最小堆
struct MinHeap* createMinHeap(int capacity) {
    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return minHeap;
}

// 交换两个结点的位置
void swapNode(struct Node** a, struct Node** b) {
    struct Node* temp = *a;
    *a = *b;
    *b = temp;
}

// 维护最小堆的性质
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]->frequency < minHeap->array[smallest]->frequency) {
        smallest = left;
    }

    if (right < minHeap->size && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency) {
        smallest = right;
    }

    if (smallest != idx) {
        swapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

// 检查最小堆是否只有一个元素
int isSizeOne(struct MinHeap* minHeap) {
    return minHeap->size == 1;
}

// 检查结点是否是叶子结点
int isLeaf(struct Node* root) {
    return !(root->left) && !(root->right);
}

// 从最小堆中提取最小值(即频率最小的结点)
struct Node* extractMin(struct MinHeap* minHeap) {
    struct Node* 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 Node* node) {
    ++minHeap->size;
    int i = minHeap->size - 1;

    while (i && node->frequency < minHeap->array[(i - 1) / 2]->frequency) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }

    minHeap->array[i] = node;
}

// 构建哈夫曼树
struct Node* buildHuffmanTree(char data[], int frequency[], int size) {
    struct Node *left, *right, *top;
    // 创建一个最小堆并初始化
    struct MinHeap* minHeap = createMinHeap(size);

    // 向最小堆中插入结点
    for (int i = 0; i < size; i++) {
        insertMinHeap(minHeap, newNode(frequency[i], data[i]));
    }

    // 构建哈夫曼树
    while (!isSizeOne(minHeap)) {
        // 从最小堆中取出最小的两个结点作为左子树和右子树
        left = extractMin(minHeap);
        right = extractMin(minHeap);

        // 创建一个新的结点作为父结点
        top = newNode(left->frequency + right->frequency, '-');
        top->left = left;
        top->right = right;

        // 将父结点插入最小堆中
        insertMinHeap(minHeap, top);
    }

    // 最后剩下的结点就是哈夫曼树的根结点
    return extractMin(minHeap);
}

// 打印哈夫曼编码
void printHuffmanCodes(struct Node* root, int arr[], int top) {
    // 叶子结点是存有字符的结点
    if (root->left) {
        arr[top] = 0;
        printHuffmanCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        printHuffmanCodes(root->right, arr, top + 1);
    }

    // 如果是叶子结点(没有左右子结点),则打印编码
    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

int main() {
    char data[] = { 'a', 'b', 'c', 'd', 'e' };
    int frequency[] = { 5, 9, 12, 13, 16 };
    int size = sizeof(data) / sizeof(data[0]);

    struct Node* root = buildHuffmanTree(data, frequency, size);

    int arr[100], top = 0;
    printHuffmanCodes(root, arr, top);

    return 0;
}

到了这里,关于(数据结构)哈夫曼编码实现(C语言)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构之哈夫曼树与哈夫曼编码

    编码是信息处理的基础(重新表示信息)。 普通的编码是等长编码,例如7位的ASCIL编码,对出现频率不同的字符都使用相同的编码长度。 但其在传输和存储等情况下编码效率不高 。 可使用不等长编码,来压缩编码:高频字符编码长度更短,低频字符编码长度更长。   [例

    2023年04月15日
    浏览(61)
  • 数据结构之哈夫曼树和哈夫曼编码

    切入正题之前,我们先了解几个概念: 路径:从树的一个结点到另一个结点分支所构成的路线 路径长度:路径上的分支数目 树的路径长度:从根结点出发到每个结点的路径长度之和 带权路径长度:该结点到根结点的路径长度乘以该结点的权值 树的带权路径长度:树中所有

    2024年02月11日
    浏览(43)
  • 数据结构课程实验五:哈夫曼树与哈夫曼编码

    实验日期:2022-12-20   目录 一、实验目的 1、掌握哈夫曼树的建立 2、掌握哈夫曼编码方式 二、实验内容

    2024年02月05日
    浏览(47)
  • 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法,并用代码实现。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度: 从树根到每一个结点的路径长度之和。记作: TL  权

    2024年02月06日
    浏览(51)
  • 【数据结构】实验十:哈夫曼编码

    实验十 哈夫曼编码 一、实验目的与要求 1 )掌握树、森林与二叉树的转换; 2 )掌握哈夫曼树和哈夫曼编码算法的实现; 二、 实验内容 1.  请编程实现如图所示的树转化为二叉树。 2.  编程实现一个哈夫曼编码系统,系统功能包括: (1)  字符信息统计:读取待编码的源文

    2024年02月15日
    浏览(45)
  • 【数据结构--哈夫曼编码(C语言版)】

    哈夫曼树 介绍哈夫曼树前先介绍下面几个名词: 1. 结点的路径长度 l 从根结点到该结点的路径上分支的数目 ,如下图结点 a 的 l = 3 。 2. 树的路径长度 树中所有叶子结点的路径长度之和 ,如下图该树的路径长度为 2 + 3 + 3 + 2 + 2 。 3. 结点的权 w 给每一个结点赋予一个新的数

    2024年02月04日
    浏览(47)
  • 数据结构 实验17:Huffman树和Huffman编码——学习理解哈夫曼树

    目录 前言 实验要求 算法描述 个人想法 代码实现和思路、知识点讲解 知识点讲解 文件传输 Huffman树的存储 Huffman的构造  Huffman编码 编码和译码 代码实现 文件写入和输出 Huffman树初始化 构造Huffman树 求带权路径长度 Huffman编码 Huffman译码 结束 代码测试 测试结果 利用Huffman编

    2024年02月03日
    浏览(58)
  • 数据结构实验五:哈夫曼树的设计及实现

    实验五   哈夫曼 树的设计及实现 一、实验目的 1. 掌握哈夫曼树的构造算法,理解二叉树的应用; 2. 掌握哈夫曼编码的构造算法。 二、实验内容 输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行

    2024年02月09日
    浏览(449)
  • 数据结构课程设计——哈夫曼编/译码系统设计与实现(C++)

    对于生产实际的问题,本设计可以作为一个无损数据压缩工具,在需要传输海量数据时,利用哈夫曼编码可以将数据进行压缩,从而减小传输的数据量,提高数据传输效率。同时,哈夫曼编码也可以应用于数据加密和解密等领域。 本设计的主要目的是学习哈夫曼编码算法,并

    2024年02月04日
    浏览(47)
  • 数据结构【哈夫曼树】

    最优二叉树也称哈夫曼 (Huffman) 树 ,是指对于一组带有确定权值的叶子结点,构造的具有最小带权路径长度的二叉树。权值是指一个与特定结点相关的数值。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 涉及到的几个概念: 路径: 从树中一个结点到另一个结

    2024年02月14日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包