hfmheader.h

问题描述： 设计哈希表实现电话号码查询系统。 基本要求： 1、设每个记录有下列数据项：电话号码、用户名、地址； 2、从键盘输入各记录

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

#define MAXSIZE 100
#define N 27



typedef struct { 
	    char ch;
unsigned int weight; 
unsigned int parent,lchild,rchild; 
}HTNode,*activeHuffmanTree; 

typedef char *HuffmanCode; 

/*
void Select(activeHuffmanTree HT,int n);
int Save(HuffmanCode HC[],char name[],int n);
void createHuffmanTree(activeHuffmanTree &HT, HuffmanCode HC[], int *w, char *ch,int n);
void activeHuffmanCoding(activeHuffmanTree &HT, HuffmanCode HC[], int *w,char *ch ,int n) ;
void activeTest(activeHuffmanTree &HT, HuffmanCode HC[]);
int FileCoding(activeHuffmanTree HT, HuffmanCode HC[]);
int FileDecoding(activeHuffmanTree HT, HuffmanCode HC[],int n);
void staticTest(HTNode HT[], HuffmanCode HC[]) ;
*/
int m,s1,s2; 

void Select(activeHuffmanTree HT,int n) { 
int i,j; 
for(i = 1;i <= n;i++) 
if(!HT[i].parent){s1 = i;break;} 
for(j = i+1;j <= n;j++) 
if(!HT[j].parent){s2 = j;break;} 
for(i = 1;i <= n;i++) 
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; 
for(j = 1;j <= n;j++) 
if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j; 
} 


int Save(HuffmanCode HC[],char name[],int n){
	FILE *fp;
	if((fp=fopen(name,"w"))==NULL)
		printf("文件打开失败！");
	for(int i=0;i<n;i++)
		fprintf(fp,"%s",HC[i+1]);
	return 0;
}

void createHuffmanTree(activeHuffmanTree &HT, HuffmanCode HC[], int *w, char *ch,int n){

int i; 


if (n<=1) return; 
m = 2 * n - 1; 
HT = (activeHuffmanTree)malloc((m+1) * sizeof(HTNode)); 
for (i=1; i<=n; i++) {
HT[i].weight=w[i-1];
HT[i].ch=ch[i-1];
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 
for (i=n+1; i<=m; i++) { 
HT[i].weight=0; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 

for (i=n+1; i<=m; i++) { 
Select(HT, i-1); 
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; 
 
} 
}

void activeHuffmanCoding(activeHuffmanTree &HT, HuffmanCode HC[], int *w,char *ch ,int n) 
{ 
int i; 
char *cd; 
int p; 
int cdlen; 

createHuffmanTree(HT,HC, w, ch,n);

//------无栈非递归遍历哈夫曼树，求哈夫曼编码-------------//// 

cd = (char *)malloc(n*sizeof(char)); 
p = m; cdlen = 0; 
for (i=1; i<=m; ++i)
HT[i].weight = 0; 
while (p) { 
if (HT[p].weight==0) { 
HT[p].weight = 1; 
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } 
else if (HT[p].rchild == 0) { 
HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); 
cd[cdlen] ='\0'; strcpy(HC[p], cd); 
} 
} else if (HT[p].weight==1) { 
HT[p].weight = 2; 
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; } 
} else { 
HT[p].weight = 0; p = HT[p].parent; --cdlen; 
} 
} 
} 








void activeTest(activeHuffmanTree &HT, HuffmanCode HC[]){
	int n=3;
	int i;
	char *c;
	int *w;
    puts("\n====================================");
	printf("请输入编码字符个数：");
	scanf("%d",&n);	
	fflush(stdin);
	w=(int *)malloc(n*sizeof(int));
    c=(char *)malloc(n*sizeof(char));
   
    printf("\n请输入编码的字符串：");
    gets(c);
	fflush(stdin);
	printf("\n请依次输入字符权值：");
	for(i=0;i<n;i++)
		scanf("%d",&w[i]);
	fflush(stdin);
	activeHuffmanCoding(HT,HC,w,c,n);
	printf("\n编码完成，结果如下：\n");
	puts("\n====================================");
	puts("      字符   编码            权 值"); 
    for(i = 0;i <n;i++)
	{  

	printf("%8c     :%-12s   (%-3d)\n",c[i],HC[i+1],w[i]); 
	} 


	Save(HC,"Yours.txt",n);
	puts("====================================");



}


