c语言实现霍夫曼编码代码
代码语言:c
所属分类:其他
代码描述:c语言实现霍夫曼编码代码
下面为部分代码预览,完整代码请点击下载或在bfwstudio webide中打开
//
// 霍夫曼编码
//
#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;
}
.........完整代码请登录后点击上方下载按钮下载查看
网友评论0