363707100.c

哈弗曼编码之一 西安邮电学院课程设计中能够用到

#include<stdio.h>
#include<string.h>
#define N 256
#define M 2*N-1
struct node    
{
    char ch;
    int weight;
}Huffmancode[N];
struct NODE
{
    int weight;
    int parent;
    int lchild;
    int rchild;
	char ch;
}HuffmanTree[M];
struct node1
{
    char ch;
    char code[N];
}zifu[N];
int all;
char word[4096];
char word_code[4096];
int Huffman_num;
int input_word(char *word);
int jisuanquanzhi(char *word,int word_num);
void jianlishu(int Huffman_num);
void choose(int i,int *s1,int *s2);
void bianma(int n);
void yima(char *word_code,int Huffman_num);
void compare();
void main()
{
	int choice;
	do
	{

        printf("\n\t\t********************************************\n");
		printf("\n\t\t**        请输入数字以完成如下操作:       **\n");
		printf("\n\t\t**        1.打开操作文件并统计权值        **\n");
		printf("\n\t\t**        2.建立并保存哈夫曼树            **\n");
		printf("\n\t\t**        3.编码哈夫曼并输出到文件        **\n");
		printf("\n\t\t**        4.反编译哈夫曼并输出到文件      **\n");
		printf("\n\t\t**        5.进行文件对比                  **\n");
		printf("\n\t\t**        0.退出                          **\n");
		printf("\n\t\t******************************************\n");
		scanf("%d",&choice);
		system("cls");
		switch(choice)
		{
		    case 1:Huffman_num=input_word(word);break;
			case 2:jianlishu(Huffman_num);printf("Successed~~\n");getchar();break;
			case 3:bianma(Huffman_num);break;
			case 4:yima(word_code,Huffman_num);break;
			case 5:compare();break;
			case 0:break;
		}
	}while(choice!=0);
}

int input_word(char *word)
{
    FILE *fp1;
    int i=0,m=1,j,flag;
	char filename[30],ch;
    printf("Now let's begin!\n\n请输入你所要编译的文件名:");	
	scanf("%s",filename);
    if((fp1=fopen(filename,"rt"))==NULL)
    {
        printf("不能打开此文件");
		exit(1);
    }
    ch=fgetc(fp1);
    while(ch!=EOF)
    {
       word[i]=ch;
       i++;
       ch=fgetc(fp1);
    }
    all=i;
    for(i=0;i<all;i++)
    {
        ch=word[i];
        flag=0;
        for(j=1;j<m;j++)
        {
            if(Huffmancode[j].ch==ch)   
            {
                Huffmancode[j].weight++;
                flag=1;
                break;
            }
        }
        if(flag==0)
        {
            Huffmancode[m].ch=ch;Huffmancode[m].weight=1;
            m++;
        }
   }
   return m-1;
}

void jianlishu(int Huffman_num)
{
    int i,n,m;
    int s1,s2;
    n=Huffman_num;
    m=2*n-1;
    for(i=1;i<=n;i++)
    {
       HuffmanTree[i].weight=Huffmancode[i].weight;
	   HuffmanTree[i].ch=Huffmancode[i].ch;
       HuffmanTree[i].parent=0;
       HuffmanTree[i].lchild=0;
       HuffmanTree[i].rchild=0;
    }
    for(i=n+1;i<=m;i++)
    {
		HuffmanTree[i].ch=-1;
       HuffmanTree[i].weight=0;
       HuffmanTree[i].parent=0;
       HuffmanTree[i].lchild=0;
       HuffmanTree[i].rchild=0;
    }
    for(i=Huffman_num+1;i<=m;i++)
    {
       choose(i-1,&s1,&s2);
       HuffmanTree[i].weight=HuffmanTree[s1].weight+HuffmanTree[s2].weight;
       HuffmanTree[s1].parent=i;
       HuffmanTree[s2].parent=i;
       HuffmanTree[i].lchild=s1;
       HuffmanTree[i].rchild=s2;
    }
	for(i=0;i<=m;i++)
	{
		printf("字符为%c权值为%d双亲为%d左孩子为%d右孩子为%d\n",HuffmanTree[i].ch,HuffmanTree[i].weight,HuffmanTree[i].parent,HuffmanTree[i].lchild,HuffmanTree[i].rchild);
	}
}

