设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 萌新训练营 › 萌新交流区 › Huffman编码
返回列表 发新帖
查看: 3879|回复: 3

[作品展示] Huffman编码

[复制链接]
eeeeelin
发表于 2013-8-5 12:34:48 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
本帖最后由 eeeeelin 于 2013-8-9 20:40 编辑

仿照小甲鱼的数据结构与算法课程，自己写了一个Huffman编码！不过就是有个BUG，就是当输入的字符串太长的时候，程序就会崩毁的，如果有解决办法，请留言告诉我哈，谢谢了！！！！

Huffman

Huffman
  1. #pragma once
  2. #ifndef HUFFMAN_H
  3. #define HUFFMAN_H

  5. #define UINT unsigned int
  6. #define MAXSIZE  100
  7. #define EXTENDSIZE 4

  9. #define OK 0
  10. #define ERROR -1
  11. #define TRUE 1
  12. #define FALSE 0

  14. typedef int Status;
  15. /*
  16. *=============================================================================
  17. *huffman树节点
  18. *=============================================================================
  19. */
  20. typedef struct _huffmanNode
  21. {
  22.     UINT weight;   //权重
  23.     char symbol;        //符号
  24.     char code[8];   //编码
  25.     struct _huffmanNode *left;  //左子树
  26.     struct _huffmanNode *right; //右子树
  27. }huffmanNode;   //树节点的具体内容
  28. /*
  29. *=============================================================================
  30. *链队列，用于存放huffman树节点
  31. *=============================================================================
  32. */
  33. typedef huffmanNode ElementType;

  35. typedef struct _queueNode
  36. {
  37.     ElementType data;  //具有树节点的元素
  38.     struct _queueNode *next;
  39. }queueNode;   //队列节点的具体内容

  41. typedef struct
  42. {
  43.     queueNode *front;   //队头
  44.     queueNode *rear;    //队尾
  45.     int queueSize;      //当前队列的大小
  46. }linkQueue;  //链队列
  47. /*
  48. *============================================================================
  49. *这个节点用于存放huffman树编码
  50. *============================================================================
  51. */
  52. typedef struct
  53. {
  54.     char symbol;   //存放符号
  55.     UINT weight;   //权重
  56.     char *code;    //编码
  57. }storeCode;
  58. /*===========================================================================*/
  59. Status selectWeight(linkQueue *Q, char *inputString);//对权重进行统计，就是对输入的字符出现次数统计,将节点按权值从小到大放入队列
  60. huffmanNode* createHuffmanTree(linkQueue *Q);   //创建haffman树
  61. Status huffmanCode(huffmanNode *root, char *stringToCode, char *inputString);  //huffman编码
  62. Status huffmandeCode(huffmanNode *T, char *stringToDecode);    //huffman解码
  63. Status huffmanShow(huffmanNode *T);  //递归遍历huffman树

  65. Status queueInit(linkQueue *Q);   //初始化队列
  66. Status enQueue(linkQueue *Q, ElementType *X);  //入队
  67. huffmanNode* deQueue(linkQueue *Q);  //出队
  68. Status isEmpty(linkQueue *Q);  //判断队列是否为空
  69. Status queueShow( linkQueue *Q );   //遍历队列
  70. void queueDestroy(linkQueue *Q);  //销毁队列
  71. Status orderEnQueue(linkQueue *Q, ElementType *X);   //由小到大排序入队

  73. #endif
