c语言实现霍夫曼编码代码

代码语言: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