输入
abbccc$
输出
9
样例输入 Copy
hello world$
样例输出 Copy
32
#include
#include#include #define MAX_SIZE 1000 typedef char elemtype; //带权值的二叉树 typedef struct BiTNode { elemtype data; int weight; //权重 struct BiTNode* lchild, * rchild; }BiTNode, * BiTree; //用单链表表示森林 typedef struct linkNode { BiTree tree; struct linkNode* next; }LinkNode, * Forest; //创建森林 int createForest(Forest& forest) { //待补全，读入字符串，以‘$'为结束符，根据每个字符出现频率为权值，构造森林。并返回森林中树的个数 int count = 0; // 森林中树的个数 BiTree tree; LinkNode* p = forest; char ch; char list[128] = {0}; scanf("%c", &ch); while (ch != '$') { list[ch] += 1; scanf("%c", &ch); } for (int i = 0; i < 128; i++) { if (!list[i]) continue; tree = (BiTNode*)malloc(sizeof(BiTNode)); tree->data = i; tree->weight = list[i]; tree->lchild = NULL; tree->rchild = NULL; LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode)); newNode->tree = tree; newNode->next = NULL; p->next = newNode; p = p->next; count++; } return count; } void sortForest(Forest forest) { int count = 0; LinkNode* p = forest->next; BiTree* trees = (BiTree*)malloc(sizeof(BiTree) * MAX_SIZE); // 将森林中所有的树存储到数组中 while (p != NULL) { trees[count++] = p->tree; p = p->next; } // 使用冒泡排序将树按照权值从小到大排序 for (int i = 0; i < count - 1; i++) { for (int j = 0; j < count - i - 1; j++) { if (trees[j]->weight > trees[j + 1]->weight) { BiTree tmp = trees[j]; trees[j] = trees[j + 1]; trees[j + 1] = tmp; } } } // 将排好序的树重新插入森林中 p = forest->next; for (int i = 0; i < count; i++) { p->tree = trees[i]; p = p->next; } free(trees); } BiTree createHuffmanTree(Forest forest) { // 将森林中的所有树按照权值从小到大排序 sortForest(forest); // 合并森林中的树，直到只剩下一棵树为止 while (forest->next->next != NULL) { BiTree t1 = forest->next->tree; BiTree t2 = forest->next->next->tree; // 创建新的二叉树节点，作为t1和t2的父节点 BiTree newNode = (BiTree)malloc(sizeof(BiTNode)); newNode->data = '#'; newNode->weight = t1->weight + t2->weight; newNode->lchild = t1; newNode->rchild = t2; // 将新节点插入森林中，并删除t1和t2 LinkNode* newLinkNode = (LinkNode*)malloc(sizeof(LinkNode)); newLinkNode->tree = newNode; newLinkNode->next = forest->next->next->next; forest->next->next->next = newLinkNode; forest->next = forest->next->next->next; // 重新排序森林 sortForest(forest); } // 返回剩下的最后一棵树，即哈夫曼树 return forest->next->tree; } void calculateEncodingLength(BiTNode* root, int depth, int& totalLength) { if (!root) { return; } if (!root->lchild && !root->rchild) { totalLength += depth * root->weight; } calculateEncodingLength(root->lchild, depth + 1, totalLength); calculateEncodingLength(root->rchild, depth + 1, totalLength); } int main() { Forest forest = (linkNode*)malloc(sizeof(linkNode)); //森林的单链表包含一个头结点，头结点符号‘$' forest->tree = (BiTNode*)malloc(sizeof(BiTNode)); forest->tree->data = '$'; forest->next = NULL; createForest(forest); BiTree root = createHuffmanTree(forest); int totalLength = 0; calculateEncodingLength(root, 0, totalLength); printf("%d\n",totalLength); } 
