鱼C论坛

 找回密码
 立即注册
查看: 2903|回复: 3

[分享] Huffman编码

[复制链接]
发表于 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

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

  7. #define OK 0
  8. #define ERROR -1
  9. #define TRUE 1
  10. #define FALSE 0

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

  31. typedef struct _queueNode
  32. {
  33.     ElementType data;  //具有树节点的元素
  34.     struct _queueNode *next;
  35. }queueNode;   //队列节点的具体内容

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

  59. Status queueInit(linkQueue *Q);   //初始化队列
  60. Status enQueue(linkQueue *Q, ElementType *X);  //入队
  61. huffmanNode* deQueue(linkQueue *Q);  //出队
  62. Status isEmpty(linkQueue *Q);  //判断队列是否为空
  63. Status queueShow( linkQueue *Q );   //遍历队列
  64. void queueDestroy(linkQueue *Q);  //销毁队列
  65. Status orderEnQueue(linkQueue *Q, ElementType *X);   //由小到大排序入队

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

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

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

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

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

  23.     for(j = 0; j < 256; j++)           //对出现的字符分配内存
  24.     {
  25.         if(probability[j] != 0)
  26.         {
  27.             tmp = (huffmanNode *)malloc(sizeof(huffmanNode));
  28.             if(NULL == tmp)
  29.             return ERROR;

  30.             tmp->symbol = (char)j;     //将字符j放到tmp->symbol
  31.             tmp->weight = probability[j];  //权重为probability[j]
  32.             tmp->left = NULL;
  33.             tmp->right = NULL;

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

  35.             free(tmp);   //释放内存
  36.             tmp = NULL;
  37.         }
  38.     }

  39.     free(probability);   //释放内存
  40.     probability = NULL;

  41.     return OK;
  42. }

  43. /*
  44. *=============================================================================
  45. *创建huffman树
  46. *=============================================================================
  47. */
  48. huffmanNode* createHuffmanTree(linkQueue *Q)
  49. {
  50.     huffmanNode *left, *right, *current;
  51.     huffmanNode *huffmantree;

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

  56.         current = (huffmanNode *)malloc(sizeof(huffmanNode));
  57.         if(NULL == current)
  58.             exit(-1);

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

  63.         orderEnQueue(Q, current);

  64.         free(current);
  65.         current = NULL;
  66.     }

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

  68.     return huffmantree;
  69. }

  70. /*
  71. *=============================================================================
  72. *huffman编码
  73. *=============================================================================
  74. */
  75. Status huffmanCode(huffmanNode *root, char *stringToCode, char *inputString)
  76. {
  77.     FILE *fp1, *fp2;
  78.     int i = 0, j;   //专用循环变量
  79.     huffmanNode *current = NULL;
  80.     linkQueue Q;
  81.     storeCode *array;   //用于存放huffman树编码的

  82.     fp1 = fopen("huffmanCode1.txt","w");
  83.     if(NULL == fp1)
  84.     perror("huffmanCode1.txt");
  85.     fp2 = fopen("huffmanCode2.txt","w");
  86.     if(NULL == fp2)
  87.     perror("huffmanCode2.txt");

  88.     array = (storeCode *)malloc(sizeof(storeCode)*256);    //分配内存
  89.     if(NULL == array)
  90.     return ERROR;

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

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

  93.     while(isEmpty(&Q))    //判断队列是否为空
  94.     {
  95.         current = deQueue(&Q);

  96.         if(current->left == NULL && current->right == NULL)   //如果树的左子树和右子树都为空,就说明到了树的叶子了
  97.         {
  98.             fprintf(fp1, "符号:%c,权重:%d,编码:%s\n", current->symbol,current->weight, current->code);
  99.             array[i].symbol = current->symbol;  //将输出的字符放到数组里面
  100.             array[i].weight = current->weight;  //将输出的权重放到数组里面
  101.             array[i].code = current->code;      //将输出的编码放到数组里面,后面要用的
  102.             i++;
  103.         }
  104.         if(current->left != NULL)
  105.         {
  106.             strcpy(current->left->code, current->code);   //把父节点的编码复制到子节点,这样才可以把父节点的编码继承下去
  107.             strcat(current->left->code, "0");   //因为节点在左边,所以把'0'放到节点上

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

  114.             enQueue(&Q, current->right);
  115.         }
  116.     }

  117.     for(i = 0, j = 0; ; i++)
  118.     {
  119.         if(array[i].symbol == inputString[j])
  120.         {
  121.             strcat(stringToCode, array[i].code);   //将编好的码用strcat连接起来
  122.             if(strlen(stringToCode) >= MAXSIZE)     //防止stringToCode不够大
  123.             {
  124.                 stringToCode = realloc(stringToCode, (MAXSIZE + EXTENDSIZE)*sizeof(char));
  125.                 if(NULL == stringToCode)
  126.                 return  ERROR;
  127.             }

  128.             i = -1;   //-1是因为for那里会i++,变成0
  129.             j++;
  130.             if(inputString[j] == '\0')  //到了输入字符串的尾就要结束了,不然进行下去就会有乱码的
  131.             {
  132.                 break;
  133.             }
  134.         }
  135.     }
  136.     free(array);
  137.     array = NULL;

  138.     for(i = 0; stringToCode[i] != '\0'; i++)   //输出huffman编码
  139.     {
  140.         fprintf(fp2, "%c", stringToCode[i]);
  141.     }
  142.     puts("");

  143.     fclose(fp1);
  144.     fclose(fp2);

  145.     return OK;
  146. }

  147. /*
  148. *=============================================================================
  149. *huffman解码
  150. *原理:当遇到0时向左走,遇到1时向右走,直到遇到叶子节点就读出相应的符号
  151. *=============================================================================
  152. */
  153. Status huffmandeCode(huffmanNode *T, char *stringToDecode)
  154. {
  155.     FILE *fp;
  156.     int i;   //循环变量
  157.     huffmanNode *tmp;  //临时变量

  158.     tmp = T;
  159.     fp = fopen("huffmandeCode.txt","w");
  160.     if(NULL == fp)
  161.     perror("huffmandeCode.txt");

  162.     for(i = 0; stringToDecode[i] != '\0'; i++)
  163.     {
  164.         if(stringToDecode[i] == '0')  //向左走
  165.         {
  166.             tmp = tmp->left;
  167.         }
  168.         if(stringToDecode[i] == '1')  //向右走
  169.         {
  170.             tmp = tmp->right;
  171.         }
  172.         if(NULL == tmp->left && NULL == tmp->right)  //到了叶子节点,输出相应的字符
  173.         {
  174.             fprintf(fp, "%c", tmp->symbol);
  175.             tmp = T;
  176.         }
  177.         if(stringToDecode[i] != '0' || stringToDecode[i] != '1')  //防止编码错误
  178.         {
  179.             continue;
  180.         }
  181.     }
  182.     if(NULL == tmp->left && NULL == tmp->right)   //到了叶子节点并且输出完字符后就要回到树根再继续
  183.     {
  184.         fprintf(fp, "%c", tmp->symbol);
  185.         tmp = T;
  186.     }

  187.     return OK;
  188. }

  189. /*
  190. *=============================================================================
  191. *递归遍历huffman树(test用的)
  192. *=============================================================================
  193. */
  194. Status huffmanShow(huffmanNode *T)
  195. {
  196.     if(T != NULL)
  197.     {
  198.         huffmanShow(T->left);   //遍历左子树
  199.         printf("%c\t", T->symbol);  //打印权重
  200.         huffmanShow(T->right);  //遍历右子树
  201.     }

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

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

  15.     Q->rear = Q->front;
  16.     Q->rear->next = NULL;
  17.     Q->queueSize = 0;

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

  28.     tmp = (queueNode *)malloc(sizeof(queueNode));
  29.     if(NULL == tmp)
  30.     return ERROR;

  31.     tmp->data = *X;
  32.     tmp->next = NULL;
  33.     Q->rear->next = tmp;
  34.     Q->rear = tmp;
  35.     Q->queueSize++;

  36.     return OK;
  37. }
  38. /*
  39. *============================================================================
  40. *出队列
  41. *============================================================================
  42. */
  43. huffmanNode* deQueue(linkQueue *Q)
  44. {
  45.     queueNode *tmp;
  46.     huffmanNode *val;

  47.     if(Q->front == Q->rear)
  48.     {
  49.         printf("队列为空,出队失败\n");
  50.         exit(-1);
  51.     }

  52.     val = (huffmanNode *)malloc(sizeof(huffmanNode));
  53.     if(NULL == val)
  54.         exit(-1);

  55.     tmp = Q->front->next;
  56.     *val = tmp->data;
  57.     Q->front->next = tmp->next;
  58.     if(Q->rear == tmp)   //如果只有一个元素
  59.         Q->rear = Q->front;   //重置尾指针
  60.     Q->queueSize--;
  61.     free(tmp);
  62.     tmp = NULL;

  63.     return val;
  64. }

  65. /*
  66. *============================================================================
  67. *判断队列是否为空
  68. *============================================================================
  69. */
  70. Status isEmpty(linkQueue *Q)
  71. {
  72.     if(Q->front == Q->rear)
  73.     return FALSE;
  74.     else
  75.     return TRUE;
  76. }

  77. /*
  78. *============================================================================
  79. *遍历队列
  80. *============================================================================
  81. */
  82. Status queueShow( linkQueue *Q )
  83. {
  84.     queueNode *p;

  85.         if( Q->front == Q->rear )
  86.                 return ERROR;

  87.         p = Q->front->next;
  88.         while( p != NULL)
  89.         {
  90.                 printf("%c", p->data.symbol );
  91.                 p = p->next ;
  92.         }
  93.         puts("");

  94.         return OK;
  95. }

  96. /*
  97. *============================================================================
  98. *销毁队列
  99. *============================================================================
  100. */
  101. void queueDestroy(linkQueue *Q)
  102. {
  103.     queueNode *tmp;

  104.     tmp = Q->front->next;
  105.     Q->front->next = NULL;
  106.     while(tmp != NULL)
  107.     {
  108.         Q->rear = tmp->next;
  109.         free(tmp);
  110.         tmp = NULL;
  111.         tmp = Q->rear;
  112.     }
  113.     Q->queueSize = 0;
  114. }
  115. /*
  116. *============================================================================
  117. *由小到大排序的入队列(画图出来很好理解的)
  118. *============================================================================
  119. */
  120. Status orderEnQueue(linkQueue *Q, ElementType *X)
  121. {
  122.     queueNode *tmp;
  123.     queueNode *iterator;

  124.     tmp = (queueNode *)malloc(sizeof(queueNode));  //分配内存
  125.     if(NULL == tmp)
  126.     return ERROR;

  127.     tmp->data = *X;
  128.     if(NULL == Q->front->next || 0 == Q->queueSize)   //第一个元素入队列,直接插入就可以了
  129.     {
  130.         tmp->next = NULL;
  131.         Q->rear->next = tmp;
  132.         Q->rear = tmp;
  133.         Q->queueSize++;
  134.     }
  135.     else
  136.     {
  137.         if(tmp->data.weight <= Q->front->next->data.weight)   //已经有了第一个元素的情况,在头节点front和front后一个
  138.         {                                                     ////元素直接插入tmp
  139.             tmp->next = Q->front->next;     //这两句千万记得
  140.             Q->front->next = tmp;           //不要搞反了,会死循环的!!!!!!!!!!
  141.             Q->queueSize++;
  142.         }
  143.         else
  144.         {
  145.             iterator = Q->front->next;
  146.             while(iterator->next != NULL)
  147.             {
  148.                 if(tmp->data.weight <= iterator->next->data.weight)  //比较中间的元素的权重大小
  149.                 {
  150.                     tmp->next = iterator->next;
  151.                     iterator->next = tmp;
  152.                     Q->queueSize++;

  153.                     return OK;
  154.                 }
  155.                 iterator = iterator->next;
  156.             }
  157.             if(NULL == iterator->next)  //在队尾直接插入
  158.             {
  159.                 iterator->next = tmp;
  160.                 tmp->next = NULL;
  161.                 Q->rear = tmp;
  162.                 Q->queueSize++;
  163.             }
  164.         }
  165.     }

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

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

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

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

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

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

  37.    // printf("huffman编码为\n");
  38.     huffmanCode(huffmantree, stringToCode, string);     //huffman编码
  39.    // printf("huffman解码为\n");
  40.     huffmandeCode(huffmantree, stringToCode);    //huffman解码
  41. /*============释放内存================*/
  42.     free(huffmantree);
  43.     huffmantree = NULL;
  44.     free(stringToCode);
  45.     stringToCode = NULL;

  46.     fclose(fp);

  47.     return 0;
  48. }
复制代码


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2013-8-5 12:41:41 | 显示全部楼层
沙发自己的!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2016-12-2 20:56:31 | 显示全部楼层
。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-10-30 20:36:38 | 显示全部楼层

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

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

GMT+8, 2024-3-29 02:29

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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