哈夫曼编码

心已赠人 2022-06-18 12:16 185阅读 0赞

### 哈夫曼编码（还有对应的实验报告，在我的上传资源里，可以免费下载））    ###

### ![Image 1][]**1.设计内容** ###

1.添加用户登录密码

2.建立哈夫曼树：读入文件(\*.souce)，统计文件中字符出现的频度，并以这些字符的频度作为权值，建立哈夫曼树。

3.编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码，然后输出编码结果，并存入文件(\*.code)中。

4.译码：利用已建立好的哈夫曼树将文件(\*.code)中的代码进行译码，并输出译码结果，并存入文件(\*.decode)中。

### **2．各个模块详细的功能描述。** ###

1.登录：输入初始密码登录进入菜单页面，三次输错密码后自动退出系统。

2.初始化源文件：通过键盘录入要进行压缩的内容，并将输入的内容保存到hfm.souce文件当中。

3.查询字符的编码：统计hfm.souce中不同字符出现的频度，赋予每个字符不同权重，根据权重建立哈夫曼树，然后输出每个字符对应的哈夫曼编码。

4.打印哈弗曼树：依次按照字符，权重，左子树，右子树，双亲打印哈夫曼树。

5.查询编码后文件：从hfm.souce中读出源文件内容，利用建立好的哈夫曼树将该内容进行编码，并保存到hfm.code文件中，输出编码后内容。

6.查询译码后文件：从hfm.code  文件中读出编码后内容，利用哈夫曼树进行译码，将译码后的文件保存到hfm.decode文件中，并输出译码后文件。

7.退出：退出系统