复制代码
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "huffman.h"

  6. /*
  7. *=============================================================================
  8. *对权重进行统计，就是对输入的字符出现次数统计,将节点按权值从小到大放入队列
  9. *=============================================================================
  10. */
  11. Status selectWeight(linkQueue *Q, char *inputString)
  12. {
  13.     int *probability;    //用来统计字符串出现的次数
  14.     int i, j;  //循环变量
  15.     huffmanNode *tmp;  //具有树结构的临时变量

  17.     probability = (int *)malloc(sizeof(int)*256 );   //分配内存
  18.     if(NULL == probability)
  19.         return ERROR;

  21.     memset(probability, 0, sizeof(int)*256);   //将problilty的元素重置为0

  23.     for(i = 0; inputString[i] != '\0'; i++)   //统计输入字符串的字符出现的次数
  24.     {  //比如说:I在字符串中出现了，那么probability[I]++,就在相应的ACSII上I的位置+1
  25.         probability[(unsigned char)inputString[i]]++;
  26.     }

  28.     for(j = 0; j < 256; j++)           //对出现的字符分配内存
  29.     {
  30.         if(probability[j] != 0)
  31.         {
  32.             tmp = (huffmanNode *)malloc(sizeof(huffmanNode));
  33.             if(NULL == tmp)
  34.             return ERROR;

  36.             tmp->symbol = (char)j;     //将字符j放到tmp->symbol
  37.             tmp->weight = probability[j];  //权重为probability[j]
  38.             tmp->left = NULL;
  39.             tmp->right = NULL;

  41.             orderEnQueue(Q, tmp);  //入队

  43.             free(tmp);   //释放内存
  44.             tmp = NULL;
  45.         }
  46.     }

  48.     free(probability);   //释放内存
  49.     probability = NULL;

  51.     return OK;
  52. }

  54. /*
  55. *=============================================================================
  56. *创建huffman树
  57. *=============================================================================
  58. */
  59. huffmanNode* createHuffmanTree(linkQueue *Q)
  60. {
  61.     huffmanNode *left, *right, *current;
  62.     huffmanNode *huffmantree;

  64.     while(Q->queueSize != 1)   //不等于1是因为在队列要存放一个树根，到时候函数返回
  65.     {
  66.         left = deQueue(Q);
  67.         right = deQueue(Q);

  69.         current = (huffmanNode *)malloc(sizeof(huffmanNode));
  70.         if(NULL == current)
  71.             exit(-1);

  73.         current->weight = left->weight + right->weight;  //新节点的权重等于左右子树权重相加
  74.         current->left = left;
  75.         current->right = right;
  76.         strcpy(current->code, "");    //warning:用strcpy对数组进行初始化,输出的编码记得先初始化，不然后面的编码就会有乱码

  78.         orderEnQueue(Q, current);

  80.         free(current);
  81.         current = NULL;
  82.     }

  84.     huffmantree = deQueue(Q);  //这时候队列就只有一个节点了，返回给huffman树

  86.     return huffmantree;
  87. }

  89. /*
  90. *=============================================================================
  91. *huffman编码
  92. *=============================================================================
  93. */
  94. Status huffmanCode(huffmanNode *root, char *stringToCode, char *inputString)
  95. {
  96.     FILE *fp1, *fp2;
  97.     int i = 0, j;   //专用循环变量
  98.     huffmanNode *current = NULL;
  99.     linkQueue Q;
  100.     storeCode *array;   //用于存放huffman树编码的

  102.     fp1 = fopen("huffmanCode1.txt","w");
  103.     if(NULL == fp1)
  104.     perror("huffmanCode1.txt");
  105.     fp2 = fopen("huffmanCode2.txt","w");
  106.     if(NULL == fp2)
  107.     perror("huffmanCode2.txt");

  109.     array = (storeCode *)malloc(sizeof(storeCode)*256);    //分配内存
  110.     if(NULL == array)
  111.     return ERROR;

  113.     queueInit(&Q);  //初始化huffman树队列

  115.     enQueue(&Q, root);   //把树根入队

  117.     while(isEmpty(&Q))    //判断队列是否为空
  118.     {
  119.         current = deQueue(&Q);

  121.         if(current->left == NULL && current->right == NULL)   //如果树的左子树和右子树都为空，就说明到了树的叶子了
  122.         {
  123.             fprintf(fp1, "符号:%c,权重:%d,编码:%s\n", current->symbol,current->weight, current->code);
  124.             array[i].symbol = current->symbol;  //将输出的字符放到数组里面
  125.             array[i].weight = current->weight;  //将输出的权重放到数组里面
  126.             array[i].code = current->code;      //将输出的编码放到数组里面,后面要用的
  127.             i++;
  128.         }
  129.         if(current->left != NULL)
  130.         {
  131.             strcpy(current->left->code, current->code);   //把父节点的编码复制到子节点，这样才可以把父节点的编码继承下去
  132.             strcat(current->left->code, "0");   //因为节点在左边，所以把'0'放到节点上

  134.             enQueue(&Q, current->left);
  135.         }
  136.         if(current->right != NULL)
  137.         {
  138.             strcpy(current->right->code, current->code);  //把父节点的编码复制到子节点，这样才可以把父节点的编码继承下去
  139.             strcat(current->right->code, "1");   //因为节点在右边，所以把'1'放到节点上

  141.             enQueue(&Q, current->right);
  142.         }
  143.     }

  145.     for(i = 0, j = 0; ; i++)
  146.     {
  147.         if(array[i].symbol == inputString[j])
  148.         {
  149.             strcat(stringToCode, array[i].code);   //将编好的码用strcat连接起来
  150.             if(strlen(stringToCode) >= MAXSIZE)     //防止stringToCode不够大
  151.             {
  152.                 stringToCode = realloc(stringToCode, (MAXSIZE + EXTENDSIZE)*sizeof(char));
  153.                 if(NULL == stringToCode)
  154.                 return  ERROR;
  155.             }

  157.             i = -1;   //-1是因为for那里会i++,变成0
  158.             j++;
  159.             if(inputString[j] == '\0')  //到了输入字符串的尾就要结束了,不然进行下去就会有乱码的
  160.             {
  161.                 break;
  162.             }
  163.         }
  164.     }
  165.     free(array);
  166.     array = NULL;

  168.     for(i = 0; stringToCode[i] != '\0'; i++)   //输出huffman编码
  169.     {
  170.         fprintf(fp2, "%c", stringToCode[i]);
  171.     }
  172.     puts("");

  174.     fclose(fp1);
  175.     fclose(fp2);

  177.     return OK;
  178. }

  180. /*
  181. *=============================================================================
  182. *huffman解码
  183. *原理：当遇到0时向左走，遇到1时向右走，直到遇到叶子节点就读出相应的符号
  184. *=============================================================================
  185. */
  186. Status huffmandeCode(huffmanNode *T, char *stringToDecode)
  187. {
  188.     FILE *fp;
  189.     int i;   //循环变量
  190.     huffmanNode *tmp;  //临时变量

  192.     tmp = T;
  193.     fp = fopen("huffmandeCode.txt","w");
  194.     if(NULL == fp)
  195.     perror("huffmandeCode.txt");

  197.     for(i = 0; stringToDecode[i] != '\0'; i++)
  198.     {
  199.         if(stringToDecode[i] == '0')  //向左走
  200.         {
  201.             tmp = tmp->left;
  202.         }
  203.         if(stringToDecode[i] == '1')  //向右走
  204.         {
  205.             tmp = tmp->right;
  206.         }
  207.         if(NULL == tmp->left && NULL == tmp->right)  //到了叶子节点，输出相应的字符
  208.         {
  209.             fprintf(fp, "%c", tmp->symbol);
  210.             tmp = T;
  211.         }
  212.         if(stringToDecode[i] != '0' || stringToDecode[i] != '1')  //防止编码错误
  213.         {
  214.             continue;
  215.         }
  216.     }
  217.     if(NULL == tmp->left && NULL == tmp->right)   //到了叶子节点并且输出完字符后就要回到树根再继续
  218.     {
  219.         fprintf(fp, "%c", tmp->symbol);
  220.         tmp = T;
  221.     }

  223.     return OK;
  224. }

  226. /*
  227. *=============================================================================
  228. *递归遍历huffman树(test用的)
  229. *=============================================================================
  230. */
  231. Status huffmanShow(huffmanNode *T)
  232. {
  233.     if(T != NULL)
  234.     {
  235.         huffmanShow(T->left);   //遍历左子树
  236.         printf("%c\t", T->symbol);  //打印权重
  237.         huffmanShow(T->right);  //遍历右子树
  238.     }

  240.     return OK;
  241. }
复制代码
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "huffman.h"

  6. /*
  7. *============================================================================
  8. *初始化huffman树队列
  9. *============================================================================
  10. */
  11. Status queueInit(linkQueue *Q)
  12. {
  13.     Q->front = (queueNode *)malloc(sizeof(queueNode));
  14.     if(NULL == Q->front)
  15.     return ERROR;

  17.     Q->rear = Q->front;
  18.     Q->rear->next = NULL;
  19.     Q->queueSize = 0;

  21.     return OK;
  22. }
  23. /*
  24. *============================================================================
  25. *入队列
  26. *============================================================================
  27. */
  28. Status enQueue(linkQueue *Q, ElementType *X)
  29. {
  30.     queueNode *tmp;

  32.     tmp = (queueNode *)malloc(sizeof(queueNode));
  33.     if(NULL == tmp)
  34.     return ERROR;

  36.     tmp->data = *X;
  37.     tmp->next = NULL;
  38.     Q->rear->next = tmp;
  39.     Q->rear = tmp;
  40.     Q->queueSize++;

  42.     return OK;
  43. }
  44. /*
  45. *============================================================================
  46. *出队列
  47. *============================================================================
  48. */
  49. huffmanNode* deQueue(linkQueue *Q)
  50. {
  51.     queueNode *tmp;
  52.     huffmanNode *val;

  54.     if(Q->front == Q->rear)
  55.     {
  56.         printf("队列为空，出队失败\n");
  57.         exit(-1);
  58.     }

  60.     val = (huffmanNode *)malloc(sizeof(huffmanNode));
  61.     if(NULL == val)
  62.         exit(-1);

  64.     tmp = Q->front->next;
  65.     *val = tmp->data;
  66.     Q->front->next = tmp->next;
  67.     if(Q->rear == tmp)   //如果只有一个元素
  68.         Q->rear = Q->front;   //重置尾指针
  69.     Q->queueSize--;
  70.     free(tmp);
  71.     tmp = NULL;

  73.     return val;
  74. }

  76. /*
  77. *============================================================================
  78. *判断队列是否为空
  79. *============================================================================
  80. */
  81. Status isEmpty(linkQueue *Q)
  82. {
  83.     if(Q->front == Q->rear)
  84.     return FALSE;
  85.     else
  86.     return TRUE;
  87. }

  89. /*
  90. *============================================================================
  91. *遍历队列
  92. *============================================================================
  93. */
  94. Status queueShow( linkQueue *Q )
  95. {
  96.     queueNode *p;

  98.         if( Q->front == Q->rear )
  99.                 return ERROR;

  101.         p = Q->front->next;
  102.         while( p != NULL)
  103.         {
  104.                 printf("%c", p->data.symbol );
  105.                 p = p->next ;
  106.         }
  107.         puts("");

  109.         return OK;
  110. }

  112. /*
  113. *============================================================================
  114. *销毁队列
  115. *============================================================================
  116. */
  117. void queueDestroy(linkQueue *Q)
  118. {
  119.     queueNode *tmp;

  121.     tmp = Q->front->next;
  122.     Q->front->next = NULL;
  123.     while(tmp != NULL)
  124.     {
  125.         Q->rear = tmp->next;
  126.         free(tmp);
  127.         tmp = NULL;
  128.         tmp = Q->rear;
  129.     }
  130.     Q->queueSize = 0;
  131. }
  132. /*
  133. *============================================================================
  134. *由小到大排序的入队列(画图出来很好理解的)
  135. *============================================================================
  136. */
  137. Status orderEnQueue(linkQueue *Q, ElementType *X)
  138. {
  139.     queueNode *tmp;
  140.     queueNode *iterator;

  142.     tmp = (queueNode *)malloc(sizeof(queueNode));  //分配内存
  143.     if(NULL == tmp)
  144.     return ERROR;

  146.     tmp->data = *X;
  147.     if(NULL == Q->front->next || 0 == Q->queueSize)   //第一个元素入队列，直接插入就可以了
  148.     {
  149.         tmp->next = NULL;
  150.         Q->rear->next = tmp;
  151.         Q->rear = tmp;
  152.         Q->queueSize++;
  153.     }
  154.     else
  155.     {
  156.         if(tmp->data.weight <= Q->front->next->data.weight)   //已经有了第一个元素的情况,在头节点front和front后一个
  157.         {                                                     ////元素直接插入tmp
  158.             tmp->next = Q->front->next;     //这两句千万记得
  159.             Q->front->next = tmp;           //不要搞反了,会死循环的!!!!!!!!!!
  160.             Q->queueSize++;
  161.         }
  162.         else
  163.         {
  164.             iterator = Q->front->next;
  165.             while(iterator->next != NULL)
  166.             {
  167.                 if(tmp->data.weight <= iterator->next->data.weight)  //比较中间的元素的权重大小
  168.                 {
  169.                     tmp->next = iterator->next;
  170.                     iterator->next = tmp;
  171.                     Q->queueSize++;

  173.                     return OK;
  174.                 }
  175.                 iterator = iterator->next;
  176.             }
  177.             if(NULL == iterator->next)  //在队尾直接插入
  178.             {
  179.                 iterator->next = tmp;
  180.                 tmp->next = NULL;
  181.                 Q->rear = tmp;
  182.                 Q->queueSize++;
  183.             }
  184.         }
  185.     }

  187.     return OK;
  188. }