int FileCoding(activeHuffmanTree HT, HuffmanCode HC[]){
	FILE *fp,*fp1;
	char ch;
	char name[20];
	char c[27]={' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
	int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
	printf("\n请输入文件名（测试文件：test.txt）：");
	scanf("%s",name);
	fflush(stdin);
    if((fp=fopen(name,"r"))==NULL)
	{
	   printf(" 文件打开失败！\n");
	   exit(1);
	   }



    printf("原文如下：\n");
	puts("===============================================================================\n");
    ch=fgetc(fp);
	while(ch!=EOF)
	{	 
	 putchar(ch);
	 ch=fgetc(fp);
	}
	puts("\n===============================================================================\n");
	fclose(fp);

	activeHuffmanCoding(HT,HC,w,c,27); 

	if((fp=fopen(name,"r"))==NULL)
	{
	   printf(" 文件打开失败！\n");
	   exit(1);
	   }
	if((fp1=fopen("coding.cod","w"))==NULL)
	{
	   printf(" 文件打开失败！\n");
	   exit(1);
	   }

	  printf("编码如下：\n");
	  puts("===============================================================================\n");
	  ch= tolower(fgetc(fp));
	while(ch!=EOF)
	{
	
     if(ch==10)
     {
		 putchar(10);
		 fputc(10,fp1);
	 }
	 else 
		 if(ch==' ')
		 {
	    	printf("%s",HC[1]);
			fprintf(fp1,"%s",HC[1]);
		 }

	 else
		 if(ch>96&&ch<123)
		 {
		   printf("%s",HC[ch-95]);
		   fprintf(fp1,"%s",HC[ch-95]);
		 }

	 else
	 {
		putchar(ch);
		fputc(ch,fp1);
	 }
		
	 ch=tolower(fgetc(fp));

	}
    fclose(fp1);
	puts("\n===============================================================================\n");
	puts("文件已保存至\"coding.cod\"\n");
	fclose(fp);
	


	return 0;
}

int FileDecoding(activeHuffmanTree HT, HuffmanCode HC[]){
    int p=2*N-1;
    FILE *fp;
	char ch;
	char name[20];
	char c[27]={' ','a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
	int w[27]={186,64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};
	int change=0;
	printf("\n请输入文件名（测试文件：coding.cod）：");
	scanf("%s",name);
	fflush(stdin);
    if((fp=fopen(name,"r"))==NULL)
	{
	   printf(" 文件打开失败！\n");
	   exit(1);
	   }


    printf("原码如下：\n");
	puts("===============================================================================\n");
    ch=fgetc(fp);
	while(ch!=EOF)
	{	 
	 putchar(ch);
	 ch=fgetc(fp);
	}
	puts("\n===============================================================================\n");
	fclose(fp);

	createHuffmanTree(HT,HC,w,c,27);

	if((fp=fopen(name,"r"))==NULL)
	{
	   printf(" 文件打开失败！\n");
	   exit(1);
	   }
	  printf("译文如下：\n");
	  puts("===============================================================================\n");
	  ch= fgetc(fp);

while(ch!=EOF){
       if(ch=='0') 
         p=HT[p].lchild;
       else 
		   if(ch=='1') 
         p=HT[p].rchild;
	   else 
		   if(ch==10||ch=='.'||ch=='?')
	   {
		  putchar(ch);
		  change=1;
	   }
	  else
		putchar(ch);

       if(p<=N)
	   {
				if(change)
				{
				 printf("%c",toupper(HT[p].ch));
				 change=0;
				 }
				 else
				 printf("%c",HT[p].ch);
 
             p=2*N-1;
	   }
      ch=fgetc(fp);
}

fclose(fp);

	puts("\n===============================================================================\n");
	
	return 0;

}


void staticTest(HTNode HT[], HuffmanCode HC[]) 
{ 
int i,n; 
char w[MAXSIZE],c[MAXSIZE];
char cd[MAXSIZE]; 
int p; 
int cdlen; 
   puts("\n====================================");
	printf("请输入编码字符个数：");
	scanf("%d",&n);
	fflush(stdin);
   while(n>MAXSIZE)
   {
    printf("\n数据过大，重新输入：");	
	scanf("%d",&n);
	getchar();
   }

    printf("\n请输入编码的字符串：");
    gets(c);
    fflush(stdin);
	printf("\n请依次输入字符权值：");
	for(i=0;i<n;i++)
		scanf("%d",&w[i]);
	fflush(stdin);


if (n<=1) return; 
m = 2 * n - 1; 

for (i=1; i<=n; i++) {
HT[i].ch=c[i-1]; 
HT[i].weight=w[i-1]; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 
for (i=n+1; i<=m; i++) { 
HT[i].weight=0; 
HT[i].parent=0; 
HT[i].lchild=0; 
HT[i].rchild=0; 
} 

for (i=n+1; i<=m; i++) { 
Select(HT, i-1); 
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; 
 
} 

//------无栈非递归遍历哈夫曼树，求哈夫曼编码-------------//// 

p = m; 
cdlen = 0; 
for (i=1; i<=m; ++i) 
HT[i].weight = 0; 
while (p) { 
   if (HT[p].weight==0) { 
      HT[p].weight = 1; 
   if (HT[p].lchild != 0)
   { 
	   p = HT[p].lchild; cd[cdlen++] ='0'; 
   } 
   else 
	   if (HT[p].rchild == 0) { 
        HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); 
        cd[cdlen] ='\0'; strcpy(HC[p], cd); 
	   } 
   } 
   else if (HT[p].weight==1) { 
         HT[p].weight = 2; 
if (HT[p].rchild != 0) { 
	p = HT[p].rchild; cd[cdlen++] ='1'; 
} 
   } 
   else { 
        HT[p].weight = 0; p = HT[p].parent; --cdlen; 
   } 
} 
	printf("\n编码完成，结果如下：\n");
	puts("\n====================================");
	puts("      字符   编码            权 值"); 
    for(i = 0;i <n;i++)
	{  
//	fprintf(fp,"%s ",HC[i]);
	printf("%8c     :%-12s   (%-3d)\n",c[i],HC[i+1],w[i]); 
	} 
	puts("====================================");
} 



int Meum(){
	int choice;
	puts("     \n\t=========================================================\n");
	puts("                       〓〓〓 哈夫曼编/译码器 〓〓〓\n  ");
	puts("     \t=========================================================\n");
	printf("     \t\t\t0-------------关于本系统信息\n\n");
	printf("     \t\t\t1-------------静态哈夫曼编码\n\n");
	printf("     \t\t\t2-------------动态哈夫曼编码\n\n");
	printf("     \t\t\t5-------------退出哈夫曼系统\n\n");
	puts("     \t==========================================================\n");
	printf("\t\t\t\t请选择: ");
	scanf("%d",&choice);
	fflush(stdin);
	return choice;
}

void SystemInfo(){
	FILE *fp;
	if(!(fp=fopen("系统信息.txt","r")))
	{
		puts("说明文件丢失！");
			return ;
	}
	puts("\n\n\n\n");
	puts("--------------------------------------------------------------------------------");
	puts("                          〓〓〓 系统信息 〓〓〓\n  ");
	puts("--------------------------------------------------------------------------------");	
	while(!feof(fp))
		putchar(fgetc(fp));
	
	putchar(10);
	puts("--------------------------------------------------------------------------------");
}