自己写的Huffman树生成与Huffman编码实现 （实现了核心功能 ，打出了每个字符的huffman编码 其他的懒得实现了，有兴趣的朋友可以自己在我的基础增加功能 ）
/* 原创文章 转载请附上原链接: */
### 硬核警告 递归 玩的可以在往下看 核心是递归实现 ￥_￥
上图：
上代码：（思路：通过递归将父亲的Huffman编码传给给孩子 孩子以此为基础进行在编码 ）
1.头文件:(myHuffmanHead.h)
1 #pragma once 2 3 #pragma warning(disable :4996) 4 #include5 #include 6 #include 7 8 /* 9 huffmanTree : 思路10 注：每个关键字为一个节点 整个数据使用链表存储11 节点内容 : 关键字 ，出现次数 ，编码 ， 下一个节点。 12 13 将 关键字的出现频率作为权值来生成HuffmanTree 然后进行Huffman code14 //1.获取关键字频率 15 1.1 获取输入 并 记录 关键字 出现次数16 17 2.生成HuffmanTree18 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 : \n");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 !='\n')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 else30 {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 else69 {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' 为传的 0或1 然后追加 '\0'; 9 每次传个n来记录编码空间长度 n+110 11 */12 int huffmanCode(nodeHuffmanTree_t *headLinkList, nodeHuffmanTree_t *headhuffmanTree)13 {14 headhuffmanTree->code = (char*)malloc(2);15 16 *(headhuffmanTree->code) = '\0';17 18 huffmanCode_(headhuffmanTree, headhuffmanTree->lchild, '0', 1);19 huffmanCode_(headhuffmanTree, headhuffmanTree->rchild, '1', 1);20 }21 22 int huffmanCode_(nodeHuffmanTree_t *parenthuffmanTree, nodeHuffmanTree_t *nexthuffmanTree, char tempCode, int layer)23 {24 if (NULL == nexthuffmanTree)25 {26 return 0;27 }28 else29 {30 char *tempSpace = (char*)malloc(sizeof(parenthuffmanTree->code));31 32 nexthuffmanTree->code = (char*)malloc(layer+2);33 34 changeCode(parenthuffmanTree->code, nexthuffmanTree->code, tempCode, tempSpace);35 36 huffmanCode_(nexthuffmanTree, nexthuffmanTree->lchild, '0', layer + 1);37 38 huffmanCode_(nexthuffmanTree, nexthuffmanTree->rchild, '1', layer + 1);39 40 }41 }
5.1.获取一个最小key的节点是个子功能：（getMinTwo.c）
1 #include"myHuffmanHead.h" 2 3 4 static int flag = 0; 5 6 int getMinTwo(nodeHuffmanTree_t **spaceSave,int spaceSize ,int *t1, int *t2) 7 { 8 9 int i = 0;10 int j = 0;11 12 while (i<2)13 {14 int min = 1;15 j = 0;16 17 while (j+1 < spaceSize)18 {19 if (NULL==spaceSave[1 + j])20 {21 j++;22 continue;23 }24 if (0 == spaceSave[1 + j]->isCoded)25 {26 min = 1 + j;27 break;28 }29 else30 {31 j++;32 }33 }34 35 for (j= 0; j < spaceSize; ++j)36 {37 if (NULL == spaceSave[min] || NULL == spaceSave[1 + j])38 {39 continue;40 }41 if (spaceSave[min]->frequency > spaceSave[1 + j]->frequency && spaceSave[1 + j]->isCoded !=1)42 {43 min = 1 + j;44 }45 }46 47 spaceSave[min]->isCoded = 1;48 49 if (0 == flag)50 {51 *t1 = min;52 flag++;53 }54 else55 {56 *t2 = min;57 flag--;58 }59 60 i++;61 }62 63 64 }
5.2.判断是否已经编码：（isExitence.c）
1 #include"myHuffmanHead.h" 2 3 4 nodeHuffmanTree_t* isExitence(nodeHuffmanTree_t* head, char inputTemp) 5 { 6 int i = 0; 7 8 if (NULL == head) 9 {10 return NULL;11 }12 else13 {14 15 16 if((head->key==inputTemp))17 {18 return head;19 }20 else21 {22 isExitence(head->next, inputTemp);23 }24 }25 }
5.3.创建分支：（makebranch.c）
1 #include"myHuffmanHead.h" 2 3 int makeBranch(nodeHuffmanTree_t **spaceSave, int spaceSize, int t1, int t2) 4 { 5 6 nodeHuffmanTree_t *newNode = (nodeHuffmanTree_t*)malloc(sizeof(nodeHuffmanTree_t)); 7 8 newNode->frequency = spaceSave[t1]->frequency + spaceSave[t2]->frequency; 9 newNode->isCoded = 0;10 11 newNode->lchild = spaceSave[t1];12 newNode->rchild = spaceSave[t2];13 14 spaceSave[t1] = newNode;15 spaceSave[t2] = NULL;16 17 }
5.4.实现拼接孩子的编码：（changeCode.c）
1 #include"myHuffmanHead.h" 2 3 4 int changeCode(char *strParent, char *strKid, char needAppend, char *tempspace) 5 { 6 strcpy(tempspace, strParent); 7 8 char *tempP = tempspace; 9 10 while (1)11 {12 if (*tempP == '\0')13 {14 *tempP = needAppend;15 16 *(tempP + 1) = '\0';17 18 strcpy(strKid, tempspace);19 20 break;21 }22 else23 {24 ++tempP;25 }26 }27 return 0;28 }
5.5.拼接Huffman编码：（myStrCat.c）
1 #include"myHuffmanHead.h" 2 3 int myStrCat(char *des, char *str) 4 { 5 char *needCatP = des; 6 7 while (1) 8 { 9 if (*needCatP == '\0')10 {11 *needCatP = str;12 13 *(needCatP + 1) = '\0';14 15 break;16 }17 else18 {19 ++needCatP;20 }21 }22 return 0;23 }
6.打印huffman编码：（printLinkList.c）
1 #include"myHuffmanHead.h" 2 3 int printLinkList(nodeHuffmanTree_t *head) 4 { 5 printf(" Key\t Frequncy\t HuffmanCode\n\n"); 6 while (head != NULL) 7 { 8 printf(" %c\t %d\t %s\n", head->key, head->frequency, head->code); 9 10 head = head->next;11 }12 }
结语：有问题欢迎提在下方 ，本人在校学生，时间较为充裕， 有时间会回复的。
/* 原创文章 转载请附上原链接: */