C语言实现哈夫曼编码_哈夫曼编码压缩文件c语言

C语言实现哈夫曼编码_哈夫曼编码压缩文件c语言////霍夫曼编码//#include<stdio.h>#include<stdlib.h>#include<string.h>/**思路:用一个有序链表(从大到小)来保存节点,然后通过链表来构造霍夫曼树,再由霍夫曼树得到霍夫曼编码**/typedefstructhuffman_tree_node{intwe…………

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

//
// 霍夫曼编码
//
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/**思路:用一个有序链表(从大到小)来保存节点,然后通过链表来构造霍夫曼树, 再由霍夫曼树得到霍夫曼编码**/
 
typedef struct huffman_tree_node{
    int weight;//权重
    char c;//字符 非叶子节点为0
    struct huffman_tree_node * nextHuffmanTreeNode;//链表下一个节点
    struct huffman_tree_node * leftHuffmanTreeNode;//左节点
    struct huffman_tree_node * rightHuffmanTreeNode;//右节点
}HuffmanTreeNode; //霍夫曼树节点
 
typedef struct huffman_code{
    char *s;//编码 如  010, 00, ....
    int len;//编码长度
    char c;//字符
}HuffmanCode; //霍夫曼编码(可以用来保存结果)
 
/**
 * 创建一个节点
 * @param c  字符
 * @param weight 权重
 * @return
 */
HuffmanTreeNode * createHuffmanTreeNode(char c, int weight){
    HuffmanTreeNode * node = (HuffmanTreeNode *)calloc(1, sizeof(HuffmanTreeNode));
    node->c = c;
    node->weight = weight;
    node->nextHuffmanTreeNode = NULL;
    node->leftHuffmanTreeNode = NULL;
    node->rightHuffmanTreeNode = NULL;
    return node;
}
 
/**
 * [insert 插入节点到有序链表中]
 * @param  h [头节点指针]
 * @param  s [要插入的节点]
 * @return   [头节点]
 */
static HuffmanTreeNode * insert(HuffmanTreeNode * h, HuffmanTreeNode * s){
    if(h == NULL){ //插入第一个节点时 没有头节点
        return s;//s作为头节点
    }
    if(s->weight > h->weight){
        s->nextHuffmanTreeNode = h; //s作为头节点
        return s;
    }
 
    HuffmanTreeNode * tempHuffmanTreeNode = h; //中间变量 用于遍历
    HuffmanTreeNode * preHuffmanTreeNode = tempHuffmanTreeNode;//中间变量的前一个节点
    while(tempHuffmanTreeNode != NULL){
        if(s->weight < tempHuffmanTreeNode->weight){ //要插入的节点的学号比当前节点小
            preHuffmanTreeNode = tempHuffmanTreeNode;
            tempHuffmanTreeNode = tempHuffmanTreeNode->nextHuffmanTreeNode;
            continue;
        }
        //插入到中间
        preHuffmanTreeNode->nextHuffmanTreeNode = s;
        s->nextHuffmanTreeNode = tempHuffmanTreeNode;
        break;
    }
    if(tempHuffmanTreeNode == NULL){ //插入的节点比已有的节点都小
        preHuffmanTreeNode->nextHuffmanTreeNode = s;
    }
    return h;
}
 
/**
 * 移除最后一个节点(最小的那个) 并返回
 * @param node
 * @return
 */
HuffmanTreeNode * removeLastHuffmanTreeNode(HuffmanTreeNode * h){
    HuffmanTreeNode * tempHuffmanTreeNode = h; //中间变量 用于遍历
    HuffmanTreeNode * preHuffmanTreeNode = tempHuffmanTreeNode;//中间变量的前一个节点
    while(tempHuffmanTreeNode->nextHuffmanTreeNode != NULL){
            preHuffmanTreeNode = tempHuffmanTreeNode;
            tempHuffmanTreeNode = tempHuffmanTreeNode->nextHuffmanTreeNode;
        }
        preHuffmanTreeNode->nextHuffmanTreeNode = NULL;
    return tempHuffmanTreeNode;
}
 
/**
 * 链表转霍夫曼树
 * @param head
 * @return
 */
HuffmanTreeNode * createTree(HuffmanTreeNode * head){
    if(head == NULL){
        return NULL;
    }
    while (1){
        //获取最小的两个节点
        HuffmanTreeNode * node1 = removeLastHuffmanTreeNode(head);
        if(node1 == head){ //只有一个节点了 完成
            return node1;
        }
        HuffmanTreeNode * node2 = removeLastHuffmanTreeNode(head);
        if(node2 == head){ //最后一个节点
            head = NULL; //头节点置为NULL
        }
        //创建一个新的节点
        HuffmanTreeNode * newNode = createHuffmanTreeNode(0, node1->weight+node2->weight);
        //设置左节点
        newNode->leftHuffmanTreeNode = node1->weight <= node2->weight ? node1 : node2;
        //设置右节点
        newNode->rightHuffmanTreeNode = node1->weight <= node2->weight ? node2 : node1;
        //新节点插入到链表中,再次循环 直到链表中只有一个节点
        head = insert(head, newNode);
    }
}
 
