📄 新建 文本文档 (6).txt
字号:
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
using namespace std;
typedef struct{// 哈夫曼树和哈夫曼编码的存储表示
unsigned int weight;
unsigned int parent,lChild,rChild;
}HTNode, *HuffmanTree;// 用动态数组存储哈夫曼树
typedef struct{
char ch;
char* hufCh;
}HuffmanCode;//用动态数组存储哈夫曼编码表
typedef struct{// 权值字符结点
char ch;
int wt;
}wElem;// 动态分配数组存储读入字符与权值
void HuffmanCoding(HuffmanTree &,HuffmanCode *,wElem *,int);//构造哈夫曼树HT,并求哈夫曼编码，将结果存入hufTree.txt
void DeCoding(HuffmanTree,HuffmanCode *,const char*,const int);//对文件里的代码进行译码,将结果存入textfile.txt
void SelectTwoNode(HuffmanTree,int,int&,int&);//选择两个最小的结点
void HuffmanCoding(HuffmanTree &HT,HuffmanCode* HC,wElem* w,int n)//构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
{
if(n<=1)
return;
int m=2*n-1; // m为结点数目
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //未用0号单元
HuffmanTree p=HT;
p++; //p指向HT的第1号单元
int i=0,ww=0; //ww为wElem* w的下标
for(i=1;i<=n;i++,p++,ww++)
{
p->weight=w[ww].wt;
p->parent=p->lChild=p->rChild=0;
} //初始化
for(;i<=m;++i,++p)
{
p->weight=p->parent=p->lChild=p->rChild=0;
}
int s1=0,s2=0; //s1,s2为HT[1 .. i-1]中parent为0且weight最小的两个结点
for(i=n+1;i<=m;++i)
{
SelectTwoNode(HT,i-1,s1,s2);
HT[s1].parent=i; // 标记 parent
HT[s2].parent=i; // 标记 parent
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=0;
int f=0;
for(i=1;i<=n;++i) //开始编码
{
int 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; //释放空间
}
// -----------------------选择两个最小的结点,序号分别放在s1和s2中--------------------
void SelectTwoNode(HuffmanTree HT,int i,int &s1,int &s2)
{
unsigned int sm1,sm2;
s1=1; //从序号为1的权值开始
s2=1;
int m=0; //最小权值的序号临时变量
for(m=1;m<=i;m++) //第一遍中第一个parent为0的结点
{
if(HT[m].parent!=0)
continue;
else
{
sm1=HT[m].weight;
s1=m;
break;
}
}
for(int j=m+1;j<=i;j++) // 第一遍选第一个最小的
{
if(HT[j].parent!=0)
continue;
else
{
if(sm1>HT[j].weight)
{
sm1=HT[j].weight;
s1=j;
}
}
}
for(m=1;m<=i;m++) //第二遍中第一个parent为0的结点
{
if(HT[m].parent!=0)
continue;
else
{
sm2=HT[m].weight;
s2=m;
if(s2==s1)
continue;
else
break;
}
}
for(int k=m+1;k<=i;k++) //第二遍选第二个最小的
{
if(HT[k].parent!=0)
continue;
else
{
if((HT[k].weight<sm2)&&(k!=s1)) //保证sm1!=sm2
{
sm2=HT[k].weight;
s2=k;
}
}
}
}
//-------------------译码实现，在 HC 里进行逐字扫描比较求子串相应的字符--------------------------------------
void DeCoding(HuffmanTree HT,HuffmanCode *HC,const char* iFile,const int n)
{// 参数n为字符个数p=2*n-1就为HT的结点数目.HT[p]就为HT的根.
ifstream fIn(iFile,ios::in);
char inBuf='1';
ofstream fout("textfile.txt",ios::out);
char* cd=new char[n]; // 储存字串的空间
int start=0; //译码开始标记
int p=2*n-1; //根下标
int iHC=1; // 用于扫描 HC 的循环变
while(fIn.get(inBuf)) // 循环读入 \'0\' 或 \'1\' 或 \'\\n\'
{
if(inBuf=='0')
{
if(HT[p].lChild!=0)
{
cd[start++]=inBuf; //使inBuf进cd*
p=HT[p].lChild; //进入左子树
continue;
}
else
{
cd[start++] = '\0';
for(iHC=1;iHC<=n;iHC++) //寻找与子串匹配的字符
{
if(strcmp(HC[iHC].hufCh,cd)==0)
{
fout<<HC[iHC].ch;
break; //找到则跳出for循环
}
else
continue;
}
start=0;
cd[start++]=inBuf; //为读下一子串做准备
p=HT[2*n-1].lChild; //此时p指向root的leftchild
}
}
else
if(inBuf=='1')
{
if(HT[p].rChild!=0)
{
cd[start++]=inBuf; //让inBuf进入cd*
p=HT[p].rChild; //进入左子树
continue;
}
else
{
cd[start++]='\0'; //子串结束符
for(iHC=1;iHC<=n;iHC++) //寻找与子串匹配的字符
{
if(strcmp(HC[iHC].hufCh,cd)==0)
{
fout<<HC[iHC].ch;
break; // 找到则跳出for循环
}
else
{
continue;
}
}
start=0;
cd[start++]='1'; //准备读下一个子串
p=HT[2*n-1].rChild; //p指向root的rightchild
}
}
else
if(inBuf=='\n')
{
continue;
}
}
cd[start]='\0';
for(iHC=1;iHC<=n;iHC++) //寻找与子串匹配的字符
{
if(strcmp(HC[iHC].hufCh,cd)==0)
{
fout<<HC[iHC].ch;
break; //找到则跳出for循环
}
else
{
continue;
}
}
delete [] cd; //释放空间
fIn.close(); //关闭文件
fout.close(); //关闭文件
}
int main( )
{
char* wFileName=new char[128];
cout<<endl<<"请输入字符存放位置及文件名: ";
cin >> wFileName;
ifstream hufInPut(wFileName,ios::in );//用hufInPut打开外部文件
if(!hufInPut)
cerr << "文件不存在" << endl;
int hufNum=0;
hufInPut>>hufNum; //读入字符集大小n到hufNum
//-------------------输出基本信息--------------------------------
cout<<"字符总数: " << hufNum << endl;
cout<<" 字符 权值" << endl;
wElem* hufW=new wElem[hufNum]; //分配n个字符和n个权值的储存空间
for(int ii=0;ii<hufNum;ii++)
{
// ------------------循环读入字符及其对应的权值--------------------------
hufInPut >> hufW[ii].ch >> hufW[ii].wt;
cout << setw(4) << hufW[ii].ch << setw(8) << hufW[ii].wt << endl;
}
cout<<endl;
hufInPut.close(); //关闭存放字符和权值的文件
delete [] wFileName; //释放空间
HuffmanTree hufT;
HuffmanCode* hufC=(HuffmanCode* )malloc((hufNum+1)*sizeof(HuffmanCode)); //分配n个字符编码的头指针向量
HuffmanCoding(hufT,hufC,hufW,hufNum );//编码
// ------------------用hufTreeOutPut把哈夫曼树HT,HC输出到文件hufTree.txt中------------------------------------------
ofstream hufTreeOutPut( "hufTree.txt" , ios::out );
hufTreeOutPut << "++ 哈夫曼树 ++++++++++++++++++++++++++++" << endl << setw(9) << " 权值 " <<" 双亲 " << " 左孩子 " << " 右孩子 "<< endl;
for(int tOut=1;tOut<=2*hufNum-1;tOut++)
{
hufTreeOutPut<<setw(6)<<tOut<<setw(8)<<hufT[tOut].weight<<setw(8)<<hufT[tOut].parent<<setw(8)<<hufT[tOut].lChild << setw( 8 ) << hufT[ tOut ].rChild << endl;
}
hufTreeOutPut << "------------------------------------------ " << endl << endl << "++ 哈夫曼编码 +++++++++++++++++++++++++++ " << endl;
//-----------向屏幕输出编码过的编码基本信息----------------------------------------------------------------------
cout << "将字符编码后, 代码为: " <<endl;
cout << " 字符 代码" << endl;
for( int cOut=1;cOut<=hufNum;cOut++)
{
hufTreeOutPut << " " << hufC[cOut].ch<< " +++++>> "<<hufC[cOut].hufCh<<endl;
//-----------------向屏幕输出编码过的编码内容----------------------------------------------------------
cout<<setw(4)<<hufC[cOut].ch<<setw(8)<<hufC[cOut].hufCh<<endl;
}
cout<<"+++++++转换后的代码存储在文件<hufTree.txt>中+++++++ "<<endl;
cout<<endl<<endl;
hufTreeOutPut <<"++ 转换成功!++++++++++++++++++++" << endl;
hufTreeOutPut.close(); //输出完毕，关闭文件
delete [] hufW; //释放内存
//-------------------向屏幕输出编码过的代码内容-------------------------------------
char* cFileName=new char[128]; // 存放文件名的空间
cout << endl<< "请输入存储有代码的文件位置及名称: ";
cin >> cFileName;
ifstream codeIn(cFileName,ios::in );
if(!codeIn)
cerr << "file can not be opened" << endl;
char codeInBuf='0';
cout<<"\n待编译的代码为:\n---------------------------------------------"<<endl;
while( codeIn.get( codeInBuf ) )
cout << codeInBuf;
cout<<"\n---------------------------------------------";
cout << endl << endl;
DeCoding(hufT,hufC,cFileName,hufNum); //译码
//--------------- 向屏幕输出译码后的内容----------------------------------------------------
cout << "译码为: " << endl;
cout<<"---------------------------------------------\n";
ifstream dcodeIn("textfile.txt",ios::in);
if( !dcodeIn )
cerr <<"file can not be opened"<<endl;
char dcodeInBuf='0';
while( dcodeIn.get(dcodeInBuf))
cout <<dcodeInBuf;
cout<<endl;
cout<<"---------------------------------------------";
cout<<"\n********译码存储在文件textfile.txt中*******"<<endl;
cout << endl<<endl;
return 0;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -