哈夫曼編碼--------檔案壓縮與解壓

實驗目的：實作對檔案的壓縮與減壓

#include<stdio.h>
#include<stdlib.h>

#include <fstream>
using namespace std;

typedef char ElemType;
typedef struct hfmTNode
{
	ElemType element;
	int w;
	struct hfmTNode *rChild;
	struct hfmTNode *lChild;
}HFMTNode;

typedef HFMTNode hfm;

//建立隊列
typedef struct priorityQueue
{
	hfm *element;
	int n;
	int maxSize;
}PriorityQueue;

void CreatePQ(priorityQueue *PQ,int msize)
{
	PQ->maxSize=msize;
	PQ->n=0;
	PQ->element=(hfm *)malloc(msize*sizeof(hfm));
}
void AdjustUp(hfm heap[],int current)
{
	int p=current;
	hfm temp;
	while(p>0)
	{
		if(heap[p].w<heap[(p-1)/2].w)
		{
			temp=heap[p];
			heap[p]=heap[(p-1)/2];
			heap[(p-1)/2]=temp;
			p=(p-1)/2;
		}
		else
			break;
	}
}

void AdjustDown(hfm heap[],int current,int border)
{
	int p=current;
	int minchild;
	hfm temp;
	while(2*p+1<=border)
	{
		if((2*p+2<=border)&&(heap[2*p+1].w>heap[2*p+2].w))
			minchild=2*p+2;
		else
			minchild=2*p+1;
		if(heap[p].w<=heap[minchild].w)
			break;
		else
		{
			temp=heap[p];
			heap[p]=heap[minchild];
			heap[minchild]=temp;
			p=minchild;
		}
	}
}
int IsFull(PriorityQueue *PQ)
{
	if(PQ->n==PQ->maxSize)
		return 1;
	else
		return 0;
}
int IsEmpty(PriorityQueue *PQ)
{
	if(PQ->n==0)
		return 1;
	else
		return 0;
}
void Append(PriorityQueue *PQ,hfm x,int i,char *ch)
{
	if(IsFull(PQ))
		return;
	PQ->element[PQ->n]=x;
	if(i)
	{
		PQ->element[PQ->n].element=*ch;
	}
	PQ->n++;
	AdjustUp(PQ->element,PQ->n-1);
}

hfm* Serve(PriorityQueue *PQ)
{
	if(IsEmpty(PQ))
		return NULL;
	hfm *p=(hfm *)malloc(sizeof(hfm));
	p->element=PQ->element[0].element;
	p->lChild=PQ->element[0].lChild;
	p->rChild=PQ->element[0].rChild;
	p->w=PQ->element[0].w;
	PQ->n--;
	PQ->element[0]=PQ->element[PQ->n];
	AdjustDown(PQ->element,0,PQ->n-1);
	return p;
}

