#include"stdafx.h"#include"stdio.h"#include"conio.h"#include<iostream>#include<string>#include<fstream>using namespace std;#define maxbit 100#define Maxvalue 2000//最大权值整数常量#define Maxleaf 100//最大叶子结点数#define size 300//0、串数组的长度static int n;//实际的叶子结点数struct HNodeType{int weight;int parent;int lchild;int rchild;int ceng;//结点相应的层数char ch;//各结点对应的字符};struct HCodeType{int bit[maxbit];//存放编码的数组int start;//编码在数组中的开始位置};static HNodeType *HuffNode;//定义静态指针HNodeType *init()//初始化静态链表{HuffNode=new HNodeType[2*n-1];for(int i=0;i<2*n-1;i++){HuffNode[i].weight=0;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;HuffNode[i].ceng=-1;HuffNode[i].ch='0';}return HuffNode;}void HaffmanTree()//建立哈夫曼树{int i,j;int m1,m2,x1,x2;cout<<"请输入叶子结点对应的权值"<<endl;for(i=0;i<n;i++){cin>>HuffNode[i].weight;}flushall();//清除缓存cout<<"请输入叶子结点对应的字符"<<endl;for(i=0;i<n;i++){cin.get(HuffNode[i].ch);}for(i=0;i<n-1;i++){m1=m2=Maxvalue;x1=x2=0;for(j=0;j<n+i;j++){if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1)//找最小值{m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].parent==-1&&HuffNode[j].weight<m2)//找次小值{m2=HuffNode[j].weight;x2=j;}}HuffNode[x1].parent=n+i;//在相应的位置重新赋值HuffNode[x2].parent=n+i;HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;HuffNode[x1].ceng=n-i;HuffNode[x2].ceng=n-i;HuffNode[n+i].ceng=n-i-1;}ofstream outfile("hfmtree.dat",ios::out|ios::binary);//建立文件存入哈夫曼树if(!outfile)cerr<<"open file error!"<<endl;for(i=0;i<2*n-1;i++)outfile.write((char*)(&HuffNode[i]),sizeof(HuffNode[i]));outfile.close();}void HaffmanCode()//哈夫曼编码{int i,j,k,m,c,p,flag=0;HCodeType HuffCode[Maxleaf],cd;ifstream infile("hfmtree.dat",ios::in|ios::binary);//打开文件读取数据if(!infile)cerr<<"open file error!"<<endl;for( i=0;i<2*n-1;i++){infile.read((char*)(&HuffNode[i]),sizeof(HuffNode[i]));}infile.close();for(i=0;i<n;i++)//编码过程{cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1){if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HuffNode[c].parent;}for(j=cd.start+1;j<n;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}cout<<"叶子结点所对应的字符及编码（形如：A--100):"<<endl;for(i=0;i<n;i++){cout<<HuffNode[i].ch<<"--";for(j=HuffCode[i].start+1;j<n;j++)cout<<HuffCode[i].bit[j];cout<<endl;}ofstream outfile("codefile.dat",ios::out|ios::binary);//存取字符串的编码结果if(!outfile)cerr<<"open file error!"<<endl;cout<<"请输入需要编码的字符串："<<endl;flushall();string s;getline(cin,s);for(k=0;k<=s.length();k++)//进行字符匹配，输出对应的、串{for(j=0;j<n;j++){if(HuffNode[j].ch==s[k])for(m=HuffCode[j].start+1;m<n;m++){flag=1;outfile.write((char*)(&HuffCode[j].bit[m]),sizeof(HuffCode[j].bit[m]));cout<<HuffCode[j].bit[m];}}if(j==n&&flag==0)cout<<"该字符不存在，无法进行编码！";cout<<" ";}outfile.close();cout<<endl;}void Haffmantran()//哈夫曼译码{int i,j,top=-1,m,p;char c[size];cout<<"请输入需要编译的0和1代码串（以字符‘s'作为结束标志）："<<endl;do//输入并存取需要编译的代码串{top++;cin>>c[top];while(c[top]!='0'&&c[top]!='1'&&c[top]!='s'){cout<<"输入错误！只能输入'0','1','s'三个字符！"<<endl;cin>>c[top];}}while(c[top]!='s');m=2*n-2;i=0;cout<<"译码结果如下："<<endl;for(j=0;j<top;j++)cout<<c[j];cout<<"--";ofstream outfile("textfile.dat",ios::out|ios::binary);//建立文件存取译码结果if(!outfile)cerr<<"open file error!"<<endl;while(i!=top){while(HuffNode[m].lchild!=-1&&HuffNode[m].rchild!=-1){if(c[i]=='0')p=HuffNode[m].lchild;elseif(c[i]=='1')p=HuffNode[m].rchild;m=p;i++;if(HuffNode[m].lchild!=-1&&HuffNode[m].rchild!=-1&&i==top){cout<<"根据编码规则只能部分译码，无法完整译码！"<<endl;break;}}if(HuffNode[m].lchild==-1&&HuffNode[m].rchild==-1){cout<<HuffNode[m].ch;outfile.write((char*)(&HuffNode[m].ch),sizeof(HuffNode[m].ch));//将译码结果存入文件}m=2*n-2;}cout<<endl;outfile.close();}void Haffmanprint()//以凹入图的形式输出哈夫曼树{int i,j,k;fstream infile,outfile;//读取哈弗曼树infile.open ("hfmTree.dat",ios::in|ios::binary);if(!infile)cout<<"hfmTree.txt文件不能打开"<<endl;for( i=0;infile.peek() != EOF;i++) //将文件中的数据读到相应的数组内{infile.read ((char*)&HuffNode[i],sizeof(HuffNode[i]));}infile.close ();//关闭文件cout<<"输出哈弗曼树的凹入图（重组的结点只有权值没有字符）"<<endl;for(i=0;i<n;i++)for(j=0;j<2*n-1;j++)//按层次查找遍历{if(HuffNode[j].ceng==i+1){for(k=0;k<HuffNode[j].ceng;k++){cout<<" ";}for(k=0;k<60-HuffNode[j].ceng-i;k++){cout<<"*";}cout<<"("<<HuffNode[j].weight<<")";if(j<n)cout<<HuffNode[j].ch;cout<<endl;}}}void showmain(){cout<<"********************主菜单********************"<<endl;cout<<"**************0.选择退出该程序**************"<<endl;cout<<"**************1.实现哈夫曼编码**************"<<endl;cout<<"**************2.实现哈夫曼译码**************"<<endl;cout<<"**************3.要打印哈夫曼树**************"<<endl;}int _tmain(int argc, _TCHAR* argv[]){char c;cout<<"********************开始建立哈夫曼树！********************"<<endl;cout<<"请输入叶子结点的个数(最大为）："<<endl;cin>>n;while(n>100){cout<<"请重新输入叶子结点的个数(最大为）："<<endl;cin>>n;}HuffNode=init();HaffmanTree();showmain();do{c=getche();cout<<endl;if(c=='1')HaffmanCode();elseif(c=='2')Haffmantran();elseif(c=='3')Haffmanprint();elseif(c=='0')break;showmain();}while(c!='0');return 0;}。