0++并用其编写解压和解压缩文件的程序.cpp

哈夫曼压缩解压缩 都很少看见翻翻看如我定时开机

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#include <Math.h>
#include <conio.h>
#define  MAX    20

typedef struct             /*哈夫曼树结构体*/       
{
	int flag;
	char data;
	int weight;
	int parent;
	int lchild;
	int rchild;
}Hftree,*HfmanTree;

typedef struct            /*哈夫曼编码结构体*/ 
{
	char data;
	int weight;
	char *code;
}Hfcode,*HfmanCode;
  
typedef struct Node       /*二叉链表*/
{
    int data;
    struct Node *lchild;
    struct Node *rchild;
}BitNode,*BiTree;

char filename[20];        /*全局变量*/
char filename1[20];

void Hfm_weight(char *&str,int *&wei,int &n,char fname[])           /*读文件求得每个字符的权值*/
{
	int i,j=1,num;
	char ch,fname1[20];
	FILE *fp;
	num=MAX;
	n=0;
      strcpy(fname1,fname);
	for(i=1;i<=MAX;i++)
	{
		wei[i]=0;
	}
      	if((fp=fopen(fname1,"r"))==NULL)
	{
		printf("文件读取失败！\n");
             exit(0);
	}
	while(!feof(fp))
	{
             ch=fgetc(fp);
             if(ch<0)
             break;
		for(i=1;wei[i]!=0;i++)
		{
			if(ch==str[i])
				{wei[i]++;
				goto jump;}
				
		}
		str[j]=ch;              /*将字符存入数组中*/
		wei[j]++;                 /*更新权值*/
             	j++;
		n++;                      /*记录不相同字符的个数*/
		if(j>=num)
		{
			num++;
			str=(char *)realloc(str,(num+1)*sizeof(char));
			wei=(int *)realloc(wei,(num+1)*sizeof(int));
                    	wei[j+1]=0;
		}
	
	jump:;
	}
}

void select(HfmanTree &ht,int n,int &s1,int &s2)      /*取两个权值最小的*/
{
	int i;
	for(i=1;i<=n;i++)
	{
		if(ht[i].flag==0)
			s1=i;
	}
	for(i=1;i<=n;i++)
	{
		if(ht[i].parent==0 && ht[i].flag==0)
		{
			if(ht[i].weight<ht[s1].weight)
			{
				s1=i;
			}
		}
	}
	ht[s1].flag=1;
	for (i=0;i<=n;i++)
	{	
		if (ht[i].flag==0)
			s2=i;
	}
	for(i=1;i<=n;i++)
	{
		if(ht[i].parent==0 && ht[i].flag==0)
		{
			if(ht[i].weight<ht[s2].weight)
			{
				s2=i;
			}
		}
	}
	ht[s2].flag=1;
	
}

