C语言数据结构之哈夫曼树及哈夫曼编码的实现 1 #pragma once 2 #include<stdio.h> 3 #include”stdlib.h” 4 #include <string.h> 5 6 typedef int ElemType1; 7 8 struct BTreeNode 9 { 10 ElemType1 data; 11 struct BTreeNode* left; 12 struct BTreeNode* right; 13 }; 14 //遍历哈夫曼树 15 void PrintBTree_int(struct BTreeNode* BT) 16 { 17 if (BT != NULL) 18 { 19 printf(“%d”, BT->data); 20 if (BT->left != NULL || BT->right != NULL) 21 { 22 printf(” ( “); 23 PrintBTree_int(BT->left); //输出左子树 24 if (BT->right != NULL) 25 printf(” , “); 26 PrintBTree_int(BT->right); //输出右子树 27 printf(” ) “); 28 } 29 } 30 } 31 32 //创建哈夫曼树 33 struct BTreeNode* CreateHuffman(ElemType1 a[], int n) 34 { 35 int i, j; 36 struct BTreeNode b, *q; 37 b = (BTreeNode )malloc(n * sizeof(struct BTreeNode)); 38 for (i = 0; i < n; i++) //动态内存分配 39 { 40 b[i] = (BTreeNode *)malloc(sizeof(struct BTreeNode)); 41 b[i]->data = a[i]; 42 b[i]->left = b[i]->right = NULL; 43 } 44 for (i = 1; i < n; i++) 45 { 46 //k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标 47 int k1 = -1, k2; 48 for (j = 0; j < n; j++) //让k1初始指向森林中第一棵树，k2指向第二棵 49 { 50 if (b[j] != NULL && k1 == -1) 51 { 52 k1 = j; 53 continue; 54 } 55 if (b[j] != NULL) 56 { 57 k2 = j; 58 break; 59 } 60 } 61 for (j = k2; j < n; j++) //构造最优解 62 { 63 if (b[j] != NULL) 64 { 65 if (b[j]->data < b[k1]->data) 66 { 67 k2 = k1; 68 k1 = j; 69 } 70 else if (b[j]->data < b[k2]->data) 71 k2 = j; 72 } 73 } 74 q = (BTreeNode *)malloc(sizeof(struct BTreeNode)); 75 q->data = b[k1]->data + b[k2]->data; 76 q->left = b[k1]; 77 q->right = b[k2]; 78 79 b[k1] = q; 80 b[k2] = NULL; 81 } 82 free(b); 83 return q; 84 } 85 //计算带权路径 86 ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0 87 { 88 if (FBT == NULL) //空树返回0 89 return 0; 90 else 91 { 92 if (FBT->left == NULL && FBT->right == NULL) 93 return FBT->data * len; 94 else 95 return WeightPathLength(FBT->left, len + 1) + WeightPathLength(FBT->right, len + 1); 96 } 97 } 98 99 //构造哈夫曼编码 100 void HuffManCoding(struct BTreeNode* FBT, int len) 101 { 102 static int a[10]; 103 if (FBT != NULL) 104 { 105 if (FBT->left == NULL && FBT->right == NULL) 106 { 107 int i; 108 printf(“结点的值为%d的编码：”, FBT->data); 109 for (i = 0; i < len; i++) 110 printf(“%d”, a[i]); 111 printf(” ”); 112 } 113 else 114 { 115 a[len] = 0; 116 HuffManCoding(FBT->left, len + 1); 117 a[len] = 1; 118 HuffManCoding(FBT->right, len + 1); 119 } 120 } 121 }
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/70676.html
