树和哈夫曼树实验报告_哈夫曼树实验报告

2020-02-28 其他范文下载本文

树和哈夫曼树实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“哈夫曼树实验报告”。

树和哈夫曼树实验报告

一．实验目的练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码二．实验环境

Microsoft visual c++ 三．实验问题描述

1.问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。

基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。测试数据：

ABCØØDEØGØØFØØØ（其中Ø表示空格字符）输出结果为：先序：ABCDEGF 先序：CBEGDFA 先序：CGEFDBA 2.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。基本要求：(至少完成功能1-2）一个完整的系统应具有以下功能： I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。基本要求：

E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

D：译码（Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。

P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：

设权值w=（5，29，7，8，14，23，3，11），n=8。

按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：

5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。四．实验主要程序流

实验题目一主要程序：

1．void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点// { char ch;ch=getchar();if(ch=='.')*bt=NULL;else { *bt=(BitTree)malloc(sizeof(BitNode));(*bt)->data=ch;CreatBiTree(&((*bt)->LChild));CreatBiTree(&((*bt)->RChild));} } 2．void Visit(char ch)//访问根节点 { printf(“%c ”,ch);} 3．

void PreOrder(BitTree root){ if(root!=NULL){ Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);} } 4． void InOrder(BitTree root){ if(root!=NULL){ InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);} } 5．int PostTreeDepth(BitTree bt)//后序遍历求二叉树的高度递归算法// { int hl,hr,max;if(bt!=NULL){ hl=PostTreeDepth(bt->LChild);//求左子树的深度

hr=PostTreeDepth(bt->RChild);//求右子树的深度

max=hl>hr?hl:hr;//得到左、右子树深度较大者

return(max+1);//返回树的深度 } else return(0);//如果是空树，则返回0 } 6．void PrintTree(BitTree Boot,int nLayer)//按竖向树状打印的二叉树 // { int i;if(Boot==NULL)return;PrintTree(Boot->RChild,nLayer+1);for(i=0;idata);PrintTree(Boot->LChild,nLayer+1);} 7．void main(){ BitTree T;int h;int layer;int treeleaf;layer=0;printf(“请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):n”);CreatBiTree(&T);printf(“先序遍历序列为:”);PreOrder(T);printf(“n中序遍历序列为:”);InOrder(T);printf(“n后序遍历序列为:”);PostOrder(T);h=PostTreeDepth(T);printf(“此二叉树的深度为:%dn”,h);printf(“此二叉树的横向显示为：n”);PrintTree(T,layer);} 实验二主要程序流： 1．int main(){ HuffmanTree huftree;char Choose;while(1){ cout>Choose;switch(Choose){ case '1': huftree.CreateHuffmanTree();break;case '2': huftree.Encoder();break;case '3': huftree.Decoder();break;case '4': huftree.PrintCodeFile();break;case '5': huftree.PrintHuffmanTree();break;case '6': cout

// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）void HuffmanTree::CreateHuffmanTree(){char Choose;cout>Choose;if(Choose=='2'){ //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();}//choose=='2' else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

CreateHuffmanTreeFromFile();} } 3.// 从键盘建立哈夫曼树函数

// 函数功能：从键盘建立哈夫曼树 //函数参数：无 //参数返回值：无

