huffman树.cpp

本程序能对含有大小写英文字母、逗号、 句号、感叹号

/*
作者：李美学
学号：1050320125
单位：哈尔滨工业大学
版权：免费
创作日期：2007-5-2
程序功能：对文件进行Huffman编码和解码。
联系方式：[e-mail]
注释：本程序只能对含有大小写英文字母、逗号、
句号、感叹号，空格符和换行符的文件进行编码。
******************************************
*/

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

#define   MAX_STACK   ((1<<14) -1)                                   //定义宏最大支持16k的编码文件
struct  node                                                         //定义结构体
{ 
	char   data;                                                     //数据的字符表示形式                              
	int    weight;                                                   //定义数据的权重
	struct node  *left;                                              //在Huffman树中指向左子树的指针
	struct node  *right;                                             //在Huffman树中指向右子树的指针
	struct node  *father;                                            //在Huffman树中指向父节点的指针
};
 
struct  node  *root = NULL;                                          //定义指向Huffman树伍的根节点的指针
int     stack[MAX_STACK];                                            //数组做堆栈使用
int     top = 0;                                                     //栈顶  

struct  node leave[31] = {                                           //定义数据及权重
	{'a', 82, NULL, NULL, NULL},                                     //定义a -- z的字符及权重
	{'b', 15, NULL, NULL, NULL},
	{'c', 28, NULL, NULL, NULL},
	{'d', 43, NULL, NULL, NULL},
	{'e', 127, NULL, NULL, NULL},
	{'f', 22, NULL, NULL, NULL},
	{'g', 20, NULL, NULL, NULL},
	{'h', 61, NULL, NULL, NULL},
	{'i', 70, NULL, NULL, NULL},
	{'j', 2, NULL, NULL, NULL},
	{'k', 8, NULL, NULL, NULL},
	{'l', 40, NULL, NULL, NULL},
	{'m', 24, NULL, NULL, NULL},
	{'n', 67, NULL, NULL, NULL},
	{'o', 75, NULL, NULL, NULL},
	{'p', 19, NULL, NULL, NULL},
	{'q', 1, NULL, NULL, NULL},
	{'r', 60, NULL, NULL, NULL},
	{'s', 63, NULL, NULL, NULL},
	{'t', 91, NULL, NULL, NULL},
	{'u', 28, NULL, NULL, NULL},
	{'v', 10, NULL, NULL, NULL},
	{'w', 24, NULL, NULL, NULL},
	{'x', 2, NULL, NULL, NULL},
	{'y', 20, NULL, NULL, NULL},
	{'z', 1, NULL, NULL, NULL},
	{',', 30, NULL, NULL, NULL},                                     //定义,的字符及权重
	{'.', 20, NULL, NULL, NULL},                                     //定义.的字符及权重
	{'!', 10, NULL, NULL, NULL},                                     //定义!的字符及权重
	{' ', 162, NULL, NULL, NULL},                                    //定义空格的字符及权重
	{'\n',16, NULL, NULL, NULL}                                      //定义换行的字符及权重
};
int  n = 31;                                                         //记录数组leave[]的大小
FILE  *in, *out;                                                     //定义全局文件指针


void  zerostack( )/*堆栈清零函数*/
{
	int  i;
	
	for(i = 0; i < 80; i++)
		stack[i] = 0;
	
	top = 0;
}


void  push(int  x)/*压栈函数*/
{
	stack[top] = x;
	top++;
}


int  pop( )/*出栈函数*/
{
	if(!top)
	{
		printf("栈是空的！\n");
		return -1;
	}
	
	top--;

	return top;
}


void  printstack() /*打印堆栈内容函数*/
{
	int  i;
	
	for(i = top - 1; i >= 0; i--)
		printf("%d",stack[i]);
}


struct  node *copy(int  m) /*将数组leave[]的第m个元素的内容复制到新开辟的节点中去,返回新节点的指针*/
{
	struct  node  *p;
	