void creat_hfmtree(HfmanTree &ht,int n,int wei[],char str[])      /*创建哈夫曼树*/
{
	int i,m;
	int s1,s2;
	m=2*n-1;
	ht=(Hftree *)malloc((m+1)*sizeof(Hftree));
	for(i=1;i<=n;i++)
	{
		ht[i].flag=0;
		ht[i].data=str[i];
		ht[i].weight=wei[i];
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)
	{
		ht[i].flag=0;
		ht[i].data='#';
		ht[i].weight=0;
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(i=n+1;i<=m;i++)
	{
		select(ht,i-1,s1,s2);
		ht[i].weight=ht[s1].weight+ht[s2].weight;
		ht[s1].parent=i;
		ht[s2].parent=i;
		ht[i].lchild=s1;
		ht[i].rchild=s2;
	}
	printf("number      data      weight      parent     lchild     rchild\n");
		for(i=1;i<=m;i++)
		 {
			printf("%4d %10c %10d %10d %10d %10d\r\n",i,ht[i].data,ht[i].weight,
        ht[i].parent,ht[i].lchild,ht[i].rchild);
		 }


}
void Hfcoding(HfmanTree ht,HfmanCode hc,char str[],int wei[],int n)             /*哈夫曼树编码*/
{
	char *cd;
	int start,c,p,i;
	cd=(char *)malloc(n*sizeof(char));
	cd[n-1]='\0';
	for(i=1;i<=n;i++)
	{
		start=n-1;
		c=i;
		p=ht[i].parent;
		while(p!=0)
		{
			--start;
			if(ht[p].lchild==c)
				cd[start]='0';
			else 
				cd[start]='1';
			c=p;
			p=ht[p].parent;
		}
		hc[i].code=(char *)malloc((n-start)*sizeof(char));
		strcpy(hc[i].code,&cd[start]);
		hc[i].data=str[i];
		hc[i].weight=wei[i];
	}
	free(cd);
}

void Save_code(HfmanCode &hc,int &n)            /*保存哈夫曼编码*/
{
	int i;
	char fname[20];
	FILE *fp;
	printf("输入要保存编码信息的文件路径：\n");
		scanf("%s",fname);
	if((fp=fopen(fname,"w"))==NULL)
	{
		printf("不能创建文件！\n");
		exit(0);
	}
	for(i=1;i<=n;i++)
	{
		fprintf(fp,"%8c%8d%8s\n",hc[i].data,hc[i].weight,hc[i].code);
	}
	fclose(fp);
}

void Press_Code(HfmanCode hc,int &n,char fname[])                    /*压缩并保存编码*/
{
	int i,k=0;
	unsigned int m;
	char fname1[20],fname2[20],fname3[20];
	char ch,*s;
	FILE *fp1,*fp2,*fp3;
	m=MAX;
	strcpy(fname2,fname);
	s=(char *)malloc(MAX*sizeof(char));
	if((fp2=fopen(fname2,"r"))==NULL)
	{
		printf("要进行编码的文件不存在！");
		exit(0);
	}
	printf("输入要保存编码的文件名:\n");
	scanf("%s",fname1);
      strcpy(filename1,fname1);
	if((fp1=fopen(fname1,"w"))==NULL)
	{
		printf("创建文件失败！");
		exit(0);
	}
	while((ch=fgetc(fp2))!=-1)
	{
		for(i=1;i<=n;i++)
		{
			if(ch==hc[i].data)
				fprintf(fp1,"%s",hc[i].code);
		}
	}
	fclose(fp1);
	while((ch=fgetc(fp2))!=-1)
	{
		for(i=1;i<=n;i++)
		{
			if(ch==hc[i].data)
			{
				strcat(s,hc[i].code);
				if(strlen(s)>=m)
					s=(char *)realloc(s,(MAX+m)*sizeof(char));
			}
		}
	}
	fclose(fp2);
	printf("输入放压缩信息的文件名:\n");
	scanf("%s",fname3);
      strcpy(filename,fname3);
	if((fp3=fopen(fname3,"w"))==NULL)
	{
		printf("文件创建失败!");
		exit(0);
	}
	if((fp1=fopen(fname1,"r"))==NULL)
	{
		printf("文件打开失败!");
		exit(0);
	}
	i=0;
	while((ch=fgetc(fp1))!=-1)
	{
		if(ch=='0')
			k=k*2;
		else  if(ch=='1')
			k=k*2+1;
		i++;
		if(i%8==0)
		{
			fprintf(fp3,"%c",k);
			k=0;
		}
	}	
		if(i%8!=0)
		{	
			k=k*(int)(pow(2,(8-i%8)));
			fprintf(fp3,"%c",k);
		}
	fclose(fp1);
	fclose(fp3);
}

void Trancoding(HfmanTree ht,int &n)           /*译码*/
{
	FILE *fp1,*fp2;
	int p,m;
	char ch;
	char fname[20],fname1[20];
	m=2*n-1;
	p=m;
      strcpy(fname1,filename1);
	if((fp1=fopen(filename1,"r"))==NULL)
	{
		printf("文件打开失败！");
			exit(0);
	}
	printf("输入要保存译码的文件名：");
		scanf("%s",fname);
	if((fp2=fopen(fname,"w"))==NULL)
	{
		printf("文件创建失败!");
		exit(0);
	}
	while(!feof(fp1))
	{
		ch=fgetc(fp1);
		if(ch=='0')
            		p=ht[p].lchild;
        	if(ch=='1')
            		p=ht[p].rchild;
        	if(ht[p].lchild==0&&ht[p].rchild==0)
        	{
            		fputc(ht[p].data,fp2);
            		p=m;
        	}

	}
	fclose(fp1);
	fclose(fp2);


}

void repress(HfmanTree ht,int n,char str[])       /*解压*/
{
	int p=2*n-1;
	unsigned int a,b;
	int i,m;
	char ch;
	char cd[9];
	char fname[20];
	char fname2[20],fname3[20];
	FILE *fp,*fp1,*fp2;
	printf("\n请输入中转文件名:");
	printf("\n");
	scanf("%s",fname2);
	printf("\n请输入解压缩后的文件名:");
	scanf("%s",fname);
	if((fp=fopen(fname,"w"))==NULL)
	{
		printf("文件创建失败!");
		exit(0);
	}
      strcpy(fname3,filename);
	if((fp1=fopen(fname3,"r"))==NULL)
	{
		printf("文件打开失败!");
		exit(0);
	}
	if((fp2=fopen(fname2,"w"))==NULL)
	{
		printf("文件创建失败!");
		exit(0);
	}
	while((ch=fgetc(fp1))!=-1)
	{
		a=(int)ch;
		cd[8]='\0';
		for(i=7;i>=0;i--)
		{
			b=a%2;
			a=a/2;
			if (b==1)
				cd[i]='1';
			else 
				if(b==0)
					cd[i]='0';			
		}	
		fprintf(fp2,"%s",cd);
	}
	fclose(fp1);
	fclose(fp2);
	if((fp2=fopen(fname2,"r"))==NULL)
	{
		printf("文件打开失败!");
		exit(0);
	}
	m=ht[2*n-1].weight;
	while((ch=fgetc(fp2))!=-1)
	{
		if(ch=='0')
			p=ht[p].lchild;
		else
			p=ht[p].rchild;
		if(ht[p].lchild==0 && ht[p].rchild==0)
		{
			 fprintf(fp,"%c",str[p]);
			 m--;
			 if (m==0)
				 goto jump;
			 p=2*n-1;	
		}
	}
	jump:
	fclose(fp2);
	fclose(fp);
}

int PostTreeDepth(HfmanCode &hc,int &n)
{
	int i;
	unsigned int max;
	max=strlen(hc[1].code);
	for(i=2;i<n+1;i++)
	{ 
		if(strlen(hc[i].code)>max)
			max=strlen(hc[i].code);
	}
	return max+1;
}

BiTree  creatbitree(HfmanTree ht, int n)        /*将哈夫曼树转化为二叉树*/
{
	char ch;
	BitNode *s;
	ch=ht[n].data;
	if(n==0)
		return NULL;
	else
	{
		s=(BitNode *)malloc(sizeof(BitNode));
		s->data=ch;
		s->lchild=creatbitree(ht,ht[n].lchild);
		s->rchild=creatbitree(ht,ht[n].rchild);
		return s;
	}
}

void PrintTree(BiTree root,int nLayer)      /*树形打印哈夫曼树*/
{
	int i;
 	if(root!=NULL)
	{
		PrintTree(root->rchild, nLayer+3);
		for(i=0;i<nLayer;i++)
			printf("    ");
			printf("%c\n",root->data);
		PrintTree(root->lchild, nLayer+3);
	}
}
void main()
{
	int n=0;         /*叶子结点个数*/
	char *str;       
      	int *wei;
	char fname[20];
	HfmanTree  ht;
	HfmanCode  hc;
	BitNode  *root;
	str=(char *)malloc((MAX+1)*sizeof(char));
	wei=(int *)malloc((MAX+1)*sizeof(int));
	printf("\t\t\t哈夫曼树的编码和译码\n");	
	printf("输入要读取文件并求每个字符权值的文件名及其路径：\n");
	scanf("%s",fname);
	Hfm_weight(str,wei,n,fname);
        printf("创建哈夫曼树......\n");
	printf("输出哈夫曼树的信息......\n");
        creat_hfmtree(ht,n,wei,str); 
	printf("树形打印哈夫曼树......\n");
	root=creatbitree(ht,2*n-1);  
	PrintTree(root,1);
	hc=(Hfcode *)malloc((n+1)*sizeof(Hfcode));        
        printf("对哈夫曼树进行编码......\n");
        Hfcoding(ht,hc,str,wei,n);   
        printf("哈夫曼编码......\n");
        Save_code(hc,n);             
        printf("压缩文件并保存......\n");
        Press_Code(hc,n,fname);
	printf("解压并保存......"); 
	repress(ht,n,str);
       printf("正在译码......\n");
	Trancoding(ht,n); 
	printf("所有功能已完成！");                      
}