哈夫曼.c

huffman编码译码系统 很简单的课程设计 有文件操作和压缩 附送一个航空售票管理

#include<stdio.h>
#include<malloc.h>
#include<process.h>
#include<conio.h>
#include<string.h>
#define MAX 100
#define MAXN 100

typedef struct node
{
	int parent;
	int lc,rc;
	int data;
	char ch;
}NODE;
typedef struct lnode 
{
	int data;
	char ch;
	struct lnode *next;
}LNODE;
typedef struct 
{
	int data;
	char ch;
	char mima[MAX];
}QZZF;
int n;

void haffman(NODE r[],QZZF qzzf[]);
int bianma(NODE r[],char a[],QZZF qzzf[]);
void yima(NODE r[],char a[],int count,QZZF qzzf[]);
void tongji(QZZF qzzf[]);

void tongji(QZZF qzzf[])
{    
	FILE *fp2;
	int i;
	char num;
	LNODE *p,*q,*t,*s;
	n=0;
	fp2=fopen("e:\\tongji.txt","rt");
	if((fp2=fopen("e:\\tongji.txt","rt"))==NULL)
	{
		printf("Cannot open it !!!\n");
		getch();
		exit(1);
	}
	s=p=(LNODE *)malloc(sizeof(LNODE));
	p->ch=num=fgetc(fp2);
	for(p->data=1,p->next=NULL;(num=fgetc(fp2))!=EOF;)
	{
		q=(LNODE *)malloc(sizeof(LNODE));
		p->next=q;
		q->next=NULL;
		q->ch=num;
		q->data=1;
		p=q;
	}
	p->next=s;
	p=s;
	while(p->next!=s)
	{
		putchar(p->ch);
		p=p->next;
	}
	putchar(p->ch);
	printf("\n");
	fclose(fp2);
	for(p=s;p->next!=s;p=p->next)
		for(t=p,q=p->next;q!=s;)
			if(q->ch==p->ch)
			{
				t->next=q->next;
				p->data++;
				free(q);
				q=t->next;
			}
			else
			{
				t=q;
				q=q->next ;	
			}
      p=s,i=1;
	printf("字符 权值:");
	do
	{	
		printf("\n");
		printf("%c-----%d ",p->ch,p->data);
		qzzf[i].data=p->data;
        qzzf[i].ch=p->ch;
		p=p->next;
		n++;i++;
	}while(p!=s);
} 

void yima(NODE r[],char a[],int count,QZZF qzzf[])
{
	int t,j=1,m,i=1,k;
	char c[MAX];
        k=2*n-1;
		while(j<=count)
        {
			if(a[j]=='0')
             t=r[k].lc;
            if(a[j]=='1')
             t=r[k].rc;
           if(r[t].lc==0)
		   {
			   printf("第%d个密码应译为",i);
			   printf("%2c--%2d\n",r[t].ch,r[t].data) ;
              k=2*n-1;
			  j++;
			  i++;
           }
           else
             k=t;
		   j++;
        } 
   printf("要编码的字符为:");
     gets(c);
	printf("\n密码为");
	m=strlen(c);
  for(k=0;k<m;k++)
	 for(j=1;j<=n;j++)
		if(c[k]==qzzf[j].ch)
			printf("%s",qzzf[j].mima);
		printf("\n密码译为:");
		puts(c);
}
int bianma(NODE r[],char a[],QZZF qzzf[])
{
	FILE *fp1;
	int i,t,m,g=1,f=1,k,j=1,q,count;
	char b[MAX];
	for(i=1;i<=n&&j<MAX;i++)
	{    
	     q=0; 
		for(m=1,t=1;t<=n;t++)
	      b[t]='2';
         t=r[i].parent;
	    if(r[t].lc==i)
            b[m++]='0';
	    if(r[t].rc==i)
			b[m++]='1';
	    while(r[t].parent!=0)
		{
			k=t;
		    t=r[t].parent;
		    if(r[t].lc==k)
                  b[m++]='0';
		    if(r[t].rc==k)
                  b[m++]='1';
		}
          for(q=0,t=m-1;t>0;t--,q++)
		  {
			if(b[t]=='2')
                ;
			else
				qzzf[i].mima[q]=a[j++]=b[t];
		  }
		  qzzf[i].mima[q]='\0';
		  a[j++]='2';
    } 
	count=j-1; 
	
	for(i=1;i<=count;i++)
	{   
		if(a[i]=='2'&&f<=n)
		     printf("为%c编码\n",r[f++].ch);
		if(a[i]!='2')    
			printf("%c",a[i]);
           
	}
  	if((fp1=fopen("e:\\bianma.txt","wt"))==NULL)
	 {
		printf("不能打开文件!\n");
		exit(0);
	 }
	for(i=1;i<=count;i++)
	{   
		if(a[i]=='2'&&g<=n)
		     fprintf(fp1,"为%c编码\n",r[g++].ch);
		if(a[i]!='2')    
			fprintf(fp1,"%c",a[i]);
   	}
	fclose(fp1);
          return count;
}

void haffman( NODE r[],QZZF qzzf[])
{
	FILE *fp;
 int m1,m2,x1,x2,i,j;/*m存放最小次小权值，x存放他们的地址，n是终端结点数*/
	 
	 for(i=1;i<=n;i++)
	 {
		 r[i].data=qzzf[i].data;
		 r[i].ch=qzzf[i].ch;
		 r[i].parent=0;
		 r[i].lc=0;
		 r[i].rc=0;
	 }
	 i=0;
	 while(i<n-1)
	 {
	      m1=32767;
	      m2=32767;
	      x1=0;
	      x2=0;
	      for(j=1;j<=n+i;j++)
	       if((r[j].data<m1)&&(r[j].parent==0))
		 {
			 m2=m1;
			 x2=x1;
			 m1=r[j].data;
			 x1=j;
		 }
		 else
	        if((r[j].data<m2)&&(r[j].parent==0))
		{
            m2=r[j].data;
			x2=j;
		}	 
			 i++;
		r[x1].parent=n+i;
		r[x2].parent=n+i;
		r[n+i].data=r[x1].data+r[x2].data;
		r[n+i].lc=x1;
		r[n+i].rc=x2;
		r[n+i].parent=0;
 }

      printf("\n结点下标 双亲结点 左孩子  权值  右孩子\n");
	 for(i=1;i<=2*n-1;i++)
	 printf("%8d  %6d %6d %6d %6d\n",i,r[i].parent,r[i].lc,r[i].data,r[i].rc);
	 if((fp=fopen("e:\\haffman.txt","wt"))==NULL)
	 {
		printf("不能打开文件!\n");
		exit(0);
	 }
     fprintf(fp,"结点下标 双亲结点 左孩子  权值  右孩子\n");
	 for(i=1;i<=2*n-1;i++)
	 fprintf(fp,"%8d  %6d %6d %6d %6d\n",i,r[i].parent,r[i].lc,r[i].data,r[i].rc);
	 fclose(fp);


 }
 main()
 {
	 int count;        /*密码长度*/    
     char a[MAX];
	 NODE r[MAX];
	 QZZF qzzf[MAX];
	 tongji(qzzf);
	 haffman(r,qzzf);
     count=bianma(r,a,qzzf);
	 yima(r,a,count,qzzf);
    
 }