实现哈夫曼树构建和哈夫曼编码的生成基于顺序数组存储哈夫曼结点。#includestdio.h#includestdlib.h#defineMAX_CODE_LENGTH100#defineMY_INT_MAX9999typedefstructHuffmanNode{charcharacter;intparent;intdirection;intweight;}HuffmanNode;// 初始化哈夫曼树HuffmanNode*huffmanTreeInit(constcharcharacters[],constintweights[],intnum){if(num0){printf(Error: Invalid number of characters!\n);returnNULL;}constinttotalNodesnum*2-1;HuffmanNode*tree(HuffmanNode*)malloc(sizeof(HuffmanNode)*totalNodes);if(!tree){printf(Error: Memory allocation failed!\n);returnNULL;}// 初始化叶子节点for(inti0;inum;i){tree[i].charactercharacters[i];tree[i].weightweights[i];tree[i].parent-1;tree[i].direction-1;}// 初始化内部节点for(intinum;itotalNodes;i){tree[i].characterx;tree[i].weight-1;tree[i].parent-1;tree[i].direction-1;}returntree;}// 打印哈夫曼树voidhuffmanTreePrint(constHuffmanNode*tree,intnumLeaves){constinttotalNodesnumLeaves*2-1;printf(%-8s%-8s%-8s%-8s\n,Char,Parent,Dir,Weight);for(inti0;itotalNodes;i){printf(%-8c%-8d%-8d%-8d\n,tree[i].character,tree[i].parent,tree[i].direction,tree[i].weight);}}// 查找最小权值节点下标intfindMinWeightIndex(constHuffmanNode*tree,intcurrentSize){intminWeightMY_INT_MAX;intminIndex-1;for(inti0;icurrentSize;i){if(tree[i].parent-1tree[i].weight!-1tree[i].weightminWeight){minWeighttree[i].weight;minIndexi;}}returnminIndex;}// 构建哈夫曼树voidbuildHuffmanTree(HuffmanNode*tree,intnumLeaves){if(!tree||numLeaves1)return;intcurrentSizenumLeaves;constinttotalNodesnumLeaves*2-1;for(intposnumLeaves;postotalNodes;pos){intmin1findMinWeightIndex(tree,currentSize);if(min1-1)break;tree[min1].parentpos;tree[min1].direction0;intmin2findMinWeightIndex(tree,currentSize);if(min2-1)break;tree[min2].parentpos;tree[min2].direction1;tree[pos].weighttree[min1].weighttree[min2].weight;tree[pos].parent-1;tree[pos].direction-1;currentSize;}}// 生成并打印哈夫曼编码voidfindEncoding(constHuffmanNode*tree,chartarget,intnumLeaves){intcode[MAX_CODE_LENGTH]{0};intcodeLength0;intindex-1;for(inti0;inumLeaves;i){if(tree[i].charactertarget){indexi;break;}}if(index-1){printf(Character %c not found!\n,target);return;}intcurrentindex;while(tree[current].parent!-1){code[codeLength]tree[current].direction;currenttree[current].parent;}printf(%c encoding: ,target);for(inticodeLength-1;i0;--i){printf(%d,code[i]);}printf(\n);}// 测试函数voidhuffmanTest(){constintnumChars5;constcharchars[]{a,b,c,d,e};constintweights[]{52,8,15,23,2};printf(\n Huffman Tree Test \n);HuffmanNode*treehuffmanTreeInit(chars,weights,numChars);if(!tree)return;printf(\nInitial tree:\n);huffmanTreePrint(tree,numChars);buildHuffmanTree(tree,numChars);printf(\nAfter construction:\n);huffmanTreePrint(tree,numChars);printf(\nEncodings:\n);for(inti0;inumChars;i){findEncoding(tree,chars[i],numChars);}free(tree);}intmain(){huffmanTest();return0;}运行结果c-1-115d-1-123e-1-12x-1-1-1x-1-1-1x-1-1-1x-1-1-1After construction:Char Parent Dir Weight a8152b518c6115d7023e502x6010x7125x8048x-1-1100Encodings:aencoding:1bencoding:0101cencoding:011dencoding:00eencoding:0100
