lab2.cpp

haffman编码进行数据压缩,开发环境为visula studio

#include"stdafx.h"
#include <fstream>
 #include <iostream>
 #include <cstdlib>
 #include <string>
 
  using namespace std;
  

  
typedef struct Clist
{
       char ch;
       int times;
       Clist *next;
};
Clist *head,*one;
int number=0;//计数器，记录文件中字符个数 
  
 
typedef struct Tree//hafuman树，压缩规则为左0右1； 
{
        Clist *node;
        Tree *left;
        Tree *right;
}; 
Tree *root; //树的根节点
  
  
typedef struct Tlist//构造hafuman树的时候用到的辅助链表结构
{
	Tree *node;
	Tlist *next;
};
Tlist *tlist;


typedef struct Table//存储字符与编码影射的链表
{
	char content;//字符
	int data;//对应的编码
	Table *next;
};
Table *Thead;//该链表的头

  void yasuo(string input,string output);
  void jieya(string input,string output);
  void init(Clist *p);
  void display_list(Clist *p,int number);
  void display_list(Clist *p);
  void add_to_list(char ch);
  void sort();
  bool is_in_char(char c);
  void init_list();
  bool has_list();
  Tree* creat_tree();//创建哈夫曼树并返回根节点
  void remove_from_list(Clist *head);//从列表中删除前2个节点
  void add_to_list(Clist *list);//向列表中加入此节点，并按顺序插入指定位置
  void display_tree(Tree *root,string code);
  bool in_Tlist(Clist *q);
  Tree* get_tree_from_Tlist(Clist *q);
  void add_to_Tlist(Tree *tree3);
  void display_Tlist();
  void do_code(char letter,Tree *root,string code,ofstream &fout);//往输出文件输出编码
  void test(char letter,string output);//测试用函数

    
    
    
 int main()
 {
     char answer='x';
     string input,output;
     

     //printf("%c",answer);
     //getchar();
     while(answer=='x'||answer=='y')
     {
		 cout<<"****************************************************************\n";
		printf("想压缩文件还是解压缩？(x-压缩,y-解压缩,其他输入退出程序)\n");
		answer=getchar();
		getchar();
     
     if(answer=='x')
     {
          printf("请输入待压缩文件名称：");
          getline(cin,input);
          printf("请输入压缩后文件名称：");
          getline(cin,output);
          yasuo(input,output);
      }
      else if(answer=='y')
     {
          printf("请输入待解压文件名称：");
          getline(cin,input);
          printf("请输入解压后文件名称：");
          getline(cin,output);
          jieya(input,output);
      }
	 }
 }
 
 
 void yasuo(string input,string output)
 {
      char letter;
      ifstream fin,fin1;
      ofstream fout;
      fin.open(input.data());
      if(fin.fail())
     {
         cout<<"无法打开该待压缩文件！";
         getchar();
         exit(1);
     }
     fout.open(output.data());
     if(fout.fail())
     {
         cout<<"无法创建压缩后文件！";
         getchar();
         exit(1);
     }
     
	 while(fin.get(letter))
     {
		  number++;
		  //cout<<letter;
		  if(number==1)
		  {
			  head=new Clist;

			  head->ch=letter;
			  head->times=1;
			  head->next=NULL;

		  }
		  else
		  {
			  if(is_in_char(letter)){}
			  else
			  {
				 add_to_list(letter);
			  }
		  }
     }
	 fin.close();
    // cout<<"@@@@@@@@";
	 //getchar();
     sort();
     
	 //cout<<"%";
	 //getchar();
	 cout<<"各字符的概率为:\n";
	 display_list(head,number);
	 //display_list(head);
	 root=creat_tree();
	 //display_list(head);
	 //display_Tlist();
	 getchar();
     
	 //getchar();
	 cout<<"编码结果为:\n";
	 display_tree(root,"");
	 //getchar();
      fin1.open(input.data());
      if(fin1.fail())
     {
         cout<<"无法打开该待压缩文件！";
         getchar();

         exit(1);
     }
	  while(fin1.get(letter))
	  {
		  
		  //test(letter,output);
		  do_code(letter,root,"",fout);
	  }
	  cout<<"压缩完毕!\n";
	  fin1.close();
	  fout.close();
  }
  
   
   void init(Clist *p)
   {
	    p=new Clist;
        p->ch='@';
        p->times=0;
        p->next=NULL;
    }
   
   
   
   bool is_in_char(char c)
   {
        Clist *p;
		for(p=head;p!=NULL;p=p->next)
        {
            if(p->ch==c) 
            {
                         p->times++;
                         return true;
            }
        }

        return false;
    }
    
    void add_to_list(char ch)
    {
         Clist *q,*p;
		 p=new Clist;
		 p->ch=ch;
		 p->times=1;
		 p->next=NULL;
         //init(p);
		 for(q=head;q->next!=NULL;q=q->next)
         {
         }
         q->next=p;
     }
     
     void sort()
     {
          Clist *p,*q;
          char c;
          int t;
          p=head;
          q=p->next;
          for(;p!=NULL;p=p->next)
          {
			  for(q=p->next;q!=NULL;q=q->next)
                {
                      if(p->times>q->times)
                      {
                            c=q->ch;
                            t=q->times;
                            q->ch=p->ch;
                            q->times=p->times;
                            p->ch=c;
                            p->times=t;
                      }                   
                }
          }
      }
      
      
 void display_list(Clist *p,int number)
 {
	 for(;p!=NULL;p=p->next)
      cout<<p->ch<<"-"<<(double)p->times/number<<"\n";
  }
 
 void display_list(Clist *p)
 {
	 for(;p!=NULL;p=p->next)
      cout<<p->ch<<"-"<<p->times<<"\n";
  }

 bool has_list()
 {
	 if(head->next==NULL)return false;
	 else return true;
 }

 
