hash.c

hash表操作,提供表中查找插入操作,并比较相同关键字下HASH长度为多少时最好.

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

int max; 

typedef struct node                                                  //Hash表
{  char s[20];
   int num,time;
}node;

typedef struct nod                                                   //二叉排序树
{   char s[20];
	struct nod *left,*right;
}nod;

nod *creat();
void init(node *head);
void deal(node *head,nod *parent,char filename[]);
void strcp(node *head,char s[],int k);
void strdeal(node *head,char s[],int k);
int strcmp(char t[],char s[]);
void prin(nod *head);
int search(char s[],nod *parent);

void main()                                                          //主函数
{
   FILE *op,*fp;
   node *head;                                                       //Hash表头指针
   nod *parent;                                                      //二叉树头指针
   char filename[50],sourcename[50];
   char s[50]="D://scy//write1.txt";                                 //数据保存文件基名
   char t[50]="D://scy//scy//1.c";                                   //源扫描文件基名
   char c='%';
   int i,j,k,p,q,r;
   int num[5],time[5];                                               //分别保存频数冲突次数
   float ave,f;                                                      //ave保存冲突百分比
   if((fp=fopen("D://scy//final.txt","at"))==NULL)
	      exit(1);
   parent=creat();                                                   //建二叉排序树
   prin(parent);                                                     //左根右打印二叉树
   fprintf(fp,"模取值\t\t关键字<100\t关键字<200\t关键字<300\t关键字<500\t关键字<1000\t平均\n");
   fprintf(fp,"        \tNUM TIME  \tNUM TIME  \tNUM TIME  \tNUM TIME  \tNUM TIME\n",max);
   for(max=38;max<50;max++)
   {  ave=0.0;
      for(i=0;i<5;i++)
     num[i]=time[i]=0;
      head=(node *)malloc(max*sizeof(node));                         //申请Hash存储空间
	  if(head==NULL) exit(1);
	  fprintf(fp,"%d  ",max);
      for(p=0;p<5;p++)
	  {  
	      init(head);                                                //Hash表节点数据初始化
	      for(q=r=0;s[q]!='\0';r++,q++)                              //变更数据保存文件名
		  {  if(s[q]!='1')
		       filename[r]=s[q];
	         else
			 {
			    filename[r++]='0'+1+p;
			    filename[r++]='-';
				filename[r++]=max/10+'0';
				filename[r]=max%10+'0';

			 }
		  }
          filename[r]='\0';
	      for(q=0;t[q]!='\0';q++)                                    //变更源文件名
		  {  if(t[q]!='1')
		       sourcename[q]=t[q];
	         else
			   sourcename[q]='1'+p;
		  }
          sourcename[q]='\0';
          if((op=fopen(filename,"w"))==NULL)
	         exit(1);
       
          deal(head,parent,sourcename);                              //扫描源文件
          fprintf(op,"HASH序号\t关键字\t\t频数\t冲突数\n");
          for(i=j=k=0;i<max;i++)
		  {
	         if(head[i].s[0]!='\0')                                  //写入中间数据保存文件
			    fprintf(op,"%-10d\t%-10s%8d\t%d\n",i,head[i].s,head[i].num,head[i].time);
             j+=head[i].num;
	         k+=head[i].time;
		  }
	      num[p]=j;
	      time[p]=k;
	      f=k;
	      f/=j;
	      ave+=f;
          fprintf(op,"\n");
          fprintf(op,"总关键字数：%d\n",j);
          fprintf(op,"总冲突数：%d\n",k);
          fprintf(op,"\n");
          fclose(op);
	      fprintf(fp,"      \t%d  %d",num[p],time[p]);
	  }
      fprintf(fp,"\t%5.2f%c\n",ave*20,c);                            //写入总冲突百分比
      printf("%d\n",max);
   }
   fclose(fp);
}

nod *creat( )                                                        //根据关键字建二叉树
{  FILE *op;
   nod *head,*cursor,*temp;
   int i;
   if((op=fopen("D://scy//关键字.txt ","r"))==NULL)
	   exit(1);
   head=(nod *)malloc(sizeof(nod));
   if(head==NULL) exit(1);
   fscanf(op,"%s ",head->s);
   head->left=head->right=NULL;
   temp=head;
   cursor=(nod *)malloc(sizeof(nod));
   while(fscanf(op,"%s ",cursor->s)!=EOF)
   {  cursor->left=cursor->right=NULL;
      for(i=0;i=strcmp(temp->s,cursor->s);)                          //字符串比较
	  {
		  if(i>0)
		  {  if(temp->left!=NULL) temp=temp->left;
		     else temp->left=cursor;
		  }
	      else
		  {  if(temp->right!=NULL)  temp=temp->right;
		     else temp->right=cursor;
		  }
	  }
	  cursor=(nod *)malloc(sizeof(nod));
	  temp=head;
   }
   fclose(op);
   return(head);
}

void init(node *head)                                                //初始化Hash表数据
{  
   int i;
   for(i=0;i<max;i++)
   {  head[i].num=head[i].time=0;
      head[i].s[0]='\0';
   }
}

void deal(node *head,nod *parent,char filename[])                    //扫描源文件更改Hash表
{  FILE *fp;
   int i,j,q,k;
   char s[500];
   char t[20];
   if((fp=fopen(filename,"r"))==NULL)
	   exit(1);
   while(fscanf(fp,"%s ",s)!=EOF)
   {
	   for(j=0;s[j]!='\0';)                                          //分离字符串中单词
	   {
		   for(i=j;('z'<s[i]||s[i]<'a')&&s[i]!='\0';i++);
	       for(q=0;s[i]!='\0'&&'z'>=s[i]&&s[i]>='a';i++,q++)
               t[q]=s[i];
		   t[q]='\0';
		   if(search(t,parent)==0)                                   //查找是否为关键字
		   {  k=(((t[0]-'a')*100+t[--q]-'a')%max+max)%max;           //计算key值
		      strdeal(head,t,k);                                     //更改Hash数据
		   }
		   j=i;
	   }      
   }
   fclose(fp);
}

void strcp(node *head,char s[],int k)                                //数据复制
{  int i;
   for(i=0;s[i]!='\0';i++)
   {  head[k].s[i]=s[i];
   }
   head[k].s[i]='\0';
   head[k].num=1;
}

void strdeal(node *head,char s[],int k)                              //将关键字适当插入Hash
{   int i;
    if(head[k].num==0) strcp(head,s,k);
	else
	{  i=strcmp(head[k].s,s);
	   if(i==0)  head[k].num++;
	   else {  head[k].time++;k=(++k)%max;strdeal(head,s,k);}        //线性探测递归调用
	} 
}

int strcmp(char t[],char s[])                                        //字符串比较
{  int i;
   for(i=0;t[i]==s[i]&&t[i]!='\0'&&s[i]!='\0';i++);
   if(t[i]!='\0'||s[i]!='\0') return(t[i]-s[i]);
   return(0);
}

void prin(nod *head)                                                 //左根右打印二叉排序树
{  
   if(head==NULL) return;
   prin(head->left);
   printf("%s\n",head->s);
   prin(head->right); 
}

int search(char s[],nod *parent)                                     //查询是否为关键字
{  nod *cursor;
   int i;
   cursor=parent;
   for(;cursor!=NULL;)
   {  i=strcmp(s,cursor->s);
      if(i==0) return(0);
	  if(i>0) cursor=cursor->right;
	  else  cursor=cursor->left;
   }
   return(-1);
}