void HuffmanTree::CreateHuffmanTreeFromKeyboard(){ int Num;cout>Num;if(Num

cout>Node[i].weight;//源文的字符权重存入Node[].weight Node[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;Node[i].code=“”;} for(int j=Num;j

int pos1,pos2;int max1,max2;pos2=pos1=j;max2=max1=numeric_limits::max();//在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标

//pos2最后应指向权重第二小的根结点的下标 //max1存放当前找到的权重最小的根结点的权重 //max2存放当前找到的权重第二小的根结点的权重

for(int k=j-1;k>=0;k--){ if(Node[k].parent==-1){//如果是某棵子树的根结点

if(Node[k].weight

max2=max1;max1=Node[k].weight;pos2=pos1;pos1=k;} else if(Node[k].weight

max2=Node[k].weight;pos2=k;} }//if(Node[j].parent==-1)} //for //在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点

Node[pos1].parent=j;Node[pos2].parent=j;Node[j].lchild=pos1;Node[j].rchild=pos2;Node[j].parent=-1;Node[j].weight=Node[pos1].weight+Node[pos2].weight;} //for

//产生所有叶子结点中字符的编码

for(int m=0;m

int j=m;int j1;while(Node[j].parent!=-1){ //从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[] j1=Node[j].parent;if(Node[j1].lchild==j)Node[m].code.insert(0,“0”);else Node[m].code.insert(0,“1”);j=j1;}} cout

//把建立好的哈夫曼树写入文件hfmTree.dat char ch;cout>ch;if(ch!='y'&&ch!='Y')return;ofstream fop;fop.open(“hfmTree.dat”,ios::out|ios::binary|ios::trunc);//打开文件

if(fop.fail()){ cout

for(int n=0;n

fop.write((char*)&Node[n],sizeof(Node[n]));flush(cout);} fop.close();//关闭文件

cout

// 函数功能：从文件建立哈夫曼树 //函数参数：无 //参数返回值：无

void HuffmanTree::CreateHuffmanTreeFromFile(){ ifstream fip;fip.open(“hfmTree.dat”,ios::binary|ios::in);if(fip.fail()){ cout

// 函数功能：为哈夫曼树编码 //函数参数：无 //参数返回值：无

void HuffmanTree::Encoder(){ if(Node==NULL){ //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树

CreateHuffmanTreeFromFile();if(LeafNum

//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入 char Choose;cout>Choose;if(Choose=='1'){ ifstream fip1(“ToBeTran.txt”);if(fip1.fail()){ cout

ifstream fip2(“ToBeTran.txt”);//第二次读源文文件，把内容写入SourceText[] k=0;while(fip2.get(ch))SourceText[k++]=ch;fip2.close();SourceText[k]='';} else { //从键盘输入源文

string SourceBuff;cin.ignore();cout

ofstream fop(“CodeFile.dat”,ios::trunc);//打开码文存放文件 int k=0;while(SourceText[k]!='')//源文串中从第一个字符开始逐个编码 { int i;for(i=0;i

if(Node[i].sourcecode==SourceText[k]){ //将对应编码写入码文文件

fop=LeafNum){ cout

// 函数功能：对哈夫曼树进行译码 //函数参数：无 //参数返回值：无

void HuffmanTree::Decoder(){//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树 if(Node==NULL){ CreateHuffmanTreeFromFile();if(LeafNum

//将码文从文件CodeFile.dat中读入 CodeStr[] ifstream fip1(“CodeFile.dat”);if(fip1.fail()){ cout

char* CodeStr;int k=0;char ch;while(fip1.get(ch)){ k++;} fip1.close();CodeStr=new char[k+1];ifstream fip2(“CodeFile.dat”);k=0;while(fip2.get(ch))CodeStr[k++]=ch;fip2.close();CodeStr[k]='';

cout

int j=LeafNum*2-1-1;//j指向哈夫曼树的根

int i=0;//码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子

while(CodeStr[i]!=''){ //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符

if(CodeStr[i]=='0')j=Node[j].lchild;else j=Node[j].rchild;if(Node[j].rchild==-1){ //因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点

cout

fop

} i++;} fop.close();

cout

// 函数功能：从文件中输出哈夫曼树的码文 //函数参数：无 //参数返回值：无

void HuffmanTree::PrintCodeFile(){ char ch;int i=1;ifstream fip(“CodeFile.dat”);ofstream fop(“CodePrin.dat”);if(fip.fail()){ cout

// 函数功能：从内存或文件中直接输出哈夫曼树 //函数参数：无 //参数返回值：无