Tree* creat_tree()
{
	Tree *tree1,*tree2,*tree3,*t;
	Clist *q,*c;
	 
    q=head;
	for(;head!=NULL&&head->next!=NULL;head=head->next->next)
	{
		/*tree1=new Tree;
	    tree2=new Tree;
	    tree3=new Tree;
		t=tree3;
	    list=new Clist;
		tree1->node=q;
		tree1->left=NULL;
		tree1->right=NULL;
		tree2->node=q->next;
		tree2->left=NULL;
		tree2->right=NULL;
		list->ch='@';
		list->times=q->times+q->next->times;
		list->next=NULL;
		tree3->node=list;
		tree3->left=tree1;
		tree3->right=tree2;
		remove_from_list(head);
		add_to_list(list);*/
		if(q->next==NULL)
		{
            
		}
		else
		{
			if(in_Tlist(head)) tree1=get_tree_from_Tlist(head);
			else
			{
				tree1=new Tree;
				tree1->node=head;
				tree1->left=NULL;
				tree1->right=NULL;
			}
			if(in_Tlist(head->next)) tree2=get_tree_from_Tlist(head->next);
			else
			{
				tree2=new Tree;
				tree2->node=head->next;
				tree2->left=NULL;
				tree2->right=NULL;
			}
			
			tree3=new Tree;
			c=new Clist;
			c->ch='@';
			c->times=head->times+head->next->times;
			c->next=NULL;
			tree3->node=c;
			tree3->left=tree1;
			tree3->right=tree2;
			add_to_Tlist(tree3);
			add_to_list(c);
		}
	}
	head=q;
	return tlist->node;
}

void remove_from_list(Clist *head)
{
	head=head->next->next;
}
void add_to_list(Clist *list)
{
	int n;
	Clist *q,*p;
	n=list->times;
	p=head;
	if(n<head->times)
	{
		list->next=head->next;
		head->next=list;
	}
	else
	{
		for(q=head->next;q!=NULL&&n<q->times;q=q->next)
		{
			p=p->next;
		}
		//list->next=q;
		//p->next=list;
		list->next=q->next;
		q->next=list;
	}
}


void display_tree(Tree *root,string code)
{
	//string code;
	Tree *t;
	t=root;
	if(t!=NULL)
	{
		if(t->node->ch!='@')
		{
		cout<<t->node->ch<<code<<"\n";
		}
		display_tree(t->left,code+"0");
		display_tree(t->right,code+"1");

	}
}

bool in_Tlist(Clist *q)
{
	Tlist *t;
	for(t=tlist;t!=NULL;t=t->next)
	{
		if(t->node->node->ch==q->ch&&t->node->node->times==q->times) return true;
	}
	return false;
}

Tree* get_tree_from_Tlist(Clist *q)
{
	Tlist *t;
	for(t=tlist;t!=NULL;t=t->next)
	{
		if(t->node->node->ch==q->ch&&t->node->node->times==q->times) return t->node;
	}
	return NULL;
}

void add_to_Tlist(Tree *tree)
{
	Tlist *t,*l;
	if(tlist==NULL)
	{
		tlist=new Tlist;
		tlist->node=tree;
		tlist->next=NULL;
	}
	else
	{
        t=new Tlist;
		l=tlist;
		t->node=tree;
		t->next=l;
		tlist=t;
	}
}


void display_Tlist()
{
	Tlist *t;
	for(t=tlist;t!=NULL;t=t->next)
		cout<<t->node->node->ch<<t->node->node->times<<"\n";
}


void do_code(char letter,Tree *root,string code,ofstream &fout)
{
	Tree *t;
	t=root;
	if(t!=NULL)
	{
		if(letter==t->node->ch) 
		{
			fout<<code;
		}
		else
		{
			do_code(letter,t->left,code+"0",fout);
			do_code(letter,t->right,code+"1",fout);
		}		
	}
}

 void test(char letter,string output)
 {
	 
	 ofstream fout;
	 fout.open(output.data(),ios::app);
	 //fout.open(output.data(),std::istringstream);
     if(fout.fail())
     {
         cout<<"无法创建压缩后文件！";
         getchar();
         exit(1);
     }
	 fout<<letter;
	 fout.close();
 }





void jieya(string input,string output)
{
      char letter;
	  Tree *t;
	  //bool flage=false;//标记变量，作为初始化列表的参数
      //Clist *p;
      ifstream fin;
      ofstream fout;
	  t=root;
      fin.open(input.data());
      if(fin.fail())
     {
         cout<<"无法打开该待压缩文件！";
         getchar();
         exit(1);
     }
     fout.open(output.data());
     if(fout.fail())
     {
         cout<<"无法创建压缩后文件！";
         getchar();
         exit(1);
     }
     
     while(!fin.eof())
     {
          fin.get(letter);
		 /* if(t->node->ch!='@')
		  {
			  fout<<t->node->ch;
			  t=root;
		  }
		  else
		  {
			  if(letter=='0') t=t->left;
			  else t=t->right;
		  }*/
		  if(letter=='0')
		  {
			  if(t->node->ch!='@')
			  {
				  fout<<t->node->ch;
				  t=root;
			  }
			  t=t->left;
		  }
		  else
		  {
			  if(t->node->ch!='@')
			  {
				  fout<<t->node->ch;
				  t=root;
			  }
			  t=t->right;
		  }
     }
	 cout<<"解压完毕！\n";
}