hfm* MakeTree(int w,hfmTNode *y,hfmTNode *z)
{
	hfm *p=(hfm *)malloc(sizeof(hfm));
	p->w=w;
	p->lChild=y;
	p->rChild=z;
	return p ;
}
//先序周遊
void PreOrder(hfm *t)
{
	if(!t)
		return;
	printf("%d  ",t->w);
	PreOrder(t->lChild);
	PreOrder(t->rChild);
}
HFMTNode* CreateHFMTree(int w[],int m)
{
	PriorityQueue PQ;
	HFMTNode *x,*y,*z;
	CreatePQ(&PQ,m);
	char ch[64];
	char c;
	c='0';
	for(int i=0;i<10;i++)
	{
		ch[i]=c+i;
	}
	c='A';
	for(int i=0;i<26;i++)
	{
		ch[i+10]=c+i;
	}
	c='a';
	for(int i=0;i<26;i++)
	{
		ch[i+36]=c+i;
	}
	ch[62]=32;
	ch[63]=10;
	for(int i=0;i<m;i++)
	{
		c=ch[i];
		x=MakeTree(w[i],NULL,NULL);
		Append(&PQ,*x,1,&c);
	}
	while(PQ.n>1)
	{
		x=Serve(&PQ);
		y=Serve(&PQ);
		if(x->w<y->w)
			z=MakeTree(x->w+y->w,x,y);
		else
		    z=MakeTree(x->w+y->w,y,x);
		
		Append(&PQ,*z,0,&c);	
	}
	return z;
}
//編碼
void CodingTree(int (*code)[100] ,int c[],char ch[],hfm *t,int *i,int j)
{
	if(!t)
		return;
	if(!t->lChild&&!t->rChild)
	{
		int p=0;
		for(int z=0;z<j;z++)
		{
			code[*i][p]=c[p];
			p++;
		}
		code[*i][p]=-1;
		ch[*i]=t->element;
		(*i)++;
		return;
	}
	else
	{
		c[j]=0;
		j++;
		CodingTree(code,c,ch,t->lChild,i,j);
	}
	
	j--;
	if(!t->lChild&&!t->rChild)
	{
		int p=0;
		for(int z=0;z<j;z++)
		{
			code[*i][p]=c[p];
			p++;
		}
		code[*i][p]=-1;
		ch[*i]=t->element;
		(*i)++;
		return;
	}
	else
	{
		c[j]=1;
		j++;
		CodingTree(code,c,ch,t->rChild,i,j);	
	}
	
}
void Coding(hfm *t,char *cc)
{
    FILE *file3;
	file3=fopen("C:/Users/123/Desktop/好好學習，天天向上/資料結構/資料/編碼檔案.txt","wb");
	if(file3==NULL)
	{
		printf("open error!\n");
		return ;
	}
    int code[100][100];
	for(int i=0;i<100;i++)
		for(int j=0;j<100;j++)
			code[i][j]=-1;
	char ch[100];
	int p=0;
	int c[100];
	for(int i=0;i<100;i++)
		c[i]=-1;
	
	//編碼
	CodingTree(code,c,ch,t,&p,0);
    int ii=0;
	unsigned char b;
	//int b[8];
	int bb=0;
	b=0;
	//int d;
	while(cc[ii]!='\0')
	{
		for(int j=0;j<p;j++)
		{
	    	if(cc[ii]==ch[j])
			{
				int pp=0;
				while(code[j][pp]!=-1)
				{
					if(bb==8)
					{
						fwrite(&b, 1, 1, file3);
						b=0;
						bb=0;
					}
					if (code[j][pp]==1)
						b = (b << 1) | 1;
				    else if(code[j][pp]==0) 
						b= b << 1;
					pp++;
					bb++;
					
				}
			}
		}
		ii++;
	}
	fclose(file3);
}

//解碼
void decode(hfm *t)
{
	FILE *file3=fopen("C:/Users/123/Desktop/好好學習，天天向上/資料結構/資料/編碼檔案.txt","rb");
	if(file3==NULL)
	{
		printf("open error!\n");
		return ;
	}
	FILE *file4=fopen("C:/Users/123/Desktop/好好學習，天天向上/資料結構/資料/編碼翻譯檔案.txt","w");
	if(file4==NULL)
	{
		printf("open error!\n");
		return ;
	}
    unsigned char la;
	long f;
	
	hfm *d;
	d=t;
    char ch=' ';
	int b=0;
	char buf[255],bx[29];
	int temp=0;
	fread(&la,1,1,file3);
		f=la;
		itoa(f, buf, 2);
		f = strlen(buf);
		for (long l = 8; l > f; l--) {
			bx[8-l]='0';
			}
		for(int i=0;i<=f;i++)
		{
			bx[i+8-f]=buf[i];
		}
	while(!feof(file3))
	{	
		if(temp==8)
		{
			fread(&la,1,1,file3);
			f=la;
			itoa(f, buf, 2);
			f = strlen(buf);
			for (long l = 8; l > f; l--) {
				bx[8-l]='0';
				}
			for(int i=0;i<=f;i++)
			{
				bx[i+8-f]=buf[i];
			}
			temp=0;
		}
		
		if(!d->lChild&&!d->rChild)
		{
			fprintf(file4,"%c",d->element);
			d=t;
			
		}
		else
		{
			
			if(bx[temp]=='0')
			{
				d=d->lChild;
			}
			if(bx[temp]=='1')
			{
				d=d->rChild;
			}
			temp++;
		}
	
	}
	fprintf(file4,"%c\n",d->element);
	fclose(file3);
	file3=NULL;
    fclose(file4);
	file4=NULL;
}	

//清空二叉樹
void Clear(hfm *t)
{
	if(!t)
		return;
	Clear(t->lChild);
	Clear(t->rChild);
	free(t);
}

//獲得權級
void frequent(char *c,int *w)
{
	char ch;
	int num[64];
	int j=0;
	for(int i=0;i<64;i++)
	{
		num[i]=0;
	}
	int n=0;
	while(c[n]!='\0')
	{
		j++;
		ch='0';
		for(int i=0;i<10;i++)
		{
			if(c[n]==ch+i)
				num[i]++;
		}
		ch='A';
		for(int i=0;i<26;i++)
		{
			if(c[n]==ch+i)
				num[i+10]++;
		}
		ch='a';
		for(int i=0;i<26;i++)
		{
			if(c[n]==ch+i)
				num[i+36]++;
		}
		if(c[n]==32)
			num[62]++;
		if(c[n]==10)
			num[63]++;
		n++;
	}
	for(int i=0;i<64;i++)
	{
		w[i]=num[i];
	}
	//向文本輸入權值
	FILE *file2=fopen("C:/Users/123/Desktop/好好學習，天天向上/資料結構/資料/權值表檔案.txt","w");
	if(file2==NULL)
	{
		printf("open error!\n");
		return ;
	}

	
	fprintf(file2,"(0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,' ','LF')\n(");
	ch='0';
	for(int i=0;i<10;i++)
	{
		fprintf(file2,"%d,",num[i]);
	}
	ch='A';
	for(int i=0;i<26;i++)
	{
		fprintf(file2,"%d,",num[i+10]);
	}
	ch='a';
	for(int i=0;i<26;i++)
	{
		fprintf(file2,"%d,",num[i+36]);
	}
	fprintf(file2,"%d,",num[62]);
	fprintf(file2,"%d)",num[63]);
	fclose(file2);
	file2=NULL;
}
//導入文本
void TEXT(int *w,char *ch)
{
	FILE *file1=fopen("C:/Users/123/Desktop/好好學習，天天向上/資料結構/資料/測試資料.txt","r");
	if(file1==NULL)
	{
		printf("open error!\n");
		return ;
	}
	char cc[300000];
	int NUM=0;
	while((cc[NUM]=fgetc(file1))!=EOF)
	{
		NUM++;
	}
	fclose(file1);
	file1=NULL;
	int num=0;
	NUM=0;
	char c;
	while(cc[NUM]!='\0')
	{
		c=cc[NUM];
	    if((48<=c&&c<=57)||(65<=c&&c<=90)||(97<=c&&c<=122)||c==10||c==32)
		{
		 	ch[num]=c;
			num++;
		}
		NUM++;
	}
	ch[num]='\0';
	frequent(ch,w);
}
void main()
{
	hfm *h;
	int w[64];
	char ch[300000];
	TEXT(w,ch);
	h=CreateHFMTree(w,64);
 	Coding(h,ch);
	decode(h);
	printf("已完成轉化\n");
	Clear(h);
}
           

• 程式運作結果

運作前

運作後

權值表，編碼，和通過編碼解壓出的譯碼存在各自檔案夾中

運作後：

權值表：

編碼：

譯碼：