课程设计.cpp

Huffman编解码器的模拟实现 应用Huffman算法实现模拟编解码器

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

typedef struct Node{           //二叉排序树中结点的结构体定义。
    char *word;                //用于存放一个单词或一个标点符号。
	int count;                 //单词或标点符号在英文文章中出现的次数。
	int len;                   //单词或标点符号长度。
	int weight;                //单词或标点符号的权值。
	struct Node *left,*right;  //结点中指向左、右孩子结点的指针。
}Node,*BiTree;                 

typedef struct node{     
    char *word;          //当前结点表示的单词或标点符号，对于非叶子结点，此域不可用。
	int weight;          //当前结点表示的单词或标点符号的权值。
	int parent;          //当前结点的父结点的下标，为0时表示无父结点。
	int lchild,rchild;   //当前结点的左、右孩子结点的下标，为0时表示无孩子结点。
}HuffmanTree[9999];      //采有一维结构数组来存储霍夫曼树。

//在二叉排序树中（T指向树根结点）查找单词或标点符号keyword，若找到，令*p指向该结点并返回0
//否则，*p指向查找路径上出现的最后一个结点并返回-1。
int searchBst(BiTree T,char *keyword,BiTree *p)
{   
	int cmpres=0;
	BiTree ptr;
	*p=0;ptr=T;
	while(ptr)
	{
		cmpres=strcmp(ptr->word,keyword);
        if(cmpres==0){*p=ptr;return 0;}
	    else{*p=ptr;ptr=cmpres>0? ptr->left: ptr->right;}
	}
	return -1;
}

//在二叉排序树中（*t指向树根结点）插入单词或标点符号为keyword的结点，若该单词结点已在树中，
//则counts增1；否则，在树中插入一个单词或标点符号为keyword的结点。
int insertBst(BiTree *t,char *keyword)
{
	BiTree s,p;
	if(searchBst(*t,keyword,&p)==-1)
	{
		s=(Node *)malloc(sizeof(Node));
		if(!s){printf("存储分配失败!\n");return -1;}
		s->word=(char *)malloc(strlen(keyword));
		s->len=strlen(keyword);
		strcpy(s->word,keyword);
		s->left=0;s->right=0;s->count=1;s->weight=s->len;
		if(p==0) *t=s;
		else if(strcmp(p->word,keyword)<0)
			    p->right=s;
		else p->left=s;
	}
	else {p->count++; p->weight=p->count*p->len;}
	return 0;
}

