hafuman.cpp

本程序有我和另两位同学完成

//哈夫曼编码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#include<math.h>
#define NULL 0
//结构体声明**********************************************
typedef struct huff_code_node   
{ //存储编码的链表
    char ch;						//编码对应的字符
    char code[100];				  //字符对应的哈夫曼码
    struct huff_code_node *next;    
}hnode,*huff;

typedef struct tree_Node	 
{//哈夫曼树结点
    char ch;					 //字符内容
    int amount;						//权值
    struct tree_Node *left,*right;		 //指向左子树与右子树
}tnode,*bt;

typedef struct list_node      
{  //链表结点
    char ch;						//存储字符串中的字符
    int amount;						 //字符权值
    tnode *son;							//链表结点带有二叉子树的根结点指针
    struct list_node *next;				  //指向链表中下一个结点
}Node,*L;

typedef struct stack_node
{
    char ch;					//单个字符
    int amount;				
    bt son;						//指向二叉树的某结点
    struct stack_node *next;
}snode,*stack;
//全局变量*******************************************
	char tmpstring[1000] ; //被多次用到，作用不同
	char rongqi[1000];
	char linshi;
	char *zifu;            //存储有待破解的编码
	bt tmptree;            //以上为解码变量 
	hnode difrnt_amount[100];//存储所有不同字符及其编码
	L l,p,q, new_node;			//链表结点
	huff hlist;						 //计算得到的编码表						
	int int_num;					//不同字符数
	int int_amount;				//所有字符数
	int code_sum;				 //哈夫曼编码总长
	char t[200],*str,*c;		   //str用于存放 要编译的字符串 ，整个程序中，其值不变
	bt root=NULL;				//哈夫曼树根结点
	int abc=0;                  //此变量只用于OpenCode函数，标记解码后的文件（字符串）长度
//**************函数声明************************
	void Manual();
	void AutoRead();
	void opencode(bt T );  
	void Search(char *str);

	void initial();
	void pull_in_list() ;
	int list_element_amount();
	void encoding();
	bt create();

	void Readtxt();
	void Savacode(char *codestr);
	void SavaData(hnode difrnt_amount[]);
	void SaveText();
	void ReadCode();
//***********************************************
void main()
{
 	system("color 24");
	system("mode con: cols=90 lines=130");
	int choice;
	int i=0;
while(1)
{
START:	
	printf("\n★★★★★★★★★★★★★★欢迎使用哈夫曼编译器1.0★★★★★★★★★★★★★★\n");
	printf("\n\n     1.手动操作                    2.文件操作                     3.退出\n");
	printf("\n请输入:");
	while(scanf("%d",&choice)!=1)
    {
      while(getchar()!='\n')
      continue;
      printf("输入错误,请重新输入!\n");
      printf("\n★★★★★★★★★★★★★★欢迎使用哈夫曼编译器1.0★★★★★★★★★★★★★★\n");
    }
	 switch (choice)
	 {
	 case 1:
		 Manual();
         break;
     case 2:
         AutoRead();
         break;
     case 3:
         exit(0);
         break;
      default:
         printf("输入错误,请重新输入!");
		 goto START;
	 }
}
		
}
void Manual()  //手动输入文件
{
	int i=0;
	initial();
	pull_in_list() ;
	int_num=list_element_amount() ;
	root=create();
	encoding();
	printf("\n");
	printf("编码为:");
	*tmpstring='\0';//全局变量置零
	Search(str);
	printf("\n");
	printf("请输入要破解的代码:\n");
	Savacode(tmpstring);//此处tmpstring存储的是编译好的哈夫曼编码
    tmptree=root;
	scanf("%c",&linshi);
	while(linshi!='#')
	{
		tmpstring[i]=linshi; //此处tmpstring存储的是输入的要破解的代码，转给zifu
		i++;
		scanf("%c",&linshi);
	}
	getchar();
	tmpstring[i]='\0';
	zifu=tmpstring;
	printf("\n");
	printf("译码为:");
	for(i=0;*zifu!='\0';i++)
		opencode(tmptree );
	SavaData(difrnt_amount);
}