/**
 * 字符串拷贝
 * @param s
 * @param len
 * @param dest
 */
void str_copy(char *s,int len ,char *dest){
    for(int i = 0; i < len; i++){
        dest[i] = s[i];
    }
}
 
/**
 * 霍夫曼编码
 * @param node 节点
 * @param s 编码的字符串 如 001,00,01...
 * @param len 编码字符串的长度
 */
void showCode(HuffmanTreeNode * node, char *s, int len){
    if(node->c != 0){ //到叶子节点了
        //打印编码结果(或保存到结构体中):
        printf("%c->%s\n", node->c, s);
        free(s);
        return;
    }
    //遍历左节点 编码增加一个0
    char * leftS = (char *)calloc(len+1, sizeof(char));
    str_copy(s, len, leftS);
    leftS[len] = '0';
    showCode(node->leftHuffmanTreeNode, leftS, len+1);
 
    //遍历右节点 编码增加一个1
    char * rightS = (char *)calloc(len+1, sizeof(char));
    str_copy(s, len, rightS);
    rightS[len] = '1';
    showCode(node->rightHuffmanTreeNode, rightS, len+1);
	
    free(s);
 
}
int main(){
    //创建节点
    HuffmanTreeNode * head = NULL;
    HuffmanTreeNode * node_a = createHuffmanTreeNode('A', 5);
    HuffmanTreeNode * node_b = createHuffmanTreeNode('B', 4);
    HuffmanTreeNode * node_c = createHuffmanTreeNode('C', 3);
    HuffmanTreeNode * node_d = createHuffmanTreeNode('D', 2);
    HuffmanTreeNode * node_e = createHuffmanTreeNode('E', 1);
    //插入到有序链表中
    head = insert(head,node_a);
    head = insert(head,node_b);
    head = insert(head,node_c);
    head = insert(head,node_d);
    head = insert(head,node_e);
    //转霍夫曼树
    HuffmanTreeNode *tree =  createTree(head);
    printf("huffman encode:\n");
    //获取编码
	char * s  = (char*)malloc(0);
    showCode(tree, s, 0);
 
}

Jetbrains全家桶1年46,售后保障稳定

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/209949.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • SQL语句多表连接查询语法

    SQL语句多表连接查询语法总结:内连接就是两个表的交集,左外连接就是左边表加两表交集,右外连接就是右边表加两表交集一、外连接1.左连接leftjoin或leftouterjoinSQL语句:select*fromstudentleftjoinscoreonstudent.Num=score.Stu_id;2.右连接rightjoin或r…

  • Dubbo服务降级

    Dubbo服务降级dubbo降级服务使用dubbo在进行服务调用时,可能由于各种原因(服务器宕机/网络超时/并发数太高等),调用中就会出现RpcException,调用失败。服务降级就是指在由于非业务异常导致的服务不可用时(上面举得例子),可以返回默认值,避免异常影响主业务的处理。官方dubbo3.0-给出的服务降级RegistryFactoryregistryFactory=ExtensionLoader.getExtensionLoader(RegistryFactory.class)

  • idea入门与实战(实战训练)

    工作中多人使用版本控制软件协作开发,常见的应用场景归纳如下:假设小组中有两个人,组长小张,组员小袁场景一:小张创建项目并提交到远程Git仓库场景二:小袁从远程Git仓库上获取项目源码场景三:小袁修改了部分源码,提交到远程仓库场景四:小张从远程仓库获取小袁的提交场景五:小袁接受了一个新功能的任务,创建了一个分支并在分支上开发场景六:小袁把分支提交到远程Git仓库场景七…

  • rk3399调试ov2659(camera模块@dvp接口)–源码分析

    rk3399调试ov2659(camera模块@dvp接口)–源码分析  之前整理的“rockchipsensorcore框架”和rkisp下的v4l2框架有点像,只不过v4l2框架有点大(而且不支持摄像头热插拔)。其实接触越多Linux子系统越发觉得这些子系统处理思想大同小异。   这种"核…

  • Mysql 查询优化

    Mysql 查询优化

  • Matlab 分段函数怎么画 表示方式 (推荐)

    Matlab 分段函数怎么画 表示方式 (推荐)在很长一段时间里面,我都只用上了连续或可导函数(也指那种可以用一个函数表达式表示),结果在这次布置的作业必须要用到分段函数,如下图,总不能通过一条线一条线的plot出来吧。对于这样一个分段函数而言,有以下两种方式可以很好的解决利用逻辑表达式比如第一个就可以表示为:即当t在某一个范围内那段函数才生效,否则乘上逻辑式因子就为0,得到的效果图如下:利用阶跃函数Heavisi…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号