(2020年7月整理)数据结构哈夫曼树编码译码实验报告

1//HaffmanTree.h#include<iostream>#include<fstream>#include<string>structHuffmanNode//哈夫曼树的一个结点{weightparentintlchild,rchild;classHuffmanTree//哈夫曼树{private:HuffmanNode*Node;//Node[]存放哈夫曼树char*Info;//Info[]存放源文用到的字符——源码，如'a','b','c','d','e'，此内容可以放入结点中，不单独设数组存放intLeafNum;//哈夫曼树的叶子个数，也是源码个数public:HuffmanTree();~HuffmanTree();voidCreateHuffmanTree();/*在内存中建立哈夫曼树，存放在Node[]中。让用户从两选择：入哈夫曼树信息，建立哈夫曼树*/voidCreateHuffmanTreeFromKeyboard();voidCreateHuffmanTreeFromFile();voidEncoder();/*使用建立好的哈夫曼树(如果不在内存，则从文件hfmTree中读入并建立内存里的哈夫曼树)，voidDecoder();/*待译码的码文存放在文件CodeFile中，使用建立好的哈夫曼树(如则从文件hfmTree中读入并建立内存里的哈夫曼树)将码文译码，voidPrintCodeFile码文文件CodeFile显示在屏幕上*/voidPrintHuffmanTree();/*将哈夫曼树以直观的形式(凹入表示法，或广义表，或其他树形表示法)显示在屏幕上，voidPrintHuffmanTree_aoru(intT,intlayer=1);/*凹入表示法显示哈夫曼树，由2PrintHuffmanTree()调用*////////////////////////////////////////////////////////////////////HuffmanTree.#include<string>#include<limits>//为使用整型最大值#include"HuffmanTree.h"usingnamespacestd;//******************************************************HuffmanTree::HuffmanTree(){Node=NULL;}//******************************************************HuffmanTree::~HuffmanTree(){delete[]Node;}//******************************************************voidHuffmanTree::CreateHuffmanTree(){charChoose;cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";cin>>Choose;if(Choose=='2'){//键盘输入建立哈夫曼树CreateHuffmanTreeFromKeyboard();}//choose=='2'else{//从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();}}//******************************************************voidHuffmanTree::CreateHuffmanTreeFromKeyboard(){cin>>Num;if(Num<=1){return;}LeafNum=Num;Node=newHuffmanNode[2*Num-1];3Info=newchar[2*Num-1];for(inti=0;i<Num;i++){//读入哈夫曼树的叶子结点信息cout<<"请输入第"<<i+1<<"个字符值";getchar();Info[i]=getchar();//源文的字符存入字符数组Info[]getchar();cout<<"请输入该字符的权值或频度";cin>>Node[i].weight;//源文的字符权重存入Node[].weightNode[i].parent=-1;Node[i].lchild=-1;Node[i].rchild=-1;}for(i=Num;i<2*Num-1;i++){//循环建立哈夫曼树内部结点intpos1=-1,pos2=-1;intmax1=32767,max2=32767;for(intj=0;j<i;j++)//在根节点中选出权值最小的两个if(Node[j].parent==-1)//是否为根结点if(Node[j].weight<max1){max2=max1;max1=Node[j].weight;pos2=pos1;pos1=j;}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;Node[i].weight=Node[pos1].weight+Node[pos2].weight;r//把建立好的哈夫曼树写入文件hfmTree.datcharch;cout<<"是否要替换原来的哈夫曼树文件(Y/N):";cin>>ch;if(ch!='y'&&ch!='Y')return;4{ofstreamfop;fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc);//打开文件{return;}fop.write((char*)&Num,sizeof(Num));//先写入哈夫曼树的叶子结点个数for(i=0;i<Num;i++){//再写入源文字符集的所有字符(存储在Info[]中)fop.write((char*)&Info[i],sizeof(Info[i]));flush(cout);}for(i=0;i<2*Num-1;i++){//最后写入哈夫曼树的各个结点(存储在Node[]中)fop.write((char*)&Node[i],sizeof(Node[i]));flush(cout);}fop.close();//关闭文件}}//******************************************************voidHuffmanTree::CreateHuffmanTreeFromFile(){ifstreamfip;{couthfmTreedat败，无法建立哈夫曼树。\n";return;}if(LeafNum<=1){fip.close();return;}Info=newchar[LeafNum];5Node=newHuffmanNode[2*LeafNum-1];for(inti=0;i<LeafNum;i++)for(i=0;i<2*LeafNum-1;i++)fip.close();}//******************************************************voidHuffmanTree::Encoder(){if(Node==NULL){//内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树CreateHuffmanTreeFromFile();if(LeafNum<=1){return;}char*SourceText;//字符串数组，用于存放源文//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入charChoose;cout按1)，还是从键盘输入源文(按2)？";cin>>Choose;if(Choose=='1'){ifstreamfip1("ToBeTran.txt");{return;}charch;while(fip1.get(ch))k++;//第一次读文件只统计文件中有多少个字符，将字符fip1.close();SourceText=newchar[k+1];//申请存放源文的字符数组空间k=0;while(fip2.get(ch))SourceText[k++]=ch;6fip2.close();SourceText[k]='\0';cout<<SourceText<<endl;}stringSourceBuff;cin.ignore();cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";getline(cin,SourceBuff,'\n');while(SourceBuff[k]!='\0')k++;SourceText=newchar[k+1];k=0;while(SourceBuff[k]!='\0'){SourceText[k]=SourceBuff[k];k++;}SourceText[k]='\0';cout<<"覆盖已有的编码原文件?(Y/N)";charch;cin>>ch;{ofstreamfip2;p{abort();}fip2<<SourceText<<endl;fip2.close();}}//开始编码ofstreamfop("CodeFile.dat",ios::trunc);//打开码文存放文件char*code;code=newchar[LeafNum];//存放一个源文字符的编码7while(SourceText[k]!='\0')//源文串中从第一个字符开始逐个编码{intstarcharch=SourceText[k];for(inti=0;i<LeafNum;i++)if(Info[i]==ch)//求出该文字所在的单元编号break;while(Node[j].parent!=-1){j=Node[j].parent;if(Info[Node[j].lchild]==Info[i])code[star++]='0';elsecode[star++]='1';}code[star]='\0';for(i=0;i<star/2;i++){intj=code[i];code[i]=code[star-i-1];code[star-i-1]=j;}i=0;//将源文的当前字符的对应编码写入码文文件while(code[i]!='\0'){fop<<code[i];}k++;//源文串中的字符后移一个}fop.close();}//******************************************************voidHuffmanTree::Decoder(){if(Node==NULL){CreateHuffmanTreeFromFile();if(LeafNum<=1){8return;}}ifstreamfip1("CodeFile.dat");{return;}char*CodeStr;charch;while(fip1.get(ch)){k++;}fip1.close();CodeStr=newchar[k+1];ifstreamfip2("CodeFile.dat");k=0;while(fip2.get(ch))CodeStr[k++]=ch;fip2.close();CodeStr[k]='\0';ofstreamfop("TextFile.dat");intjLeafNum1-1;//j指向哈夫曼树的根inti=0;//码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子while(CodeStr[i]!='\0'){//下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符if(CodeStr[i]=='0')j=Node[j].lchild;elsej=Node[j].rchild;if(Node[j].rchild==-1){cout<<Info[j];fop<<Info[j];j=LeafNum*2-1-1;}}9fop.close();}//******************************************************voidHuffmanTree::PrintCodeFile(){charch;iifstreamfip("CodeFile.dat");ofstreamfop("CodePrin.dat");{return;}while(fip.get(ch)){cout<<ch;fop<<ch;{cout<<endl;fop<<endl;}}cout<<endl;fop<<endl;fip.close();fop.close();}//******************************************************voidHuffmanTree::PrintHuffmanTree(){if(Node==NULL){CreateHuffmanTreeFromFile();if(LeafNum<=1){return;}}ofstreamfop("TreePrint.dat",ios_base::trunc);fop.close();PrintHuffmanTree_aoru(2*LeafNum-1-1,0);return;}//******************************************************voidHuffmanTree::PrintHuffmanTree_aoru(intT,intlayer){for(inti=0;i<layer;i++)cout<<"___";cout<<Node[T].weight<<endl;if(Node[T].lchild!=-1)PrintHuffmanTree_aoru(Node[T].lchild,++layer);if(Node[T].rchild!=-1)PrintHuffmanTree_aoru(Node[T].rchild,layer--);}///////////////////////////////////////////////////////////////////main.cpp#include<string.h>#include<stdlib.h>usingnamespacestd;main{HuffmanTreehuftree;charChoose;while(1){***********************"<<endl;cout<<"您可以进行以下操作:"<<endl;cout<<"1建立哈夫曼树3译码(码文已在文件CodeFile中)5显示哈夫曼树"<<endl;cout<<"2编码(源文已在文件ToBeTran中，或键盘输入)4显示码文6退出"<<endl;cout<<"请选择一个操作:";cin>>Choose;switch(Choose){case'1':huftree.CreateHuffmanTree();break;case'2':huftree.E