hafuman.cpp

是数据结构的作业

#include "stdio.h"
#include "stdlib.h"       
#include "string.h"
#include "conio.h"

#define  MAXSIZE 60

/************************************定义赫夫曼树结构体*******************************************/

typedef struct
{
	float  weight;
	unsigned  int parent, lchild, rchild;
}HTNode, *HuffmanTree;
typedef char **HuffmanCode ;

/************************************************定义堆结构体**********************************************************/

typedef struct
{
	float key;                           //关键字项
	int otherinfo;                       //其他数据项（此题目中用不到）
}RedType;    

typedef struct
{
	RedType  r[MAXSIZE+1];               //r[0]闲置用作哨兵
	int   length;                        //顺序表长度
}SqList;

/**************************************************全局变量*************************************************************/

HuffmanTree HT;                          //赫夫曼树
HuffmanCode HC;                          //码值

 FILE  *fp, *fp1, *fp2;
int   a[30] = {0};
float b[30];
float *w;                                //权

/****************************************测试解码（可以输入一个不正确的二进制码串）**************************************/

void testdecode()  	
{   
	char str[200];                        //存放自己输入的码子
	int p, p1, i;                         //解码的线索
	char ch;
	
	printf("\n请根据以上各个字符的编码输入一串二进制码字(200个以内):\n");
	gets(str);

	printf("以上码子解码后为:\n");

	p = 59;                                //最初令p为树根整数，p由根顺着树枝一直到树叶
 
	i = 0;
	
	ch = str[i++];
  
	 while (ch!='\0')
	 {
	
		for ( ; ch!='\0' && (HT[p].lchild!=0||HT[p].rchild!=0) ; )          
		{
			if (ch == '0')
			{ 
			  p = HT[p].lchild; 
			   
			}
		
			else if(ch == '1')
			{ 
			  p = HT[p].rchild;
			}

			else
			{
			  printf("\n你输入了'0','1'之外的字符，无法正确译码，请检查 !\n");
			  return ;                      //直接结束
			}

			ch = str[i++];                  //下一个码字 不断的取下一个 
		}
	   
	   
	   if(p <= 30)                          //小于等于30的时候才正确，有可能最后一位p还没有在1-30范围内的时候就没有二进制码了，也就是说二进制码最后不完整。
	   switch (p)
	   { 
	         case 27 : printf(",");
		               break;
			
			 case 28 : printf(".");
					   break;
					  
			 case 29 : printf(" ");
					   break;
			 
			 case 30 : printf("\n");
					   break;
			 
			 default : printf("%c", p+96);
					   
	  }
      
	   p1 = p;                                 //让p1记住p
	   
	   p = 59;                                 //这里p要重置为59，因为经过上面的程序p已经变化了，不重置为1则HT[p].lchild!=0||HT[p].rchild!=0所以for语句无法进行!!!! 
	   
	}                                          //while循环
    
	  if (p1 > 30) 
	 	printf("\n以上正确译出了前面的字符，由于你输入的二进制码不完整，最后一位字符无法译出，请检查!\n");
}

/*******************************************下面是解码*********************************************************/

 void decode()   
{	
	int p;
	char ch;

	printf("\n\n对码子解码后的如下:\n");

	fp1 = fopen("bianma.txt","r");
	if(!fp1)
	{
		printf("can not open this file!\n");
		exit(0);
	}
	
 
	p = 59;                                  //最初令p为任意一个非零整数，p由根顺着树枝一直到树叶
	
	ch = fgetc(fp1);
    
	fp2 = fopen("jiema.txt","w");
	if (!fp2)
	{
		printf("can not open this file!\n");
		exit(0);
	}
	
	while (ch!=EOF)
	{
	
		for ( ; HT[p].lchild!=0||HT[p].rchild!=0 ; )          
		{
			if (ch == '0')
			{ 
			  p = HT[p].lchild; 
			   
			}
		
			else 
			{ 
			  p = HT[p].rchild;
			   
			}

			ch = fgetc(fp1);                  //下一个码字 不断的取下一个 
		}
	
	   switch (p)
	   { 
	         case 27 : printf(",");
		               fprintf(fp2,",");
			           break;
			
			 case 28 : printf(".");
					   fprintf(fp2, ".");
					   break;
			 
			 case 29 : printf(" ");
					   fprintf(fp2, " ");
					   break;
			 
			 case 30 : printf("\n");
					   fprintf(fp2, "\n");
					   break;
			 
			 default : printf("%c", p+96);
					   fprintf(fp2, "%c", p+96);
	 }

	   
	   
	   p = 59;                                  //这里p要重置为59，因为经过上面的程序p已经变化了，不重置为1则HT[p].lchild!=0||HT[p].rchild!=0所以for语句无法进行!!!! 
	   
	}  //while循环

	printf("\n");
	fprintf(fp2, "\n");

	fclose(fp1);
	fclose(fp2);
}

/*******************************************求最小权值*********************************************************/
	
void minweight()	
{  
	float Weight = 0;
	int i;
   
	for (i = 0 ; i < 30 ; i++)
	  Weight = Weight + strlen(HC[i+1])*b[i];

      printf("最小权值是:%f\n",Weight); 
}

/*******************************************打印码子**********************************************************/

void printcode()
{   
	char ch;
	fp = fopen("Huffman.txt","r");
	if (!fp)
	{
		printf("can not open this file!\n");
		exit(0);
	}

	fp1 = fopen("bianma.txt","w");
	if (!fp1)
	{
		printf("can not open this file!\n");
		exit(0);
	}

 
    printf("\n原英文文章经编码后如下:\n");
 
	ch = fgetc(fp);
	while (ch!=EOF)
	{
	    if (ch > 96 && ch < 123)                    //小写字母   
		{
		   printf("%s", HC[ch-96]);
		   fputs(HC[ch-96], fp1);                   //输出到文件里面
		   ch = fgetc(fp);
		   continue;
		}		   
	
		if (ch > 64 && ch < 91)                     //大小字母
		{
		   printf("%s", HC[ch-64]);
		   fputs(HC[ch-64], fp1);                   //输出到文件里面
		   ch = fgetc(fp);
		   continue;
		}
		
		if (ch == ',')
		{
			printf("%s", HC[27]);
			fputs(HC[27], fp1);
			ch = fgetc(fp);
			continue;
		}
		
		if (ch == '.')
		{
			printf("%s", HC[28]);
			fputs(HC[28], fp1);
			ch = fgetc(fp);
			continue;
		}
		
		if (ch == ' ')
		{
			printf("%s", HC[29]);
			fputs(HC[29], fp1);
			ch = fgetc(fp);
			continue;
		}
		
		if (ch == '\n')
		{
			printf("%s", HC[30]);
			fputs(HC[30], fp1);
			ch = fgetc(fp);
			continue;
		}
		
	 }
	
	printf("\n\n");
    
	fclose(fp);
	fclose(fp1);
}

/*****************************************堆排序****************************************************/

void  HeapAdjust(SqList &L, int s, int m)
{
	RedType rc;
	int j; 
	
	rc = L.r[s];
	for (j = 2 * s ; j <= m ; j*=2)
	{ 
		if (j < m && L.r[j].key > L.r[j+1].key) //即使等于也不要动，不用加1
			++j;
		
		if (rc.key <= L.r[j].key)               //即使等于也不要动，直接跳出来
			break;
		
		L.r[s] = L.r[j];
		s = j;
	
	}
	
	L.r[s] = rc;
}