01109143朱子骏.docxVIP

《数据结构》实验报告题目:_ 哈夫曼树的实现学号:_________姓名:_朱子骏__________教师:___李香菊________东南大学成贤学院计算机系2012年4月23日huffman_tree.h的代码：#ifndef __HUFFMAN_TREE_H__#define __HUFFMAN_TREE_H__#include string.h// 串类#include huffman_tree_node.h// 哈夫曼树结点类模板// 哈夫曼树类模板template class CharType, class WeightTypeclass HuffmanTree{protected:// 哈夫曼树的数据成员:HuffmanTreeNodeWeightType *nodes;// 存储结点信息,nodes[0]未用CharType *LeafChars;// 叶结点字符信息,LeafChars[0]未用String *LeafCharCodes;// 叶结点字符编码信息,LeafCharCodes[0]未用int curPos;// 译码时从根结点到叶结点路径的当前结点int num;// 叶结点个数//辅助函数模板:void Select(int cur, int r1, int r2);// nodes[1 ~ cur]中选择双亲为0,权值最小的两个结点r1,r2void CreatHuffmanTree(CharType ch[], WeightType w[], int n);// 由字符,权值和字符个数构造哈夫曼树public:// 哈夫曼树方法声明及重载编译系统默认方法声明:HuffmanTree(CharType ch[], WeightType w[], int n);// 由字符,权值和字符个数构造哈夫曼树virtual ~HuffmanTree();// 析构函数模板String Encode(CharType ch);// 编码LinkListCharType Decode(String strCode);// 译码HuffmanTree(const HuffmanTreeCharType, WeightType copy);// 复制构造函数模板HuffmanTreeCharType, WeightType operator=(const HuffmanTreeCharType, WeightType copy);// 重载赋值运算符};// 孩子兄弟表示哈夫曼树类模板的实现部分template class CharType, class WeightTypevoid HuffmanTreeCharType, WeightType::Select(int cur, int r1, int r2)// 操作结果：nodes[1 ~ cur]中选择双亲为0,权值最小的两个结点r1,r2{r1 = r2 = 0;// 0表示空结点for (int pos = 1; pos = cur; pos++){// 查找树值最小的两个结点if (nodes[pos].parent != 0) continue;// 只处理双亲不为0的结点if (r1 == 0){// r1为空,将pos赋值给r1r1 = pos;}else if (r2 == 0){// r2为空,将pos赋值给r2r2 = pos;}else if(nodes[pos].weight nodes[r1].weight){// nodes[pos]权值比nodes[r1]更小,将pos赋为r1r1 = pos;}else if (nodes[pos].weight nodes[r2].weight){// nodes[pos]权值比nodes[r2]更小,将pos赋为r2r2 = pos;}}}template class CharType, class WeightTypevoid HuffmanTreeCharType, WeightType::CreatHuffmanTree(CharType ch[], WeightType w[], int n)// 操作结果：由字符,权值和字符个数构造哈夫曼树{num = n;// 叶结点个数int m = 2 * n - 1;// 结点个数nodes = new HuffmanTreeNodeWeightType[m + 1];// nodes[0]未用LeafChars = new CharType[n + 1];// LeafChars[0]未用LeafCharCodes = new String[n + 1];// LeafCharCodes[0]未用int