0001 HuffTree* minHChar ( HuffForest* forest ) { //在Huffman森林中找出权重最小的(超)字符 0002 ListNodePosi ( HuffTree* ) p = forest->first(); //从首节点出发查找 0003 ListNodePosi ( HuffTree* ) minChar = p; //最小Huffman树所在的节点位置 0004 int minWeight = p->data->root()->data.weight; //目前的最小权重 0005 while ( forest->valid ( p = p->succ ) ) //遍历所有节点 0006 if ( minWeight > p->data->root()->data.weight ) //若当前节点所含树更小,则 0007 { minWeight = p->data->root()->data.weight; minChar = p; } //更新记录 0008 return forest->remove ( minChar ); //将挑选出的Huffman树从森林中摘除,并返回 0009 } 0010 0011 HuffTree* generateTree ( HuffForest* forest ) { //Huffman编码算法 0012 while ( 1 < forest->size() ) { 0013 HuffTree* T1 = minHChar ( forest ); HuffTree* T2 = minHChar ( forest ); 0014 HuffTree* S = new HuffTree(); 0015 S->insertAsRoot ( HuffChar ( '^', T1->root()->data.weight + T2->root()->data.weight ) ); 0016 S->attachAsLC ( S->root(), T1 ); S->attachAsRC ( S->root(), T2 ); 0017 forest->insertAsLast ( S ); 0018 } //assert: 循环结束时,森林中唯一(列表首节点中)的那棵树即Huffman编码树 0019 return forest->first()->data; 0020 }