复制代码
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "huffman.h"

  6. int main(int argc, char *argv[])
  7. {
  8.     int fn = 0, fileSize = 0;   //文件指针的底层流式文件号，文件的大小
  9.     FILE *fp;    //定义一个文件指针
  10.     char string[4096];   //要编码的字符串
  11.     char *stringToCode = NULL;  //用来存放编码的
  12.     linkQueue Q;     //定义一个huffman树队列
  13.     huffmanNode *huffmantree = NULL;   //定义一个huffman树节点
  14. /*=========================文件操作==============================================*/
  15.     fp = fopen("huffman.txt","r");   //只读文件
  16.     if(NULL == fp)
  17.     perror("huffman.txt");
  18.     fn = fileno(fp);  //取得文件指针的底层流式文件号
  19.     fileSize = filelength(fn);   //取文件长度字节数
  20.     printf("文件的大小为%d\n", fileSize);
  21.     if(fileSize > 4096)
  22.     {
  23.         printf("请定义文件大小<=4096字节\n");
  24.         exit(-1);
  25.     }
  26.     fgets(string, fileSize+1, fp);   //将文本文件里的内容输出到数组string
  27. /*===============================================================================*/
  28.     huffmantree = (huffmanNode *)malloc(sizeof(huffmanNode));    //初始化
  29.     if(NULL == huffmantree)
  30.     exit(-1);

  32.     stringToCode = (char *)malloc(MAXSIZE*sizeof(char));  //分配内存大小
  33.     if(NULL == stringToCode)
  34.     exit(-1);
  35.     memset(stringToCode, 0, sizeof(char)*MAXSIZE);    //将字符数组置为空

  37.     queueInit(&Q);   //初始化huffman树队列

  39.     selectWeight(&Q, string);  //对权重进行统计，就是对输入的字符出现次数统计,将节点按权值从小到大放入队列

  41.     huffmantree = createHuffmanTree(&Q);  //创建huffman树

  43.    // printf("huffman编码为\n");
  44.     huffmanCode(huffmantree, stringToCode, string);     //huffman编码
  45.    // printf("huffman解码为\n");
  46.     huffmandeCode(huffmantree, stringToCode);    //huffman解码
  47. /*============释放内存================*/
  48.     free(huffmantree);
  49.     huffmantree = NULL;
  50.     free(stringToCode);
  51.     stringToCode = NULL;

  53.     fclose(fp);

  55.     return 0;
  56. }
复制代码


小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

eeeeelin
 楼主| 发表于 2013-8-5 12:41:41 | 显示全部楼层
沙发自己的！！
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

你咋这么牛逼呢
发表于 2016-12-2 20:56:31 | 显示全部楼层
。。。。
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

JCSY
发表于 2018-10-30 20:36:38 | 显示全部楼层
强
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-11-4 18:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表