	p = (struct node *)malloc(sizeof(struct  node));                 //申请结构体指针
    
	if(p == NULL)
	{
		printf("No enough  memory !\n");
		exit(0);
	}
	
	p->data = leave[m].data;
	p->weight = leave[m].weight;
	p->left = leave[m].left;
	p->right = leave[m].right;
	p->father = leave[m].father;

	if(leave[m].left != NULL)
	(leave[m].left)->father = p;

	if(leave[m].right != NULL)
	(leave[m].right)->father = p;

	return p;
}


int  searchmin()  /*寻找数组leave[]中权最小的元素*/
{
	int  i = 0, t = 0;
	int  min = leave[0].weight;
	
	for(i = 0; i < n; i++)
	{
		if(min > leave[i].weight)
		{
			min = leave[i].weight;
			t = i;
		}  
	}

	return t;
}


void  del(int m) /*删除数组leave[]中的第m个元素*/
{
	int i;
	
	for(i = m; i < n - 1; i++)                      
	{
		leave[i] = leave[i + 1]; 
	}

	n--;
}


void  add(struct  node *p)/*在数组leave[]中加入*p所指向的结点*/
{
  	 leave[n].data = p->data;
	 leave[n].weight = p->weight;
	 leave[n].left = p->left;
	 leave[n].right = p->right;
	 leave[n].father = p->father;

	 p->left->father = &leave[n];
	 p->right->father = &leave[n];
	 
     n++;
     free(p);
}

struct  node *link(struct  node *p1, struct  node *p2)/*建立新节点,并联结p1与p2所指向的节点*/
{
   struct  node *p;
   
   p = (struct node *)malloc(sizeof(struct  node));                  //申请结构体指针
    
	if(p == NULL)
	{
		printf("No enough  memory !\n");
		exit(0);
	}

    p->left = NULL;
	p->right = NULL;

	p->left = p1;
	p1->father = p;
	p->right = p2;
	p2->father = p;
	p->data = 0;
	p->weight = (p1->weight) + (p2->weight);                         //新节点的权是两节点权的和

	return p;
}


struct  node *maketree()/*生成Huffman树,返回树的根*/
{
	int  i = 0, j = 0;
	struct  node *p, *p1, *p2;
	
	while(n >1)
	{
		i = searchmin();                                             //函数调用
		p1 = copy(i);
		del(i);

		j = searchmin();                                             //函数调用
		p2 = copy(j);
		del(j);

		p = link(p1, p2);                                            //函数调用
		add(p);
    }
	
	leave[0].father = NULL;

	return (&leave[0]);
}


struct  node *search(struct node *p,  char data) /*查找节点函数*/
{
	static  struct node *q = NULL;
	struct  node  *old;
	
	if(p != NULL)
	{
		if(p->data == data || p->data == (data + 32))                //大写字母与小写字母都一起当小写字母处理
		{
			q = p;
		}
		
		else 
		{
			q = search(p->left, data);                               //递归调用
			q = search(p->right, data);
		}
		
	}
	
	old = q;
	q= NULL;

	return old;
}


void  code(char data, int x, FILE *out )/*找到指定的节点后进行编码*/
{  
   int   i;
   char  ch;
   struct node  *old, *p;

   p = search(root, data);

   if(p == NULL)
   {
     printf("字符%c未定义!\n", data);
	 return;
   }

   old = p;
   zerostack();

   while(p->father != NULL)                                
   {
     if(p == p->father->left)
		 push(0);
   
     if(p == p->father->right)
        push(1);
    
      p = p->father;
   }
  
   if(x == 0)
   {
	   for(i = top -1; i >= 0; i--)
	   {   
		   ch = (char)(stack[i] + 48);
		   fputc(ch, out);
	   }
   }

   if(x == 1)
   { 
	   if(old->data != ' ' && old->data != '\n')                       
		   printf("\ndata = %c\tweight = %d\tcode = ", old->data, old->weight);
	   
	   else if (old->data == ' ')                                    //对空格字符的特殊处理
		   printf("\ndata = space\tweight = %d\tcode = ", old->weight);
	   
	   else                                                          //对换行字符的特殊处理
		   printf("\ndata = Enter\tweight = %d\tcode = ", old->weight);
	   
	   printstack();
   }
   
   zerostack();
}


