📄 sm_hffmantree2.cpp
字号:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include<stdlib.h>
#include<conio.h>
using namespace std;
typedef struct //哈夫曼树的存储结构
{
int weight;
char HTch;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;//动态数组存储哈夫曼树
typedef struct //哈夫曼编码表的存储结构
{
char ch;
char* hufCh;
}HuffmanCode;//动态数组存储哈夫曼编码表
typedef struct//字符结点
{
char ch;//字符
int wt;//字符权值
}wElem;//动态分配数组存储读入字符与权值
void Select(HuffmanTree,int,int&,int&);
//void Select( HuffmanTree,unsigned int,unsigned int &,unsigned int &);
void HuffmanCoding(HuffmanTree&,HuffmanCode*,wElem,int);
void DeCoding(HuffmanTree,HuffmanCode ,char*,int);
void Print(char *);
/*void PreorderVisit( HTNode,HuffmanTree,int);
void Treeprinting( HTNode,HuffmanTree,int);*/
void Select(HuffmanTree HT,int n,int &s1,int &s2) //该函数用来选择两个权值最小的结点,结果存放在s1,s2中
{
int i,j,k,l,sw1,sw2;
for(i=1;i<=n;i++) //第一遍查询第一个parent 为0的结点
{
if(HT[i].parent==0)
{
sw1=HT[i].weight;
s1=i;
break;
}
}
for(j=i+1;j<=n;j++) //第一遍寻找第一个最小的结点存在S1中
{
if(HT[j].parent==0)
{
if(sw1 > HT[j].weight)
{
sw1=HT[j].weight;
s1=j;
}
}
}
for(k=1;k<=n;k++)//第二遍寻找第一个parent 为0的结点
{
if(HT[k].parent==0)
{
sw2=HT[k].weight;
s2=k;
if(s2==s1)
continue;
else
break;
}
}
for(l=k+1;l<=n;l++)//第二遍查询第二个最小的结点存在S2中
{
if(HT[l].parent==0)
{
if(sw2>HT[l].weight && l!=s1)//保证找到的两个结点不同,即s1!=s2;
{
sw2=HT[l].weight;
s2=l;
}
}
}
}
//以下函数HuffmanCoding功能为:哈夫曼编码
void HuffmanCoding(HuffmanTree &HT,HuffmanCode *HC,wElem *w,int n)//w存放n字符及其权值(从0号单元开始),构造哈夫曼树HT,并求出n个字符的哈夫曼编码表HC.
{
int i,m,ww=0;
int s1,s2;
HuffmanTree p;//定义指针变量p
if(n<=1) return;
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//给哈夫曼树分配存储空间,0号单元未用
HT[0].parent=-1;HT[0].lchild=-1;HT[0].rchild=-1;HT[0].weight=0;
for(p=HT+1,i=1;i<=n;i++,p++,ww++)//初始化n个叶子结点(即 n个字符)
{
p->weight=w[ww].wt;
p->HTch=w[ww].ch;
p->parent=p->lchild=p->rchild=0;
}//跳出循环时i=n+1;
for(;i<=m;i++,++p)//初始化叶子结点之外的其它所有结点
{
p->weight=0;
p->HTch='O';
p->parent=p->lchild=p->rchild=0;
}
for(i=n+1;i<=m;i++)//建立哈夫曼树
{
Select(HT,i-1,s1,s2);//在HT数组的1至i-1个结点中选择parent为0且权值weight最小的两个结点,其序号分别为S1和S2;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
char*cd=new char[n];//分配编码的存储空间
cd[n-1]='\0';//编码结束符
int c,f,start;
for(i=1;i<=n;i++)//逐个字符求哈夫曼编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
HC[i].ch=w[i-1].ch;//复制字符
HC[i].hufCh=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
strcpy(HC[i].hufCh,&cd[start]);//从 cd复制编码(串)到HC
}
delete []cd;//释放空间
}
void EnCoding(HuffmanCode *HC,int hufnum)
{
ofstream ufileWrite("ToBeTran.txt",ios::out);
if(!ufileWrite)
{
cout<<"文件不能打开!";
}
cout<<endl<<"文件创建成功"<<endl;
cout<<"请连续不间断地输入待编码字符序列,以回车结束输入:";
cin.sync();//清理缓冲区以避免不必要的错误!
char buf=' ';
while(buf!='\n')
{
buf=getchar();
ufileWrite<<buf;
}
cout<<endl;
ufileWrite.close();
cout<<"++对文件进行编码,并将编码存于文件CodeFile.txt中++++++++++++++++++++++++++++++"<<endl<<endl;
ifstream ufileRead("ToBeTran.txt",ios::in);
ofstream codeWrite("CodeFile.txt",ios::out);
if(!ufileRead)
{
cout<<"待编码文件不能打开"<<endl;
exit(-1);
}
if(!codeWrite)
{
cout<<"CodeFile.txt不能打开!!!"<<endl;
exit(-1);
}
char charInbuf;
while(ufileRead.get(charInbuf))
{
for(int k=1;k<=hufnum;k++)
{
if(charInbuf==HC[k].ch)
{
codeWrite<<HC[k].hufCh;
break;
}
}
}
cout<<endl<<endl;
codeWrite.close();
}
//以下函数Decoding功能为:哈夫曼译码
void DeCoding(HuffmanTree HT,HuffmanCode *HC,char*CodeFile,int n)
{
ifstream fRead(CodeFile,ios::in);//需要进行译码的目标文件为CodeFile,该函数功能即为打开CodeFile用于Read;
ofstream fWrite("TextFile.txt",ios::out);//对CodeFile译码后,结果存入TextFile,该函数功能为 建一个TextFile用于Write;
char inbuf;//用来暂存每次从CodeFile中读出的字符"0"和"1""\0"""\n"
char *cd=new char[n];//储存字串的空间
int start=0;//译码开始标记
int p=2*n-1;//根下标
int iHC;//用于扫描HC的循环变量
while(fRead.get(inbuf))
{
if(inbuf=='0') //如果读入0则进入左子树
{
if(HT[p].lchild!=0)
{
cd[start++]=inbuf;
p=HT[p].lchild;
continue;
}
else
{
cd[start++]='\0';//子串结束符
for(iHC=1;iHC<=n;iHC++)
{
if(strcmp((HC[iHC].hufCh),cd)==0)//在哈夫曼编码表HC中查找得到的子串
{
fWrite<<HC[iHC].ch;//找到则把对应的字符写入TextFile.txt
break;
}
else
continue;
}
start=0; //为读下一个子串做准备;
cd[start++]=inbuf;
p=HT[2*n-1].lchild;//此时p指向根结点的左孩子;
}
}
else if(inbuf=='1')//读入1则进入右子树进行判断
{
if(HT[p].rchild!=0)
{
cd[start++]=inbuf;
p=HT[p].rchild;
continue;
}
else
{
cd[start++]='\0';//子串结束符
for(iHC=1;iHC<=n;iHC++)
{
if(strcmp(HC[iHC].hufCh,cd)==0)//在哈夫曼编码表HC中查找该子串
{
fWrite<<HC[iHC].ch;//找到则把对应的字符写入TextFile.txt
break;
}
else
continue;
}
start=0; //为读下一个子串做准备
cd[start++]=inbuf;
p=HT[2*n-1].rchild;//此时P指向根结点的右孩子0
}
}
else if(inbuf='\n')
continue;
}
//当读取了CodeFile中的最后一个字符后,跳出循环时,输出最后一个子串
cd[start]='\0';
for(iHC=1;iHC<=n;iHC++)
{
if(strcmp(HC[iHC].hufCh,cd)==0)
{
fWrite<<HC[iHC].ch;
break;
}
else
continue;
}
delete []cd;//释放空间
fRead.close();//关闭文件
fWrite.close();
}
//以函数功能为:向屏幕输出译码文件CodeFile.txt,以每行50个代码的格式输出
void Print(char* cfileName)
{
ifstream codeRead(cfileName,ios::in);
ofstream codeWrite("CodePrin",ios::out);
if(!codeRead)
{
cout<<"文件不能打开!!!"<<endl;
exit(-1);
}
if(!codeWrite)
{
cout<<"文件不能打开!!!"<<endl;
exit(-1);
}
char codeInbuf='0';
cout<<endl<<"待译码的文件为"<<endl;
codeWrite<<"待译码的文件为"<<endl;
int num=1;
while(codeRead.get(codeInbuf))
{
if(num<=50)
{
cout<<codeInbuf;
codeWrite<<codeInbuf;
num++;
}
else
{
cout<<endl;
codeWrite<<endl;
num=1;
}
}
cout<<endl;
cout<<"该文件存储在CodePrin.txt中"<<endl;
}
void PreorderVisit( HTNode T,HuffmanTree HT,int n )
{
// 先序遍历二叉树
ofstream fout( "TreePrint.txt",ios::app );
if( !fout ){ cout<<"文件“TreePrint.txt”存取失败!\n";exit(-1); }
if((T.parent!=-1)&&(T.lchild!=-1)&&(T.rchild!=-1))
{
cout<<setw(2*(2*(n+1)-T.parent))<<T.HTch<<endl<<endl; // 访问结点
fout<<setw(2*(2*(n+1)-T.parent))<<T.HTch<<endl<<endl;
PreorderVisit( HT[T.lchild],HT,n ); // 遍历左子树
PreorderVisit( HT[T.rchild],HT,n );// 遍历右子树
}
// fout.close();
}
void Treeprinting( HTNode T,HuffmanTree HT,int n )
{
//蒋已经在内存中的哈夫曼树以直观的方式显示在终端上，
//并将此形式的字符写入文件“TreePint”中
T.parent=2*n;
cout<<"建立的哈夫曼树如下:\n";
PreorderVisit( T,HT,n );
cout<<"文件“TreePint”建立成功!\n";
}
void main()
{
//以下为初始化字符集数组
cout<<"*************************************************************"<<endl;
cout<<"27个字符存放在文件CharFile.txt中,字符权值直接存放在数组w中"<<endl;
cout<<"*************************************************************"<<endl;
cout<<"字符及其对应权值为:"<<endl;
int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
wElem *hufW=new wElem[27];
ofstream charWrite("CharFile.txt",ios::out);
if(!charWrite) exit(-1);
charWrite.write(" ABCDEFGHIJKLMNOPQRSTUVWXYZ",27);
charWrite.close();
ifstream charRead("CharFile.txt",ios::in);
if(!charRead) exit(-1);
char inbuf;
int i=0;
while(charRead.get(inbuf))
{
hufW[i].ch=inbuf;
cout<<hufW[i].ch<<"*****>>";
hufW[i].wt=w[i];
cout<<hufW[i].wt<<endl;
i++;
}
charRead.close();
char c;
int hufnum=27;
HuffmanTree HT;
HuffmanCode *HC=(HuffmanCode*)malloc((hufnum+1)*sizeof(HuffmanCode));//分配n个字符编码的头指针向量
while(1)
{
cout<<"*****************************************************************************"<<endl;
cout<<"I----初始化,即建立哈夫曼树并将它存于文件hfmTree.txt中"<<endl;
cout<<"E----编码,对用户输入的文件的正文进行编码,然后将结果存入文件CodeFile.txt中"<<endl;
cout<<"D----译码,对文件CodeFile中的代码进行译码,结果存入文件TextFile.txt中"<<endl;
cout<<"P----印代码文件,将文件CodeFile.txt中的内容以每行50个代码显示在屏幕上"<<endl;
cout<<"T----印哈夫曼树,将哈夫曼树以直观的方式显示在屏幕上,并写入文件TreePrint.txt中"<<endl;
cout<<"Q----退出"<<endl;
cout<<"*****************************************************************************"<<endl<<endl;
cout<<"请按顺序选择要实现的功能<I,E,D,P,T>:";
cin>>c;
switch(c)
{
case'I':
{
cout<<"建立哈夫曼树,并把哈夫曼树存放在hfmTree.txt中"<<endl;
HuffmanCoding(HT,HC,hufW,hufnum);//建立哈夫曼树并且编码;
ofstream hufWrite("hfmTree.txt",ios::out);//把从终端读到的字符及权值以哈夫曼树的存储形式输出到文件hfmTree.txt中;
hufWrite << "++ 哈夫曼树 ++++++++++++++++++++++++++++" << endl << setw(9) << " 权值 " <<" 双亲 " << " 左孩子 " << " 右孩子 "<< endl;
for(int tOut=1;tOut<=2*hufnum-1;tOut++)
{
hufWrite<<setw(6)<<tOut<<setw(8)<<HT[tOut].weight<<setw(8)<<HT[tOut].parent<<setw(8)<<HT[tOut].lchild << setw( 8 ) << HT[ tOut ].rchild << endl;
}
hufWrite<<"---------------------------------------------------------------------";
hufWrite<<endl<<endl;
hufWrite.close();
//向屏幕输出哈夫曼编码,并把编码保存在文件hfmCode.txt中;
ofstream cdWrite("hfmCode.txt",ios::out);
if(!cdWrite)
{
cout<<"文件不能打开!!!!";
exit(-1);
}
cout<<"将字符编码后,编码为:"<<endl;
cout<<"字符 代码"<<endl;
for(int cOut=1;cOut<=hufnum;cOut++)
{
cout<<setw(6)<<HC[cOut].ch<<setw(15)<<HC[cOut].hufCh<<endl;
cdWrite<<setw(6)<<HC[cOut].ch<<setw(15)<<HC[cOut].hufCh<<endl;
}
cdWrite.close();
break;
}
case'E':
{
EnCoding(HC,hufnum);
break;
}
case'D':
{
cout<<"对CodeFile.txt中的代码进行译码 结果存在TextFile.txt中"<<endl;
DeCoding(HT,HC,"CodeFile.txt",hufnum);
//向屏幕输出译码后的内容;
cout<<"************译码***************"<<endl;
ifstream dcodeRead("TextFile.txt",ios::in);
char dcodeInbuf='0';
if(!dcodeRead)
{
cout<<"TextFile.txt文件不能打开!!"<<endl;
exit(-1);
}
cout<<endl;
while(dcodeRead.get(dcodeInbuf))
{
cout<<dcodeInbuf;
}
cout<<endl;
cout<<"译码存储在文件TextFile.txt 中";
break;
}
case'P':
{
Print("CodeFile.txt");
break;
}
case'T':
{
Treeprinting(HT[2*hufnum-1],HT,hufnum);
break;
}
case'Q':exit(-1);
default:exit(-1);
}
cout<<endl<<"************************************************"<<endl;
}
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -