C语言实现哈夫曼编码

本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下

代码来自于《小甲鱼C++快速入门》

主程序main.cpp

#include "stdafx.h"
#include <stdlib.h>
#include "huffman.h"
int main()
{
 htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树
 hlTable *codeTable = buildTable(codeTree);//建立编码表
 encode(codeTable,"I love FishC.com!");//对输入的字符串进行编码
 decode(codeTree,"0011111000111");//解码
 system("pause");
 return 0;
}

两个头文件:
huffman.h:定义了哈夫曼树和编码表的结构

#pragma once
#ifndef _HUFFMAN_H
#define _HUFFMAN_H
typedef struct _htNode{
 char symbol;
 struct _htNode *left,*right;
}htNode;

typedef struct _htTree{
 htNode *root;
}htTree;

typedef struct _hlNode{
 char symbol;
 char *code;
 struct _hlNode *next;
}hlNode;

typedef struct _hlTable{
 hlNode *first;
 hlNode *last;
}hlTable;

htTree *buildTree(char *str);
hlTable *buildTable(htTree *huffmanTree);
void encode(hlTable *table, char *stringToEncode);
void decode(htTree *tree, char *stringToDecode);
#endif

queue.h:定义了有序队列的结构,将字符按优先级排列,即频率从小到大排列,val是树节点,直接由队列建立起哈夫曼树

#pragma once
#ifndef _PQUEUE_H
#define _PQUEUE_H
#include "huffman.h"
#define MAX_SZ 256
#define TYPE htNode *

typedef struct _pQueueNode{
 TYPE val;
 unsigned int priority;
 struct _pQueueNode *next;
}pQueueNode;

typedef struct _pQueue{
 unsigned int size;
 pQueueNode *first;
}pQueue;

void initPQueue(pQueue **queue);
void addPQueue(pQueue **queue, TYPE val, unsigned int priority);
TYPE getQueue(pQueue **queue);
#endif

两个cpp文件实现两个头文件声明的函数:
huffman.cpp

#include "stdafx.h"
#include "queue.h"
#include "huffman.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
htTree *buildTree(char *str)
{
 int *probability = (int *)malloc(sizeof(int) * 256);
 //初始化
 for (int i = 0; i < 256; i++)
 {
 probability[i] = 0;
 }
 //统计待编码的字符串各个字符出现的次数
 for (int j = 0; str[j] != '\0'; j++)
 {
 probability[str[j]]++;
 }

 //定义队列的头指针
 pQueue *huffmanQueue;
 initPQueue(&huffmanQueue);
 //填充队列
 for (int k = 0; k < 256; k++)
 {
 if (probability[k] != 0)
 {
  htNode *aux = (htNode *)malloc(sizeof(htNode));
  aux->left = NULL;
  aux->right = NULL;
  aux->symbol = (char)k;
  addPQueue(&huffmanQueue, aux, probability[k]);
 }
 }
 free(probability);
 //生成哈夫曼树
 while (huffmanQueue->size != 1)
 {
 unsigned int newPriority = huffmanQueue->first->priority + huffmanQueue->first->next->priority;
 htNode *aux = (htNode *)malloc(sizeof(htNode));
 aux->left = getQueue(&huffmanQueue);
 aux->right = getQueue(&huffmanQueue);
 addPQueue(&huffmanQueue, aux, newPriority);
 }
 htTree *tree = (htTree *)malloc(sizeof(htTree));
 tree->root = getQueue(&huffmanQueue);
 return tree;
}

void traverseTree(htNode *treeNode,hlTable **table,int k,char code[256])
{
 if (treeNode->left == NULL&&treeNode->right == NULL)
 {
 code[k] = '\0';
 hlNode *aux = (hlNode *)malloc(sizeof(hlNode));
 aux->code = (char *)malloc(sizeof(char)*(strlen(code) + 1));
   strcpy(aux->code,code);
 aux->symbol = treeNode->symbol;
 aux->next = NULL;
 if ((*table)->first == NULL)
 {
  (*table)->first = aux;
  (*table)->last = aux;
 }
 else
 {
  (*table)->last->next = aux;
  (*table)->last = aux;
 }
 }
 if (treeNode->left != NULL)
 {
 code[k] = '0';
 traverseTree(treeNode->left,table,k+1,code);
 }
 if (treeNode->right != NULL)
 {
 code[k] = '1';
 traverseTree(treeNode->right, table, k + 1, code);
 }
}