#include<stdio.h>
    #include<stdlib.h>
    #include<conio.h>
    #include<windows.h>
    #include <graphics.h>
    #pragma comment (lib,"Winmm.lib")
    #define N 26
    #define M 2*N-1
    #define MAX 10000
    #define MAXSIZE 100
    menu();
    typedef struct
    {
    	char ch;
    	int weight,rchild,lchild,parent;
    }hfm;
    typedef struct
    {
     char bits[N];   //位串
     int start;      //编码在位串中的起始位置
     char ch;        //字符
    }codetype;
    typedef struct
    {
     char ch;   
     int  weight;     
    }weighttype;
    read_in_f1(weighttype weight[N])
    {
    	int i,j,k=0,n=0,m;;
    	char ch,cd[MAX];//cd[MAX]缓冲数组
        FILE *fp;
    		
        if((fp=fopen("hfm.souce","r"))==NULL) 
        {
            printf("not open");
            exit(0);
        }
        while ((ch=fgetc(fp))!=EOF)
    		cd[n++]=ch;
    	for(i=0;i<n;i++)
    	{	m=0;
    		if(cd[i]=='$') continue; 
    		weight[k].ch=cd[i];
    		for(j=i;j<n;j++)
    		{	
    			if(cd[j]==weight[k].ch)
    			{		
    				m++;
    				cd[j]='$';				
    			}
    		}
    		weight[k].weight=m;
    		k++;
    	}
        fclose(fp);
    
    }
    void create_hfm(hfm HFM[],weighttype weight[N])
    {
    	char c;
    	int i,j,f,p1,p2,s1,s2;//p1,p2为最小和次小节点的下标,s1,s2为最小和次小节点的权重
    	for(i=0;i<M;i++)
    	{
    		HFM[i].weight=0;
    		HFM[i].rchild=-1;
    		HFM[i].lchild=-1;
    		HFM[i].parent=0;
    		HFM[i].ch='^';
    	}
    	for(i=0;i<N;i++)
    	{
    		if(weight[i].weight!=0)
    		{
    			HFM[i].ch=weight[i].ch;
                HFM[i].weight=weight[i].weight;
    		}
    	}
    	for(i=N;i<M;i++)
    	{
    		p1=0;p2=0;		s1=s2=MAX;	
    		for(j=0;j<i;j++)
    		{
    			if(HFM[j].parent==0)
    			if(HFM[j].weight<s1)      //找权重最小的节点
    			{
    				s1=HFM[j].weight;	
    				p1=j;
    			}
    	        else if(HFM[j].weight<s2) 
    			{
    				s2=HFM[j].weight;
    				p2=j;                //找权重次小的节点
    			}
    		}
    		HFM[i].weight=HFM[p1].weight+HFM[p2].weight;   //赋新结点权重
    		HFM[i].lchild=p1;       HFM[i].rchild=p2;      //赋新结点左右孩子指针	
    		HFM[p1].parent=i;   	HFM[p2].parent=i;      //改变最小节点和次小节点的双亲指针
    	
    	}
    
    }
    void hfmcode(codetype code[],hfm HFM[])//根据哈夫曼树求出哈夫曼编码
    {
    	int i,j,c,p;
        codetype cd;  //缓冲变量
    	char ch;
        FILE *fp1,*fp2;
        for(i=0;i<N;i++)
    	{
    		cd.start=N;
            cd.ch=HFM[i].ch;
            c=i;               //从叶结点出发向上回溯
            p=HFM[i].parent;   //HFM[p]是HFM[i]的双亲
    		while(p!=0)
    		{
    			cd.start--;
    			if(HFM[p].lchild==c) 		cd.bits[cd.start]='0';   //HFM[i]是左子树，生成代码'0'
                else                        cd.bits[cd.start]='1';   //HFM[i]是右子树，生成代码'1'
    			c=p;
                p=HFM[p].parent;
    		}
    		code[i]=cd;      //第i+1个字符的编码存入code[i]
    	}
    	printf("输出每个字符的哈夫曼编码:\n");
    	for(i=0;i<N;i++)
    	{
    		if(HFM[i].weight!=0)
    		{
    			printf("%c: ",code[i].ch);
    			for(j=code[i].start;j<N;j++)
    			{
    				printf("%c ",code[i].bits[j]);
    			}
    			printf("\n");
    		}
    	}
        if((fp1=fopen("hfm.souce","r"))==NULL) 
        {
            printf("not open");   exit(0);  
        }
    	if((fp2=fopen("hfm.code","wt"))==NULL)
    	{
    		printf("写文件出错！！按任意键退出。");
    		getch();	exit(0);	   		
    	}
        while ((ch=fgetc(fp1))!=EOF)
    	{
    	  for(i=0;i<N;i++)
    	  {
    		if(ch==code[i].ch)
    		{
    			for(j=code[i].start;j<N;j++)
    			{					
    				fprintf(fp2, "%c",code[i].bits[j] ); //向所建文件写一字符串//	printf("%c ",code[i].bits[j]);	                 		  
    			}
    		}		
    	  }
    	}
    	fprintf(fp2, "%d",2);
    	printf("保存成功！！请按任意键继续。\n");
        fclose(fp2);            
        fclose(fp1);
    		printf("按任意键返回主菜单！！！");
        getch();
    	menu();
    }
    void decode(hfm HFM[M])   //依次读入电文，根据哈夫曼树译码
    {
    	int i,j=0,s,g=0;
    	FILE *fp1,*fp2;
        char b[MAX];     
        i=M-1;               //从根结点开始往下搜索
    	if((fp1=fopen("hfm.code","r"))==NULL)
    	{
    		printf("读文件出错！！按任意键退出。");
    	    getch(); 	exit(0);	  		
    	}
    	if((fp2=fopen("hfm.decode","wt"))==NULL)
    	{
    		printf("xie文件出错！！按任意键退出。");
    		getch();  exit(0);	  		
    	}
    	while ((s=fgetc(fp1))!=EOF)
    	{
    		b[g++]=s;
    	}
        printf("译码后的字符为：\n");
        while(b[j]!='2')
    	{	
    		if(b[j]=='0')
    			i=HFM[i].lchild;   //走向左孩子
            else
    			i=HFM[i].rchild;   //走向右孩子
    		if(HFM[i].lchild==-1)  //tree[i]是叶结点
    		{
    			fprintf(fp2, "%c",HFM[i].ch);
    			printf("%c",HFM[i].ch);
                i=M-1;            //回到根结点
    		}
    		j++;
    	}
    	printf("保存成功！！请按任意键继续。\n");
    	fclose(fp2);
    	fclose(fp1);
    	printf("按任意键返回主菜单！！！");
        getch();
    	menu();
    }
    save_in_f1()//创建文件
    {
    	char ch;
    	FILE *fp;
    	if((fp=fopen("hfm.souce","wt"))==NULL)
    	{
    		printf("写文件出错！！按任意键退出。");
    		getch();	exit(0);	
    	}
    		printf("请输入原始文档(以^结束)：\n");
    	while(ch!='^')
    	{
    		ch=getchar();
    
    		fputc(ch,fp); //向所建文件写一字符串  
    	}
    	    printf("保存成功！！请按任意键继续。\n");
    	    fclose(fp);
    	    	printf("按任意键返回主菜单！！！");
        getch();
    	menu();	
    }
    	print(hfm HFM[MAX])
    	{
    		int i;
    		printf("字符\t权重\t左子树\t右子树\t双亲\n");
    	    for(i=1;i<M;i++)
    		{
    		   //if(HFM[i].ch=='^') continue;
    		     printf("%c\t%d\t%d\t%d\t%d\n",HFM[i].ch,HFM[i].weight,HFM[i].lchild,HFM[i].rchild,HFM[i].parent);
    		}
    			printf("按任意键返回主菜单！！！");
        getch();
    	menu();
    	}
    
    
    printcode()
    {
    	FILE *fp;
    	char ch;
    	if((fp=fopen("hfm.code","r"))==NULL)
    	{
    		printf("读文件出错！！按任意键退出。");
    		getch();	exit(0);	   		
    	}
        while ((ch=fgetc(fp))!=EOF)
    	{ 
    		if((ch-48)==2) break;
    	  printf("%d",ch-48);
    	
    	}	
        fclose(fp);	
    		printf("按任意键返回主菜单！！！");
        getch();
    	menu();
    }
    menu()
    {
    
    	system("cls");
     system("color 03" );
        puts("                                                                                        ");
        puts("                                                  ☆ hafuman编码☆        ");
        puts("                                   ═══════════════════════");
        puts("                         ╔═══════════════════════════════╗"); 
        puts("                         ║                     ※1. 初始化源文件                        ║");
        puts("                         ║                                                              ║");
        puts("                         ║                     ※2. 查询字符的编码                      ║");
    	puts("                         ║                                                              ║");
        puts("                         ║                     ※3. 打印哈弗曼树                        ║");
    	puts("                         ║                                                              ║");
        puts("                         ║                     ※4. 查询编码后文件                      ║");
    	puts("                         ║                                                              ║");
        puts("                         ║                     ※5. 查询译码后文件                      ║");
    	puts("                         ║                                                              ║");
        puts("                         ║                     ※6. 退出                                ║");
        puts("                         ║                                                              ║");
        puts("                         ╚═══════════════════════════════╝");
    	 printf("\n\n请选择（1-6）:");
    
    }
    void mi_ma()//密码验证
    {	
    	int   i=0, x = 3;
        int flag = 0;
        char    s[20];
    	char mima[20]="123456";
    	 system("cls");
     system("color 03" );
    	system("color 0a");
        do
        { 
    	  printf("\n\n");
          printf(" ╒═━━━━━━╗\n");
          printf(" ║请您输入密码: ║\n");
          printf(" ╚━━━━━━━╝\n");
    		for(i=0;i<6;i++)
    		{
    			s[i]=getch();
                printf("%c",s[i]);
    		 	printf("\b*");
    		}
    	getch();
        s[6]='\0';
        printf("\n");
    	
    
    	if(!strcmp(s,mima))//进行密码验证
            {
                printf("密码正确！！！！\n\n\n按任意键继续~~~\n");
    			getch();
                flag=1;
                break;
            }
            else
            {
                printf("密码错误，请重新输入:\n");
                x--;
            }
        }
        while(x>0);
        if(!flag)
        {
            printf("你已经输入三次错误密码!");
            exit(0);
        }
    
    
    }
    main()
    {
    	int i;
    	weighttype weight[N]={0};
    	hfm HFM[MAX];
    	
    	codetype code[N]; //存放哈弗曼编码
    	mi_ma();
    
    	menu();
    		while(1)
    	{
    loop:
    		fflush(stdin);
    		scanf("%d",&i);
    		
    		    switch(i)
    			{
    		      case 1: 
    		    	save_in_f1();
    		read_in_f1(weight); //获取各个字符的出现的频率
        	create_hfm(HFM,weight);//建立哈弗曼树
    			
    		    	break;
    			 case 2:
    				   	read_in_f1(weight); //获取各个字符的出现的频率
        	create_hfm(HFM,weight);//建立哈弗曼树
    			    hfmcode(code,HFM);//编码
    			    break;
    			  case 3:
    			///	  	read_in_f1(weight); //获取各个字符的出现的频率
        //	create_hfm(HFM,weight);//建立哈弗曼树
    				print(HFM);//输出哈弗曼树
    				break;		   			
    			  case 5:
    				  	read_in_f1(weight); //获取各个字符的出现的频率
        	create_hfm(HFM,weight);//建立哈弗曼树
    			decode(HFM);//解码 
    				break;
    				 case 4:
    					 	read_in_f1(weight); //获取各个字符的出现的频率
        	create_hfm(HFM,weight);//建立哈弗曼树
    			    printcode();
    				break;
    					 case 6:
    						 exit(0);
    		
    				break;
    			  default:printf("您输入的编码不对！请重新输入：\a");
    			    goto loop;
    			}	
    	}
    	
    
    }

[Image 1]: