自己写的Huffman树生成与Huffman编码实现 (实现了核心功能 ,打出了每个字符的huffman编码 其他的懒得实现了,有兴趣的朋友可以自己在我的基础增加功能 )
/* 原创文章 转载请附上原链接: https://www.cnblogs.com/jiujue/p/10325699.html */
### 硬核警告 递归 玩的可以在往下看 核心是递归实现 ¥_¥
上图:
上代码:(思路:通过递归将父亲的Huffman编码传给给孩子 孩子以此为基础进行在编码 )
1.头文件:(myHuffmanHead.h)
1 #pragma once 2 3 #pragma warning(disable :4996) 4 #include<stdio.h> 5 #include<stdlib.h> 6 #include<string.h> 7 8 /* 9 huffmanTree : 思路 10 注:每个关键字为一个节点 整个数据使用链表存储 11 节点内容 : 关键字 ,出现次数 ,编码 , 下一个节点。 12 13 将 关键字的出现频率作为权值来生成HuffmanTree 然后进行Huffman code 14 //1.获取关键字频率 15 1.1 获取输入 并 记录 关键字 出现次数 16 17 2.生成HuffmanTree 18 19 20 3.根据huffmanTree 进行HuffmanCode 并打印每个关键字的 Huffman编码 21 tips : 左 0 ; 右 1 22 */ 23 24 typedef struct nodehuffmantree { 25 26 char key; 27 int frequency; 28 29 char *code; 30 31 int isCoded; 32 33 struct nodehuffmantree * next; 34 struct nodehuffmantree *lchild, *rchild; 35 36 }nodeHuffmanTree_t; 37 38 int myStrCat(char *des, char *str); 39 40 int changeCode(char *strParent, char *strKid, char needAppend, char *tempspace); 41 42 int linkCode(nodeHuffmanTree_t *headLinkList, char *input); 43 44 int printLinkList(nodeHuffmanTree_t *head); 45 46 int makeBranch(nodeHuffmanTree_t **spaceSave, int spaceSize, int t1, int t2); 47 48 nodeHuffmanTree_t* isExitence(nodeHuffmanTree_t* head, char inputTemp); 49 50 int creatHuffmanTree(nodeHuffmanTree_t *headLinkList, nodeHuffmanTree_t **headhuffmanTree); 51 52 nodeHuffmanTree_t ** getSpaceSave(nodeHuffmanTree_t *headLinkList); 53 54 int huffmanCode(nodeHuffmanTree_t *headLinkList, nodeHuffmanTree_t *headhuffmanTree);
2主函数入口:(source_1.c)
1 #include"myHuffmanHead.h" 2 3 4 int main() 5 { 6 7 nodeHuffmanTree_t *head = NULL; 8 nodeHuffmanTree_t *headTree = NULL; 9 char *needcode; 10 printf("please input : "); 11 12 obtainIput(&head, &needcode); 13 14 creatHuffmanTree(head, &headTree); 15 16 huffmanCode(head, headTree); 17 18 printLinkList(head); 19 20 //linkCode(head, needcode); 21 22 system("pause"); 23 return 0; 24 }
10.获取输入:(obtainIput.c)
1 #include"myHuffmanHead.h" 2 3 4 int obtainIput(nodeHuffmanTree_t **head,char **input) 5 { 6 char tempInput; 7 nodeHuffmanTree_t **t1 = head; 8 nodeHuffmanTree_t *t2 = NULL; 9 10 tempInput = getc(stdin); 11 *input = tempInput; 12 while (tempInput !=' ') 13 { 14 if (!(t2= isExitence( (*head), tempInput))) 15 { 16 nodeHuffmanTree_t *nodeTempHuffman = (nodeHuffmanTree_t *)malloc(sizeof(nodeHuffmanTree_t)); 17 18 (*t1) = nodeTempHuffman; 19 20 nodeTempHuffman->key = tempInput; 21 nodeTempHuffman->frequency = 1; 22 nodeTempHuffman->next = NULL; 23 nodeTempHuffman->lchild = NULL; 24 nodeTempHuffman->rchild = NULL; 25 nodeTempHuffman->isCoded = 0; 26 t1 = &((*t1)->next); 27 tempInput = getc(stdin); 28 } 29 else 30 { 31 t2->frequency++ ; 32 tempInput = getc(stdin); 33 continue; 34 } 35 } 36 return 0; 37 }
3.创建一个Huffman树:(creatHuffmanTree.c)
1 #include"myHuffmanHead.h" 2 3 4 /* 5 1.1 先遍历 链表 计算有几个需要编码 6 1.2 创建一个空间 来存储 需要被编码的节点 并在每次编码后将编码后的过的删除 替换成 parent 7 */ 8 9 static nodeHuffmanTree_t **spaceSave = NULL; 10 11 12 nodeHuffmanTree_t ** getSpaceSave(nodeHuffmanTree_t *headLinkList) 13 { 14 nodeHuffmanTree_t *t1 = headLinkList; 15 16 int n = 0; 17 int i = 1; 18 19 while (t1 != NULL) 20 { 21 n++; 22 t1 = t1->next; 23 } 24 25 spaceSave = (nodeHuffmanTree_t*)malloc(sizeof(nodeHuffmanTree_t*)*n + 1); 26 27 t1 = headLinkList; 28 29 while (i < n + 1) 30 { 31 spaceSave[i] = t1; 32 ++i; 33 t1 = t1->next; 34 } 35 36 (int)spaceSave[0] = n; 37 38 return n; 39 } 40 41 int creatHuffmanTree(nodeHuffmanTree_t *headLinkList, nodeHuffmanTree_t **headhuffmanTree) 42 { 43 //nodeHuffmanTree_t **spaceSave = NULL; 44 45 int n = getSpaceSave(headLinkList); 46 int n2 = (int)spaceSave[0]; 47 48 while (n2 > 1) 49 { 50 51 int t1, t2; 52 53 getMinTwo(spaceSave, n, &t1, &t2); 54 55 56 makeBranch(spaceSave, n, t1, t2); 57 58 n2--; 59 } 60 61 while (n >= 1) 62 { 63 if (spaceSave[n] != NULL) 64 { 65 *headhuffmanTree = spaceSave[n]; 66 break; 67 } 68 else 69 { 70 n--; 71 } 72 } 73 74 return 0; 75 }
5.实现对huffman树的Huffman编码:
(huffmanCode.c)//先后顺序以代码为主 &_&
1 #include"myHuffmanHead.h" 2 3 4 5 /* 6 7 递归 每次向下递归是 向左递归 传0 向右传1 8 每次接受并改掉 ' ' 为传的 0或1 然后追加 ' '; 9 每次传个n来记录编码空间长度 n+1 10 11 */ 12 int huffmanCode(nodeHuffmanTree_t *headLinkList, nodeHuffmanTree_t *headhuffmanTree) 13 { 14 headhuffmanTree->code = (char*)malloc(2); 15 16 *(headhuffmanTree->code) = '