hlTable *buildTable(htTree *huffmanTree)
{
 hlTable *table = (hlTable *)malloc(sizeof(hlTable));
 table->first = NULL;
 table->last = NULL;

 char code[256];
 int k = 0;

 traverseTree(huffmanTree->root,&table,k,code);
 return table;
}
void encode(hlTable *table, char *stringToEncode)
{
 hlNode *traversal;
 printf("Encoding......\n\nInput string:\n%s\n\nEncoded string :\n",stringToEncode);
 for (int i = 0; stringToEncode[i] != '\0'; i++)
 {
 traversal = table->first;
 while (traversal->symbol != stringToEncode[i])
  traversal = traversal->next;
 printf("%s", traversal->code);
 }
 printf("\n");
}
void decode(htTree *tree,char *stringToDecode)
{
 htNode *traversal = tree->root;

 printf("\n\nDecoding......\n\nInput string: \n%s\n\nDecoded string: \n",stringToDecode);
 for (int i = 0; stringToDecode[i] != '\0'; i++)
 {
 if (traversal->left == NULL&&traversal->right == NULL)
 {
  printf("%c", traversal->symbol);
  traversal = tree->root;
 }
 if (stringToDecode[i] == '0')
  traversal = traversal->left;
 else if (stringToDecode[i] == '1')
  traversal = traversal->right;
 else
 {
  printf("The input string is not coded correctly!\n");
  return;
 }
 }
 printf("\n\n");
 return;
}

queue.cpp:

#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
#include "queue.h"
void initPQueue(pQueue **queue)
{
 *queue = (pQueue *)malloc(sizeof(pQueue));
 (*queue)->first = NULL;
 (*queue)->size = 0;
 return;
}
void addPQueue(pQueue **queue, TYPE val, unsigned int priority)
{
 if ((*queue)->size == MAX_SZ)
 {
 printf("\n Queue is full. \n");
 return;
 }
 pQueueNode *aux = (pQueueNode *)malloc(sizeof(pQueueNode));
 aux->priority = priority;
 aux->val = val;
 if ((*queue)->size == 0||(*queue)->first==NULL)
 {
 aux->next = NULL;
 (*queue)->first = aux;
 (*queue)->size = 1;
 return;
 }
 else
 {
 if (priority <= (*queue)->first->priority)
 {
  aux->next = (*queue)->first;
  (*queue)->first = aux;
  (*queue)->size++;
  return;
 }
 else
 {
  pQueueNode *iterator = (*queue)->first;
  while (iterator->next!=NULL)
  {
  if (priority <= iterator->next->priority)
  {
   aux->next = iterator->next;
   iterator->next = aux;
   (*queue)->size++;
   return;
  }
  iterator = iterator->next;
  }
  if (iterator->next == NULL)
  {
  aux->next = NULL;
  iterator->next = aux;
  (*queue)->size++;
  return;
  }
 }
 }
}
TYPE getQueue(pQueue **queue)
{
 TYPE returnValue;
 if ((*queue)->size > 0)
 {
 returnValue = (*queue)->first->val;
 (*queue)->first = (*queue)->first->next;
 (*queue)->size--;
 }
 else
 {
 returnValue = NULL;
 printf("\n Queue is empty \n");
 }

 return returnValue;
}

