大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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);
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/209949.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...