哈夫曼树及编码 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 struct node 5 { 6 int key; 7 struct node *l; 8 struct node *r; 9 }; 10 typedef struct node *pnode; 11 int mark[100]; 12 struct node huffman[100]; 13 void PrintNode(const pnode node) 14 { 15 printf(“key = %d ”, node->key); 16 } 17 void PreOrder(pnode T) 18 { 19 if(T) 20 21 { 22 PrintNode(T); 23 PreOrder(T->l); 24 25 PreOrder(T->r); 26 27 } 28 29 } 30 void Select(int *mark, struct node *huffman, int size, int *choose) 31 { 32 33 int i; 34 35 for(i = 0; i< size; i++) 36 { 37 if(mark[i]) 38 { 39 choose[0] = i; 40 i++; 41 break; 42 } 43 } 44 choose[1] = choose[0]; 45 for(; i < size; i++) 46 { 47 if(mark[i]) 48 { 49 if(huffman[choose[0]].key >= huffman[i].key) 50 { 51 choose[1] = choose[0]; 52 choose[0] = i; 53 54 55 } 56 else if(huffman[choose[1]].key > huffman[i].key) choose[1] = i; 57 58 59 } 60 61 } 62 } 63 void Choose(int *mark, struct node *huffman, int size, int *choose) 64 { 65 int i; 66 int minkey = 0; 67 int tkey = 0; 68 int temp = 0; 69 for(i = 0; i< size; i++) 70 { 71 if(mark[i]) 72 { 73 minkey = i; 74 i++; 75 break; 76 } 77 } 78 tkey = minkey; 79 for(; i< size; i++) 80 { 81 if(mark[i]) 82 { 83 if(huffman[i].key < huffman[minkey].key) 84 { 85 tkey = minkey; 86 minkey = i; 87 } 88 if(tkey == minkey) 89 tkey = i; 90 if(huffman[tkey].key > huffman[i].key && i != minkey) 91 { 92 tkey = i; 93 } 94 } 95 } 96 choose[0] = minkey; 97 choose[1] = tkey; 98 } 99 pnode HuffmanTree(int *mark, struct node *huffman, int size) 100 { 101 int choose[2]; 102 int i; 103 pnode mynode; 104 105 for(i = 0; i < size-1; i++) 106 { 107 Select(mark, huffman, size, choose); 108 mynode = (pnode)malloc(sizeof(struct node)); 109 mynode->key = huffman[choose[0]].key+huffman[choose[1]].key;//更新key值 110 mynode->l = (pnode)malloc(sizeof(struct node)); 111 mynode->l->key = huffman[choose[0]].key; 112 mynode->l->l = huffman[choose[0]].l; 113 mynode->l->r = huffman[choose[0]].r; 114 mynode->r = &huffman[choose[1]]; 115 huffman[choose[0]] = *mynode; 116 mark[choose[1]] = 0; 117 free(mynode); 118 } 119 return &huffman[choose[0]]; 120 } 121 int main(void) 122 { 123 int key[8] = {5,29,7,8,14,23,3,11}; 124 int i; 125 pnode huffmantree; 126 memset(mark, -1, sizeof(mark)); 127 memset(huffman, 0, sizeof(huffman)); 128 for(i = 0; i < 8; i++) 129 { 130 huffman[i].key = key[i]; 131 } 132 huffmantree = HuffmanTree(mark, huffman, 8); 133 PreOrder(huffmantree); 134 return 0; 135 }
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/55839.html