void AutoRead()  //自动读取已经存在的哈夫曼码文件和要编译的字符文件
{
	int i=0;
	Readtxt(); //读取
	pull_in_list() ;
	int_num=list_element_amount() ;
	root=create();//建树
	encoding();
	printf("\n");
	printf("编码为:");
	*tmpstring='\0';//全局变量置零
	Search(str);  //编码
	Savacode(tmpstring); //保存编码
	tmptree=root;    //此处tmptree用于解码
	ReadCode();           //读码
	printf("\n");
	printf("译码为:");
	*rongqi='\0';//全局变量置零
	abc=0;
	for(i=0;*zifu!='\0';i++)
		opencode(tmptree);       //解码
	rongqi[abc]='\0';   //此处rongqi 存的是解出来的译码用于SaveText调用
	SavaData(difrnt_amount);
	SaveText();
}

void initial()        //初始化操作 
{
	int i=0;char tmp;
    l=(Node*)malloc(sizeof(Node));     
    l->ch='\0';
    l->amount=0;
    l->son=NULL;
    l->next=NULL;
    str=t;  
    printf("输入字符串进行哈夫曼编码:\n");
	getchar();
	scanf("%c",&tmp);
    while(tmp!='#'){str[i]=tmp;i++;scanf("%c",&tmp);}
    getchar();    
}

void pull_in_list()                
{
    int exist;		
    int n;				
    int m;				
    c=str;
    
    while(*c!='\0')        //若字符串未读完
    {
        exist=0;
        p=l;    
        while(p->next!=NULL)   
        {
            p=p->next;
            if(p->ch==*c)				//当前字符已经在链表中
            {
                exist=1;
                p->amount++;			
                break;
            }
        }

        if(exist==0)    //当前字符不存在于链表中
        {
            new_node=(Node*)malloc(sizeof(Node));
            new_node->ch=*c;
            new_node->amount=1;
            new_node->next=NULL;
            new_node->son=NULL;
            p->next=new_node;
            p=new_node;
        }
        c++;    //读下一个字符
    }

    printf("统计结果:\n");
    p=l;
    n=0;
    m=0;
    while(p->next!=NULL)
    {
        n++;
        p=p->next;
        m+=p->amount;
        printf("%c——%d\n",p->ch,p->amount);
    }
    int_num=n;
    int_amount=m;
    printf("一共有%d种字符输入，字符总数%d\n",int_num,int_amount);
}

int list_element_amount()      //计算链表中结点的数量（不包括头结点）
{
    L temp;       
    int n=0;        //结点数量
    temp=l;   //tmp指向表头l(字母)
    while(temp->next!=NULL)    
    {
        n++;
        temp=temp->next;
    }
    return n;
}

bt create()    //建立最优二叉树
{
    //这些变量用于寻找最小结点
    L min1_pos,min2_pos,t,min_pri;
    bt min1_son,min2_son;
    int min1,min2;
    char min1_c,min2_c;//这些变量用于构造二叉子树
    bt left,right,root;//这些变量用于将二叉子树信息插入链表
    L made,temp_p;
    while(list_element_amount()>=2)    //若表中还有两个或以上结点，则继续
    {
        //选择次数值最小的两个结点
        t=l->next;
        min1=t->amount;       
        min1_pos=t;           
        min1_c=t->ch;       
        min1_son=t->son;   
        min_pri=l;            //min_pri始终指向最小结点的前驱以便删除最小结点

        while(t->next!=NULL)
        {
            t=t->next;//跳出循环时t即min1指向空，最小结点删除
            if(min1>t->amount)   
            {
                min1=t->amount;        //将当前结点的次数值赋给min1
                min1_pos=t;           
                min1_c=t->ch;        //将当前结点的字符赋值给min1_c
                min1_son=t->son;   
            }
        }
        min_pri=l;
        while(min_pri->next!=min1_pos)
            min_pri=min_pri->next;
        min_pri->next=min1_pos->next;      
        //寻找第二个小结点
        t=l->next;
        min2=t->amount;        
        min2_pos=t;          
        min2_c=t->ch;
        min2_son=t->son;
        min_pri=l;        //min_pri始终指向最小结点的前驱

        while(t->next!=NULL)
        {
            t=t->next;
            if(min2>t->amount)