int  trace(int x,  FILE *out)/*在堆栈中给定编码,按编码找到对应的节点,x为堆栈中编码的起始为*/
{
	struct  node *p, *old;
	int     i = x;
	
	p = root;
	
	while(p != NULL)
	{
		old = p;
		
		if(!stack[i])
			p = p->left;
		
		else
			p = p->right;
		
		i++;
		
	}
	
	fputc(old->data, out);

	return (i-1);
}


void  encode()/*编码函数*/
{
	char  ch;
	char  infile[20], outfile[20];
	
	printf("\n请输入被编码文件的文件名和存放编码文件的文件名:\n");   
	scanf("%s", infile);
	scanf("%s", outfile);
	
	in = fopen(infile, "r");
	out = fopen(outfile, "w");
	
	if(in == NULL || out == NULL)            
	{
		printf("文件打开失败!\n");
		exit(0);
	}
	
	while((ch = fgetc(in)) != EOF)
		code(ch, 0, out);

	fclose(in);                                                      //关闭文件
	fclose(out);
}


void   decode() /*解码函数*/
{
	int   x , i = 0;
	char  ch, infile[20], outfile[20];
	
	printf("\n请输入编码文件名和存放还原文件名:\n");   
	scanf("%s", infile);
	scanf("%s", outfile);
	
	in = fopen(infile, "r");
	out = fopen(outfile, "w");
	
	if(in == NULL || out == NULL)            
	{
		printf("文件打开失败!\n");
		exit(0);
	}
	
	zerostack();
	
	while((ch = fgetc(in)) != EOF)
	{
		if(ch == '0')
			push(0);
		
		else if(ch == '1')
			push(1);

		else                                                         //对换行符不做任何处理
			;
	}
	
	for(x = 0; x <top; )
		x = trace(x, out);
	
	fclose(in);                                                      //关闭文件
	fclose(out);	
}


void  view()/*打印数据项及其编码*/
{
	char ch;
	
	for(ch = 'a'; ch <= 'z'; ch++)
		code(ch, 1, NULL);
	
	code(',', 1, NULL);
	code('.', 1, NULL);
	code('!', 1, NULL);
	code(' ', 1, NULL);
	code('\n', 1, NULL);
}


char  display()
{
 char  c;

 do{
   printf("\n请选择:\n");
   printf("1---查看字符和其相应编码.\n");
   printf("2---编码文件.\n");
   printf("3---解码文件.\n");
   printf("4---退出程序.\n");
 
   c = getche();

 }while(c < '1' || c > '4');

    return c;
}


void  preorder(struct  node *root)/*遍历Huffman数*/
{
	static  struct  node *q = NULL;
	
	if(root != NULL)
	{
		if((root->data >= 'a' && root->data <= 'z' ) || root->data ==',' || root->data == '.' || root->data == ' ' || root->data =='!'  || root->data =='\n')
			printf("\ndata:%c\tweight:%d", root->data, root->weight);
		
		preorder(root->left);
		preorder(root->right);
	}
}


void  Exit()
{
	printf("\n谢谢使用!\n");
	exit(0);
}



main()
{
	char  choice;
	
	printf("欢迎使用!");
	root = maketree();
	
	while(1)
	{
		choice = display();
		
		switch(choice)
		{
		case '1':
			view();
			break;
			
		case '2':
			encode();
			printf("编码成功！\n");
			break;
			
		case '3':
			decode();
			printf("解码成功！\n");
			break;
			
		case '4':
			Exit();
			
		default:
			break;
		}
	}

	return 0;
}