哈夫曼树大实验报告

/程序名：Huffman.h

/程序功能：输入字符集，生成哈，对文件进行编码译码,输出

/作者：__

/日期：2009.12.20

/版本：1.0

/”Huffman.h”

include

include"iomanip.h"

include"fstream.h"

structHuffmanNode

public:

classHuffmanTree

intweight;/存放结点的权值，假设只考虑处理权值为整数的情况intMark;/标记结点是否被访问过intparent;/-1表示为根结点，否则表示为非根结点intlchild,rchild;/分别存放改结点的左，右孩子的所在单元的编号

public:

include"Huffman.h"

/初始化

voidHuffmanTree::Initialization(intWeightNum)

inthead;/根结点HuffmanNodeNode;/哈中结点的存储结构charInfo;/用来保存各字符的信息intLeafNum;/树中的叶子结点总数voidInitialization(intWeightNum);/初始化voidEncoding();/利用构造好的哈对字符ch进行编码voidDecoding();/对二进制串进行译码voidWriteHuffmanFile();/将哈夫曼的信息写入文件voidReadHuffmanFile();/从文件中读出哈夫曼的信息voidPrint();/输出经过编码后的码文voidTree_Print(int,int);/以凹形表是形式输出哈intGethead();/获取头文件inti,j,pos1,pos2,ma_1,ma_2;

Node=newstructHuffmanNode[2WeightNum-1];/WeightNum权值对应的哈中的结点总数为2WeightNum-1;

Info=newchar[2WeightNum-1];for(i=0;iInfo[i];cout<Node[i].weight;Node[i].Mark=i+1;Node[i].parent=-1;/为根结点Node[i].lchild=-1;/无左孩子Node[i].rchild=-1;/无右孩子}for(i=WeightNum;i<2WeightNum-1;i++){pos1=-1;pos2=-1;/分别用来存放当前最小值和次小值的所在单元编号ma_1=32767;/32767为整型树的最大值

ma_2=32767;/分别用来存放当前找到的最小值和次小值for(j=0;j<=i-1;j++)/在根结点中选出权值最小的两个if(Node[j].parent==-1)/是否为根结点

小值要小

if(Node[j].weight

Node[i].parent=-1;/表示新阶段应该是根结点Node[i].weight=Node[pos1].weight+Node[pos2].weight;

Node[i].Mark

+Node[pos2].Mark;

=Node[pos1].Mark}/forLeafNum=WeightNum;

cout<<"哈构造成功。"<

WriteHuffmanFile();

}/HuffmanTree

/利用构造好的哈对字符进行编码

voidHuffmanTree::Encoding()

ifstreamf1("ToBeTran.t_t");if(f1.fail()){cout<<"源文文件打开失败!请建立好ToBeTran.t_t，再操作！ ";

}return;

charch;

intk=0;while(f1.get(ch))k++;f1.close();

charTe_t;

Te_t=newchar[k+1];ifstreamf2("ToBeTran.t_t");k=0;while(f2.get(ch))Te_t[k++]=ch;f2.close();Te_t[k]='