hash.c

利用Hash技术统计单词的频度。扫描一个C源程序

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

#define M 41                                /*hash的模,可以就此修改*/

char str[41][10]=
{   "asm","break","case","cdecl","char","const","continue",
    "default","do","double","else","enum","extern","far",
	"float","for","goto","huge","if","int","interrupt",
    "long","near","pascal","register","return","short","signed",
    "sizeof","static","struct","switch","typedef","union","unsigned",
	"void","volatile","while"
};

typedef struct node
{
	char *key;
	int fre;
	int cnflct;
	int flag;
}NODE;                                                 //哈希结点

NODE h[M];                                             //哈希表结构

int i=0; 
void stat(char filename[]);                            //对指定文件进行操作
int depart(FILE *fp,char a[]);                        // 从一个大字符串中分解单词
int letter(char c);                                    //验证是否是字母（小写）
int bin_search(char a[]);                              //识别是否是关键词（采用折半查找法）
int hash(char a[]);                                    //Hash函数，解决冲突，统计冲突次数
void inhash(char a[],int address);                     //插入Hash表，或调整Hash表项中的频度
void PrintHash(char dataname[]);                       //输出Hash表，关键词总数，冲突次数


void main()
{
  /*  int j;                                //测试已知文件
	char filename[12][15]={"ALLOC.H","ASSERT.H","FCNTL.H","FLOAT.H","GRAPHICS.H","PROCESS.H","STRING.H","TIME.H",
	"_STRSTRE.CPP","ADDIN.CPP","ASP.CPP","COMPREG.CPP"};
	char dataname[12][15]={"ALLOC.data","ASSERT.data","FCNTL.data","FLOAT.data","GRAPHICS.data","PROCESS.data",
		"STRING.data","TIME.data",	"_STRSTRE.data","ADDIN.data","ASP.data","COMPREG.data"};
	for(j=0;j<12;j++)
	{	
        i=0;
	    stat(filename[j]);
	    PrintHash(dataname[j]);
	}
  */  
	char filename[10];                      //自己输入许统计的文件
	printf("filename:\n");
	scanf("%s",filename);
       stat(filename);
	   i=0;
	    PrintHash("1.data");
 
}

void stat(char filename[])
{	int address;char a[20];FILE *fp;
	if((fp=fopen(filename,"r"))==NULL)
    {  puts("\n\nThis file can not be opened!");
       exit(0); }
    while(depart(fp,a))  
	    if(bin_search(a))
		{	
			address=hash(a);
		    inhash(a,address);
		}
	fclose(fp);
}


int depart(FILE *fp,char a[])
{
	int tmp_i=0,tmp_k,a_i; char tmp[20];
	if(fscanf(fp,"%c",&tmp[tmp_i])==-1)return(0);i++;
	while(letter(tmp[tmp_i])==0)
    {
		tmp_i++;if(fscanf(fp,"%c",&tmp[tmp_i])==-1)return(0);i++;
	}                                                                                                         
	tmp_k=tmp_i;
	while(letter(tmp[tmp_i]))
    {
		tmp_i++;if(fscanf(fp,"%c",&tmp[tmp_i])==-1)return(0);i++;
	}
	for(a_i=0;tmp_k<tmp_i;tmp_k++,a_i++)a[a_i]=tmp[tmp_k];
	a[a_i]='\0';
    return (1);
}

int letter(char c)
{
	if(c<='z'&&c>='a')return 1;
	else return 0;
}
int bin_search(char a[])
{ int low,high,mid;
  low=0;high=M-1;
  while(low <= high)
  { mid=(low+high)/2;
    if(strcmp(a,str[mid])==0) return(mid);
    if(strcmp(a,str[mid])==-1) high=mid-1;
                          else low=mid+1;
  }
  return(0);
}


int hash(char a[])
{
	int i,tmp=0,first,last,result;
	first=a[0]-'a';
	for(i=0;a[i]!='\0';i++);
	last=a[i-1]-'a';
    result=(first*100+last)%M;
	h[result].cnflct=0;
	while(h[result].flag==1&&strcmp(h[result].key,a)!=0)
	{  
		if(result<M-2)
		  result++;
		else result=0;               
	    tmp++;
	}
	h[result].cnflct+=tmp;
	return(result);	
}

void inhash(char a[],int address)
{
	if(h[address].flag==1)h[address].fre++;
    else 
	{   h[address].key=malloc(10*sizeof(char));
	    strcpy(h[address].key,a);
     	h[address].fre=1;
        h[address].flag=1;
	}
}

void PrintHash(char dataname[])
{
	int j,keyc=0,cnflctc=0;FILE *fp;
    fp=fopen(dataname,"w");		
	for(j=0;j<M;j++)
		fprintf(fp,"%d,%s,fre:%d,conflict:%d\n",j,h[j].key,h[j].fre,h[j].cnflct);
	for(j=0;j<M;j++)
		if(h[j].flag==1)
		{	keyc+=h[j].fre;
		    cnflctc+=h[j].cnflct;
        }
	fprintf(fp,"关键字总数：%d\n",keyc);
	fprintf(fp,"冲突次数：%d\n",cnflctc);
	fclose(fp);
}