hash.txt

线性探测再散列

#include<stdio.h>
#define L  10
#define true 1
#define false 0
typedef struct
{ int num[L];
  int count;
}HashTable;
typedef struct
{ int key;
}Record;
int InitiaHash(HashTable &H) /*初始化哈希表*/
{ int i;
	for(i=0;i<L;i++)
    H.num[i]=0;
  for(i=0;i<L;i++)
	printf ("%5d",H.num[i]);
  printf("\n");
  return true;
}
 int Hash(int n)   /*哈希函数设计*/
 {int m;
 m=n%L;
 return m;}
  
int LineInsertHash(HashTable &H,int key)  /*哈希表插入值，用线性探测再散列解决冲突*/
 { int loc,flag=0;
  /* float avg;*/
   loc=Hash(key);
   H.count=0;
   while (H.count<L&&flag==0)
   {if (H.num[loc]==0)
   {  H.num[loc]=key;
      flag=1;
	  H.count++;
      printf ("InsertHase is sucessful\n");}
     else if (loc<L)
		 loc++;
	 else 
		 loc=0;
    /*count++;*/
}
   if (H.count>L)
   { printf("the hashtable is full\n");
     printf("InsertHase is not sucessful\n");
     return false;}
  /*printf ("The avg is %f\n",count/L);*/
  return true;
}
int LineSearchHash (HashTable &H,int key)  /*线性探测再散列进行查询*/
{int loc,flag=0;
 loc=Hash(key);
 H.count=0;
 while (H.count<L && flag==0)
 {if (H.num[loc]=key)            /*查找成功*/
   {printf("Search is sucessful\n");
    printf("the key's position is %d\n",loc);
    flag=1;}
  else if(loc<L)
    {loc++;
    H.count++;}
   else 
      loc=0;}
if(H.count>=L)
{printf("The key is not in the HashTable\n");
return false;}
else
 return true;
}
/*int InsertHash (HashTable &H,int R.key)   哈希表插入值，用二次探测再散列解决冲突*/


void print (HashTable &H)    /*输出哈希表*/
 { int i;
  for (i=0;i<L;i++)
     printf("%5d",i);
  printf("\n");
  for (i=0;i<L;i++)	  
     printf("%5d",H.num[i]);
  printf("\n");
 }

 void  main()   /*主函数*/
 { 
   int key,j,i;
   HashTable H;
   Record R ;
   InitiaHash(H);
  while (i!=10)
  {  printf("*****************menu****************\n");
     printf ("\t1:LineInsertHash\t2:LinesearchHash\n");
     printf ("\t3:InsertHash\t4:SearchHash\n");
     printf ("\t5:print\n");
     printf ("*************************************\n");
     
     printf("please input action you  want\n");
     scanf ("%d",&j);  
	
     switch (j)
	 {case 1 : printf ("please input you want to insert\n");
               scanf ("%d",&R.key); 
	           LineInsertHash (H,R.key); break;
      case 2 : scanf("%d",&key);
		       LineSearchHash(H,key); break;
 
	  case 3 : print(H); break; 
	  default : i=10 ;
	 }
   }
 }