//从某篇英文文章中找出每一单词和标点符号，并把它们插入到二叉排序树中。
void FindWords(BiTree *root,char FileName[],char *c1[],int *counts1)
{
	char ch,*word,buffer[40],string[2]; //字符数组buffer用来存放一个单词，
	FILE *fin;                          //字符数组string用来存放一个标点符号。              
	int i=0;

	fin=fopen(FileName,"r");
	if(!fin){printf("打开文件%s错误!\n",FileName);return;}
	while(!feof(fin))
	{
		ch=fgetc(fin);
        while((!feof(fin))&&(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z'))
		{buffer[i++]=ch;ch=fgetc(fin);}
        
		if(i!=0)
        {
			buffer[i]='\0';
	        word=(char *)malloc(strlen(buffer));
		    strcpy(word,buffer);
			c1[(*counts1)++]=word;
		    if(insertBst(root,word)==-1)return;
		     i=0;
		}
		
		if((!feof(fin))&&(ch!=' '))
		{
			string[0]=ch;
		    string[1]='\0';

			word=(char *)malloc(2);
		    strcpy(word,string);
			c1[(*counts1)++]=word;
		    if(insertBst(root,word)==-1)return;
		}
        if(i!=0)
        {
			buffer[i]='\0';
	        word=(char *)malloc(strlen(buffer));
		    strcpy(word,buffer);
			c1[(*counts1)++]=word;
		    if(insertBst(root,word)==-1)return;
		     i=0;
		}
	}
	fclose(fin);

}

//中序遍历root指向根的二叉排序树,通过中序遍历二叉排序树，英文文章中的所有单词和标点符号会按照英文
//字典中单词的排列顺序依次存放在字符类型的指针数组char *c[]中，大致顺序是：标点符号排在最前面，
//然后是含有大写字母的单词按字典顺序，最后是只含有小写字母的单词按字典顺序。
void InOrder(BiTree root,char *c[],int w[],int *counts)
{
	
	if(root)
	{
	   
		InOrder(root->left,c,w,counts);
        c[*counts]=root->word; w[*counts]=root->weight; (*counts)++;
		//整形数组w[]保存英文文章中的所有单词和标点符号的权值。
		//c[i]中保存的单词或标点符号的权值就是w[i];
		//count用来统计所有不重复单词和标点符号的总个数。
        InOrder(root->right,c,w,counts);
		
		
	}
}

//从HT[0...n-1]中选择parent为0且weight最小的两棵树，其序号为s1和s2。
void select(HuffmanTree HT,int *s1,int *s2,int n)
{	

	for(int i=0;i<n;i++)
		if(HT[i].parent==0)
		    *s1=i;
    for(i=0;i<n;i++)
		  if((HT[i].parent==0)&&(HT[*s1].weight>HT[i].weight)) *s1=i;

    HT[*s1].parent=-1;  //此语句是为了让*s1!=*s2

    for(int j=0;j<n;j++)
		if(HT[j].parent==0)
		    *s2=j;
	for(j=0;j<n;j++)
		  if((HT[j].parent==0)&&(HT[*s2].weight>HT[j].weight)) *s2=j;
}

//构造霍夫曼树HT。
void createHTree(HuffmanTree HT,char *c[], int w[],int counts)
{
	int i,s1,s2;
	if(counts<=1) return;
	for(i=0;i<counts;i++) //根据counts个权值构造counts个只有根结点的二叉树。
	{	
		HT[i].word=c[i]; HT[i].weight=w[i]; //HT[i].word存放c[i],HT[i].weight存放w[i]
	    HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	}
	for(;i<2*counts-1;i++)
	{
		HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;
	}
    for(i=counts;i<2*counts-1;i++) //构造霍夫曼树
	{
        select(HT,&s1,&s2,i);  //从HT[0...i-1]中选择parent为0且weight最小的两棵树，其序号为s1和s2。
		HT[s1].parent=i;  HT[s2].parent=i;
		HT[i].lchild=s1;  HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
}

//从每个叶子结点出发追溯到树根，逆向找出霍夫曼树中叶子结点的编码，
//counts个叶子结点在霍夫曼树HT中的下标为0到counts-1,
//HC[i]存放HT[i].word的Huffman编码,也就是存放c[i]的Huffman编码。
void HuffmanCoding(HuffmanTree HT,char *HC[],char *c[],char *c1[],int counts,int counts1)
{
	char *cd;
	int i,start,cc,f;
	if(counts<=1) return;
	cd=(char *)malloc(counts);
	cd[counts-1]='\0';
	for(i=0;i<counts;i++)
	{
		start=counts-1;
		for(cc=i,f=HT[i].parent;f!=0;cc=f,f=HT[f].parent)
			if(HT[f].lchild==cc) cd[--start]='0';
			else cd[--start]='1';
		HC[i]=(char*)malloc(counts-start);
		strcpy(HC[i],&cd[start]);
	}
	free(cd);

	FILE *out;
	out=fopen("编码.txt","w");
    if(!out){printf("打开文件%s错误!\n","编码.txt");return;}
	printf("编码后的结果输出在文件：编码.txt中.\n");
	for( i=0;i<counts1;i++)
	{
	   for(int j=0;j<counts;j++)
	   {
		   if(strcmp(c1[i],c[j])==0)
			   fputs(HC[j],out);
	   }	
	}
    fclose(out);
}


//首先读取经过编码产生的编码文件(只含有字符'0'和'1'),然后用霍夫曼树进行译码，
//生成译码文件（原英文文章）。
void Decoding(HuffmanTree HT,int counts)
{
	
    int i=0;
	char ch,buffer[9999];//字符数组buffer用来存放编码文件中的所有字符。
    FILE *in;
	in=fopen("编码.txt","r");
	if(!in){printf("打开文件%s错误!\n","编码.txt");return;}
    while(!feof(in))
	{
		ch=fgetc(in);
		buffer[i++]=ch;
	}
    fclose(in);
    int j=i;
    int p=2*counts-2;
    FILE *fout;
	char null=' ';
	fout=fopen("译码.txt","w");
    if(!fout){printf("打开文件%s错误!\n","译码.txt");return;}
    printf("译码后的结果输出在文件：译码.txt中.\n");
	for(i=0;buffer[i]!='\0'&&i<j;i++)
	{
		if((buffer[i])=='0') p=HT[p].lchild;
		else p=HT[p].rchild;
		if(HT[p].lchild==0&&HT[p].rchild==0)
		{
			fputs(HT[p].word,fout);
			fputc(null,fout); //在单词(或标点符号)与单词(或标点符号)之间插入空格。
			p=2*counts-2;
		}
	}
    fclose(fout);
}

void main()
{
	BiTree root=0;
	HuffmanTree HT;
    char *c[9999];//用于保存英文文章中的所有单词和标点符号，不保存重复的单词和标点符号，每个数组元素
			      //保存一个单词或一个标点符号。

    int w[9999];  //用于保存英文文章中的所有单词和标点符号的权值，不保存重复的单词和标点符号的权值，
			      //即：w[i]保存c[i]的权值，权值的计算公式为：权值=单词的长度*单词在文章中出现的频率。

	char *c1[9999];//用于保存英文文章中的所有单词和标点符号，保存重复的单词和标点符号，每个数组元素保
			       //存一个单词或一个标点符号，并且按照单词或标点符号在文章中出现顺序来存储，c1[0]保存
                   //英文文章中的第一个单词或标点符号，即：c1[i]保存英文文章中的第i+1个单词或标点符号。

    int counts=0;   //用来统计所有单词和标点符号的总个数，不包括重复的单词和标点符号。

    int counts1=0;  //用来统计所有单词和标点符号的总个数，包括重复的单词和标点符号。

    char* HC[9999];//用来保存所有单词和标点符号的Huffman编码，不包括重复的单词和标点符号的Huffman编码，
                   //即：HC[i]保存c[i]的Huffman编码。

	char FileName[40];
	printf("请输入要进行霍夫曼编码的英文文章的文件名：");
	gets(FileName);
	FindWords(&root,FileName,c1,&counts1); //从某篇英文文章中找出每一单词和标点符号，并把它们插入到二叉排序树中。
	InOrder(root,c,w,&counts);       //中序遍历root指向根的二叉排序树。
    createHTree(HT,c,w,counts);     //构造霍夫曼树HT。
    HuffmanCoding(HT,HC,c,c1,counts,counts1);  //从每个叶子结点出发追溯到树根，逆向找出霍夫曼树中叶子结点的编码。
	Decoding(HT,counts);        //利用霍夫曼树进行译码。
}