void choose(int i,int *s1,int *s2)
{
    int j;
    for(j=1;j<=i;j++)
    {
        if(HuffmanTree[j].parent==0 && HuffmanTree[j].weight!=0) 
            break;
    }
    *s1=j;
    for(j=1;j<=i;j++)
    {
        if(HuffmanTree[j].parent==0 && HuffmanTree[j].weight!=0 && j!=*s1)
            break;
    }
    *s2=j;
    for(j=1;j<=i;j++)
    {
        if((HuffmanTree[j].weight<HuffmanTree[*s1].weight) && (HuffmanTree[j].parent==0) && j!=*s2) 
            *s1=j;
    }
    for(j=1;j<=i;j++)
    {
        if((HuffmanTree[j].weight<HuffmanTree[*s2].weight) && (HuffmanTree[j].parent==0) && j!=*s1) 
            *s2=j;
    }
}

void bianma(int n)
{
    char cd[10],filename1[30];
    int i,j,k,l,temp,start;
	FILE *fp;
    i=1;
    start=0;
    l=0;
    while(1)
    {
        if(i>n) break;
        start=0;
        temp=i;
        while(1)
        {
            if(HuffmanTree[temp].parent==0) break;
            j=temp;
            temp=HuffmanTree[temp].parent;
            if(HuffmanTree[temp].lchild==j) 
            {
                cd[start]='0';
                start++;
            }
            if(HuffmanTree[temp].rchild==j) 
            {
                cd[start]='1';
                start++;
            }
        }
        zifu[i].ch=Huffmancode[i].ch;
        for(k=start-1;k>=0;k--)
        {
            zifu[i].code[l]=cd[k];
            l++;
        }
        zifu[i].code[l]='\0';
        l=0;
        i++;
    }
	start=0;
 	for(i=0;i<all;i++)
	{
	    for(j=1;j<=all;j++)
		if(zifu[j].ch==word[i]) break;
		for(k=0;;k++)
		{
			if(zifu[j].code[k]=='\0') break;
			word_code[start]=zifu[j].code[k];
			start++;
		}
        word_code[start]='\0';
	}
	printf("请输入你的中介文件名:");
	scanf("%s",filename1);
	if((fp=fopen(filename1,"w"))==NULL)
	{
		printf("不能打开文件!");
	}
	fputs(word_code,fp);
}
void yima(char *word_code,int Huffman_num)
{
    FILE *fpa;
    int k;int i=0;
    char ch;char filename2[30];
    k=2*Huffman_num-1;  
    ch=word_code[i];
	printf("输入你的目的文件名:");
	scanf("%s",filename2);
    printf("The output is: ");
    if((fpa=fopen(filename2,"w"))==NULL)
    {
        printf("不能打开文件!");
    }
    while(ch!='\0')
    {       
        if(ch=='0')
            k=HuffmanTree[k].lchild;
        else
            k=HuffmanTree[k].rchild;
        if(HuffmanTree[k].lchild==0&&HuffmanTree[k].rchild==0)    
        {
			printf("%c",HuffmanTree[k].ch);
            fputc(HuffmanTree[k].ch,fpa);  
            k=2*Huffman_num-1;
        }
		i++;
        ch=word_code[i];
    }
    fclose(fpa);
}
void compare()
{
	FILE *fp1,*fp2;
	char ch1,ch2;
	char filename1[30],filename2[30];
	printf("请输入第一个文件的文件名：");
	scanf("%s",filename1);
	printf("\n");
	printf("请输入第二个文件的文件名：");
	scanf("%s",filename2);
	printf("\n");
	if((fp1=fopen(filename1,"rb"))==NULL)
	{
		printf("不能打开文件!");
		exit(1);
	}
	if((fp2=fopen(filename2,"rb"))==NULL)
	{
		printf("不能打开文件!");
		exit(1);
	}
	ch1=fgetc(fp1);
	ch2=fgetc(fp2);
	while((!feof(fp1))&&(!feof(fp2)))
	{

		if(ch1!=ch2)
		{
			printf("程序运行错误~");
			exit(1);
		}
		ch1=fgetc(fp1);
		ch2=fgetc(fp2);
	}
	if((!feof(fp1))||(!feof(fp2))) printf("程序运行错误~");
	printf("完美运行");
}