//课程设计哈夫曼树文件的压缩#include<iostream>#include<fstream>#include<string>#include<iomanip>#include"stdio.h"using namespace std;string remfile[6000];//存放原文件字符的数组；int remcount=0;//记录元素个数；float  bitecount=0;//记录二进制码的个数；/****************************************************************/struct huffchar{//存放读入字符的类； int count;//字符出现的个数；    char data;//字符；};int count=1;//记录huff数组中字符实际出现的个数； huffchar huff[1000];//类的对象；   /****************************************************************//*文件读入部分和统计字符出现的频率*/bool char_judge(char c)//判断字符出现的函数；{  for(int i=1;i<=count;i++)   if(huff[i].data==c){huff[i].count++;return true;}//如果出现过，出现的频数加1；   return false; } void char_add(char c)//添加新出现的字符；{ huff[count].data=c; huff[count++].count++;//个数增加，}   //文件的读取void read_file_count(){ char c; ifstream infile; infile.open("huffman.txt");//打开huffman.txt文件；  if(!infile)//检查文件是否打开。 {  cerr<<"不能打开 huffman.txt文件";//输出文件未打开的标志。  exit(0); }  cout<<"读入的文件中的内容为："<<endl; while((c=infile.get())!=EOF) {   remfile[++remcount]=c; if(!char_judge(c))  char_add(c); } cout<<endl;} /******************文件读入和统计字符出现频率部分结束**************/ /******************************************************************/ /******************构造huffman树程序部分***************************/struct huff_tree{//huffman树结点定义； int parent; int lchild; int rchild; int weight; };  int sum;//huffman树中结点的个数； huff_tree huffman[1000];void creathuffman()//构造huffman树的函数{  int min1,min2;//指示权值最小； int loc1,loc2;//指向权值最小的两个数的位置；  for(int i=1;i<=sum;i++) {   //对huffman树的结点进行初始化；  huffman[i].parent=0;  huffman[i].lchild=0;  huffman[i].rchild=0;  huffman[i].weight=0;    } for(int ii=1;ii<count;ii++)//将权值赋给huffman[].weight; huffman[ii].weight=huff[ii].count; sum=2*count-3;  for(int j=count;j<=sum;j++){ loc1=loc2=0;//权值最小的    min1=min2=20000;     for(int k=1;k<=j-1;k++)//求权值最小的两个地址；  if(huffman[k].parent==0)   if(huffman[k].weight<=min1)   {    min2=min1;min1=huffman[k].weight;                loc2=loc1;loc1=k;   }   else    if(huffman[k].weight<=min2)    {min2=huffman[k].weight;loc2=k;}////////////将求出的两个权值最小的结点合并为新的结点，并将新的结点存入数组中         huffman[loc1].parent=j;   huffman[loc2].parent=j;   huffman[j].lchild=loc1;   huffman[j].rchild=loc2;   huffman[j].weight=huffman[loc1].weight+huffman[loc2].weight;     }   } /*******************************构造huffman树的程序部分结束********************************/ /*************************************huffman编码开始**************************************/  struct huffcode{//译码结构体 string bits[100];//存放解码； int start;// int count; string c;//存放字符；};huffcode hcode[100];void huffmancode()//编码函数{  int rem,p;int count1=0;    for(int y=1;y<=count;y++) {//编码部分；  rem=y;  hcode[y].start=sum;        hcode[y].c=huff[y].data;  p=huffman[y].parent;  while(p!=0)  {   if(huffman[p].lchild==rem)hcode[y].bits[++count1]='0';    else   hcode[y].bits[++count1]='1';  rem=p;   p=huffman[p].parent;  }  hcode[y].count=count1;  count1=0; } for(int t=1;t<=count;t++)//输出所编的码；{ cout<<"字符"<<hcode[t].c<<"；编码：  "; int r=hcode[t].count;while(r)cout<<hcode[t].bits[r--];cout<<endl;} } /************************************************************************************/ string str;void code_huffman_file(){    ofstream fp;  cout<<"请输入文件名"<<endl<<"例如：huffman1.txt"<<endl;    cout<<"该文件用来存放编码后的文件即压缩文件"<<endl; cin>>str;  fp.open(str.c_str()); if(!fp)//检查文件是否打开。 {  cerr<<"不能打开 "<<str<<"文件"<<endl;//输出文件未打开的标志。  exit(0); } for(int j=1;j<=remcount;j++) {  for(int i=1;i<=count;i++)          if(remfile[j]==hcode[i].c)    {     for(int k=hcode[i].count;k>0;k--)     {fp<<hcode[i].bits[k];bitecount++;}              break;    } } fp.close();} /****************************编码并将编码存入文件部分结束*************************/   /////////////////////////////////////////////////////////////////////////////////   void code_file_out()//将编码过的文件恢复；   { ifstream fp1;//编码文件；    ofstream fp2;//解压缩文件； fp1.open(str.c_str());    if(!fp1)//检查文件是否打开。 {  cerr<<"不能打开 "<<str<<"文件"<<endl;//输出文件未打开的标志。  exit(0); }    char inchar; cout<<"请输入文件名"<<endl<<"例如：huffman2.txt"<<endl;    cout<<"该文件存放解压缩后的文件"<<endl; string s1; cin>>s1;  fp2.open(s1.c_str()); if(!fp2)//检查文件是否打开。 {  cerr<<"不能打开"<<s1<<"文件"<<endl;//输出文件未打开的标志。  exit(0); }    for(int ptr=sum;!fp1.eof();)//将编码转为字符输入的到文件中；  {      fp1>>inchar;  if(inchar=='1')ptr=huffman[ptr].rchild;//查找相应编码对应huffman树中的位置，  else ptr=huffman[ptr].lchild;     if(huffman[ptr].lchild==0&&huffman[ptr].lchild==0)//判断是否为叶子结点；  {fp2<<huff[ptr].data;ptr=sum;}//是叶子结点，将该结点的对应字符输入到文件中；  }  cout<<endl<<"                请检查原文件"<<"huffman.txt"<<"与解压缩文件"<<s1<<endl<<endl<<endl;  cout<<"*********************************请检查*****************************"<<endl;}           /*************************解压缩文件部分结束**************************************/        void evaluating(){  float y1; y1=bitecount/8/remcount*100; cout<<"压缩比例是："<<y1<<"%"<<endl;}     void main(){ cout<<"          *******************************************************"<<endl; cout<<"          *                 数据结构课程设计                    *"<<endl; cout<<"          *                 Huffman树文件压缩                   *"<<endl; cout<<"          *                      ****                         *"<<endl; cout<<"          *                  *********                       *"<<endl; cout<<"          *******************************************************"<<endl; system("pause"); read_file_count(); creathuffman();  huffmancode(); code_huffman_file(); code_file_out(); evaluating(); cout<<endl<<endl<<"                      文件的压缩与解压缩完成"<<endl;  system("pause");}

评论