运行结果:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • C++实现哈夫曼编码

    本文实例为大家分享了C++实现哈夫曼编码的具体代码,供大家参考,具体内容如下 #include<iostream> #include<string> #include<vector> #include<algorithm> using namespace std; int Max = 300; class tree{ public: char s; int num; tree *left; tree *right; tree(){ s= '!'; num =

  • C++实现哈夫曼树编码解码

    本文实例为大家分享了C++实现哈夫曼树的编码解码,供大家参考,具体内容如下 代码: #pragma once #include<iostream> #include<stack> using namespace std; #define m 20 stack<int> s; /*哈夫曼树结点类HuffmanNode声明*/ template<class T> class HuffmanNode { private: HuffmanNode<T>

  • 解析C++哈夫曼树编码和译码的实现

    一.背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 二.实现步骤: 1.构造一棵哈夫曼树 2.根据创建好的哈夫曼树创建一张哈夫曼编码表 3.输入一串哈夫曼序列,输出原始字符 三.设计思想: 1.首先要构造一棵哈夫曼树,哈夫曼树的结点结构包括权值,双亲,左右孩子:假如由n个字符来构造一棵哈夫曼树,则共有结点2n-1个:在构造前,先初始化

  • 基于C++实现的哈夫曼编码解码操作示例

    本文实例讲述了基于C++实现的哈夫曼编码解码操作.分享给大家供大家参考,具体如下: 哈夫曼编码是一个通过哈夫曼树进行的一种编码,一般情况下,以字符:'0'与'1'表示.编码的实现过程很简单,只要实现哈夫曼树,通过遍历哈夫曼树,这里我们从每一个叶子结点开始向上遍历,如果该结点为父节点的左孩子,则在字符串后面追加"0",如果为其右孩子,则在字符串后追加"1".结束条件为没有父节点.然后将字符串倒过来存入结点中. C++实现代码如下: #include<iostre

  • C语言实现哈夫曼编码

    本文实例为大家分享了C语言实现哈夫曼编码的具体代码,供大家参考,具体内容如下 代码来自于<小甲鱼C++快速入门> 主程序main.cpp #include "stdafx.h" #include <stdlib.h> #include "huffman.h" int main() { htTree *codeTree = buildTree("I love wwwwwwwwwFishC.com!");//建立哈夫曼树 hl

  • 用R语言实现霍夫曼编码的示例代码

    可读性极低,而且其实也没必要用R语言写,图个乐罢了 p=c(0.4,0.2,0.2,0.1,0.1)###输入形如c(0.4,0.2,0.2,0.1,0.1)的概率向量,即每个待编码消息的发生概率 p1=p###将概率向量另存,最后计算编码效率要用 mazijuzhen=matrix(,nrow=length(p),ncol=length(p)-1)###码字矩阵:第i行对应向量p的第i个分量所对应的那个待编码消息的编码后的码字 group=matrix(c(1:length(p),rep(NA

  • 利用Python和C语言分别实现哈夫曼编码

    目录 1.C语言实现 1.1代码说明 1.2运行结果 2.Python实现 2.1代码说明 2.2运行结果 1.C语言实现 1.1代码说明 a  创建双向链表: 在创建哈夫曼树的过程中,需要不断对结点进行更改和删除,所以选用双向链表的结构更容易 '''C #include <stdlib.h> #include <stdio.h> #include <windows.h> //哈夫曼树结构体,数据域存储字符及其权重 typedef struct node { char

  • C语言实现BMP图像处理(哈夫曼编码)

    哈夫曼(Huffman)编码是一种常用的压缩编码方法,是 Huffman 于 1952 年为压缩文本文件建立的.它的基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同.这些代码都是二进制码,且码的长度是可变的. 下面给出具体的 Huffman 编码算法: (1) 首先统计出每个符号出现的频率,上例 S0 到 S7 的出现频率分别为 4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14. (2) 从左到右把上述频率按从小到大的

  • C语言实现哈夫曼树

    本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下 //哈夫曼树C语言实现 #include <stdio.h> #include <stdlib.h> typedef struct HuffmanNode { char letter;//存储的字符,叶节点为字母,非叶节点为# struct HuffmanNode *parent;//父亲结点 int code;//如果为父亲结点的左孩子,则为0,右孩子为1 }HuffmanNode; typedef st

  • C语言实现哈夫曼树的方法

    本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下 准备工作: 1.定义一个结构体,表示一个节点.其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标 2.定义一个整形数组,用于存放各个节点的权值 3.定义一个整形数组,用于存放哈夫曼编码,当然也可以定义一个整形数组来存放哈夫曼编码 构建哈夫曼树: 1.给这个哈夫曼树创建一个结构体数组,其中分配的空间是2 * n - 1,因为我们都知道哈夫曼树的性质有一个是:给定n个叶子节点,那么由这n个叶子

  • 基于C语言利用哈夫曼树实现文件压缩的问题

    一.哈夫曼树 具有n个权值的n个叶子结点,构造出一个二叉树,使得该树的带权路径长度(WPL)最小,则称此二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree). 注意:哈夫曼树是带权路径长度最短的树,且权值越大的叶子结点离根结点越近. 二.哈夫曼编码         哈夫曼编码是一种编码方式,又称"霍夫曼编码",其是可变字长的编码(VCL)的一种,是由霍夫曼于1952年提出的一种编码方式,有时被称为最佳编码,一般称为Huffman编码. 那么我们为什么要使用哈夫曼编码进行压缩?

  • JS实现的哈夫曼编码示例【原始版与修改版】

    本文实例讲述了JS实现的哈夫曼编码.分享给大家供大家参考,具体如下: 原始版 function cal(str) { if (typeof str !== 'string' || str.length < 1) { return; } var map = {}; var i = 0; while(str[i]) { map[str[i]] ? map[str[i]]++ : (map[str[i]] = 1); i++; } return map; } function sort(map) {

随机推荐