开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 嵌入式/单片机编程 > DSP编程 > 查看源码
huffman.c
资源名称：msp430.rar　[点击查看]
上传用户：xs588588
上传日期：2021-03-30
资源大小：242k
文件大小：3k
源码类别：

DSP编程

开发平台：

C/C++

huffman.c：源码内容
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. #define TRUE 1
  5. #define FALSE 0
  7. // 编码的最大位数
  8. #define MAXBITS 50
  9. // 最大的字符数
  10. #define MAXSYMBS MAXBITS
  11. // 树中的最大节点
  12. #define MAXNODES 2 * MAXSYMBS-1
  14. struct CodeType {
  15. int nBits[MAXBITS];
  16. int nStartPos;
  17. };
  19. struct NodeType {
  20. int nFrequency;
  21. int nParent;
  22. int iSLeft;
  23. };
  25. // 队列的插入删除处理
  26. void QueueInsert(int nWhich);
  27. int QueueDelete(void);
  29. // 定义全局变量
  30. struct NodeType node[MAXNODES];
  31. // 队列最初位空
  32. int rootnodes = -1;
  34. void main(void)
  35. {
  36. struct CodeType cd, code[MAXSYMBS];
  37. int i;
  38. int nSymbolsNum;
  39. int nBitCount;
  40. int nNextNode;
  41. int nLeftNode, nRightNode;
  42. int root;
  43. int thisnode;
  44. char symbol, alphabet[MAXSYMBS];
  46. // 清空字符数组
  47. for(i = 0; i < MAXSYMBS; i++)
  48. {
  49. alphabet[i] = ' ';
  50. }
  52. /*// 有多少个字符
  53. printf("Please input char's countn");
  54. scanf("%d", &nSymbolsNum);
  56. printf("Please input char and frequenciesn");
  57. // 得到数据和每个字符的频率
  58. for(i = 0; i < nSymbolsNum; i++)
  59. {
  60. scanf("%s%d", &symbol, &node[i].nFrequency);
  61. QueueInsert(i);
  62. alphabet[i] = symbol;
  63. }*/
  65. //构造信源数据
  66. nSymbolsNum = 3;
  67. alphabet[0] = 'a';
  68. node[0].nFrequency = 8;
  69. QueueInsert(0);
  70. alphabet[1] = 'b';
  71. node[1].nFrequency = 2;
  72. QueueInsert(1);
  73. alphabet[2] = 'c';
  74. node[2].nFrequency = 5;
  75. QueueInsert(2);
  77. // 形成Huffman树
  78. for(nNextNode =  nSymbolsNum;
  79. nNextNode < 2 * nSymbolsNum - 1;
  80. nNextNode ++)
  81. {
  82. nLeftNode = QueueDelete();
  83. nRightNode = QueueDelete();
  85. // 形成新的树，作为子节点
  86. node[nLeftNode].nParent = nNextNode;
  87. node[nRightNode].nParent = nNextNode;
  88. node[nLeftNode].iSLeft = TRUE;
  89. node[nRightNode].iSLeft = FALSE;
  91. // 父节点的频率是两个子节点频率之和
  92. node[nNextNode].nFrequency = 
  93. node[nLeftNode].nFrequency + node[nRightNode].nFrequency;
  95. //插入节点
  96. QueueInsert( nNextNode);
  97. }
  99.     // 根节点
  100. root = QueueDelete();
  101. // 根据树进行编码
  102. for(i = 0; i < nSymbolsNum; i++)
  103. {
  104. // 搜索的初始点
  105. cd.nStartPos = MAXBITS;
  107. // 对树进行遍历，对内容进行编码
  108. thisnode = i;
  109. while(thisnode != root)
  110. {
  111. --cd.nStartPos;
  112. cd.nBits[cd.nStartPos] = node[thisnode].iSLeft ? 0 : 1;
  113. thisnode = node[thisnode].nParent;
  114. }
  116. // 内容拷贝
  117. for(nBitCount = cd.nStartPos; nBitCount < MAXBITS; nBitCount++)
  118. {
  119. code[i].nBits[nBitCount] = cd.nBits[nBitCount];
  120. }
  121. code[i].nStartPos = cd.nStartPos;
  122. }
  124. for(i = 0; i < nSymbolsNum; i++)
  125. {
  126. printf("n%c %d ", alphabet[i], node[i].nFrequency);
  127. for(nBitCount = code[i].nStartPos; nBitCount < MAXBITS; nBitCount++)
  128. {
  129. printf("%d", code[i].nBits[nBitCount]);
  130. }
  131. printf("n");
  132. }
  133. }
  134. // 将节点插入到队列里
  135. void QueueInsert(int nWhich)
  136. {
  137. int thisnode, previous;
  138. // 队列是否为空
  139. if(rootnodes == -1)
  140. {
  141. // 空队列
  142. node[nWhich].nParent = -1;
  143. rootnodes = nWhich;
  144. }
  145. else
  146. {
  147. thisnode = rootnodes; 
  148. previous = -1;
  149. //搜索大的节点
  150. while((thisnode != -1) && 
  151. (node[thisnode].nFrequency < node[nWhich].nFrequency))
  152. {
  153. previous = thisnode;
  154. thisnode = node[thisnode].nParent;
  155.   }
  157. // 连接到第一个大的节点
  158. node[nWhich].nParent = thisnode;
  159. if(previous != -1)
  160. {
  161. // 拷贝
  162. node[previous].nParent = nWhich;
  163. }
  164. else
  165. {
  166. // 插入到开始位置
  167. rootnodes = nWhich;
  168. }
  169. }
  170. }
  172. //从优先队列里去掉第一个结点
  173. int QueueDelete(void)
  174. {
  175. int thisnode = rootnodes;
  176. rootnodes = node[thisnode].nParent;
  177. return thisnode;
  178. }