哈夫曼树大实验报告.doc

// 程序名：Huffman.h // 程序功能：输入字符集，生成哈夫曼树，对文件进行编码译码,输出 // 作者：xx // 日期：2009.12.20 // 版本：1.0 //” Huffman.h” #includeiostream.h #includeiomanip.h #includefstream.h struct HuffmanNode { public: int weight;//存放结点的权值，假设只考虑处理权值为整数的情况 int Mark;//标记结点是否被访问过 int parent;//-1表示为根结点，否则表示为非根结点 int lchild,rchild;//分别存放改结点的左，右孩子的所在单元的编号 }; class HuffmanTree { public: int head;//根结点 HuffmanNode *Node;//哈夫曼树中结点的存储结构 char * Info;//用来保存各字符的信息 int LeafNum;//树中的叶子结点总数 void Initialization(int WeightNum);//初始化 void Encoding();//利用构造好的哈夫曼树对字符ch进行编码 void Decoding();//对二进制串进行译码 void WriteHuffmanFile();//将哈夫曼的信息写入文件 void ReadHuffmanFile();//从文件中读出哈夫曼的信息 void Print();//输出经过编码后的码文 void Tree_Print(int,int);//以凹形表是形式输出哈夫曼树 int Gethead();//获取头文件 }; // #includeHuffman.h /////////////////////////////////////////////////////////////////////////////////////////////////////// //初始化 void HuffmanTree::Initialization(int WeightNum) { int i,j,pos1,pos2,max1,max2; Node=new struct HuffmanNode[2*WeightNum-1] ;//WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1; Info=new char[2* WeightNum-1]; for(i=0;iWeightNum;i++) { cout 请输入第i+1个字符值; cinInfo[i]; coutendl请输入该字符的权值或频度; cinNode[i].weight ; Node[i].Mark =i+1; Node[i].parent =-1;//为根结点 Node[i].lchild =-1;//无左孩子 Node[i].rchild =-1;//无右孩子 } for(i=WeightNum;i2*WeightNum-1;i++) { pos1=-1; pos2=-1;//分别用来存放当前最小值和次小值的所在单元编号 max1=32767;//32767为整型树的最大值 max2=32767;//分别用来存放当前找到的最小值和次小值 for(j=0; j=i-1;j++)//在根结点中选出权值最小的两个 if(Node[j].parent ==-1)//是否为根结点 if(Node[j].weight max1)//是否比最小值要小 { max2=max1;//原最小值变为次小值 max1=Node[j].weight ;//存放最小值 pos2=pos1;//修改次小值所在的单元编号 pos1=j;//修改最小值所在的单元编号 } else if(Node[j].weight max2)//比原最小值大但比原次小值要小 { max2=Node[j].weight ;//存放次小值 pos2=j;//修改次小值所在的单元编号 } Node[pos1].parent =i; Node[pos2].parent =i; Node[i].lchild =pos1; Node[i].rchild =pos2; Node[i].parent =-1;//表示新阶段应该是根结点