sy8_3.c

数据结构实验与学习指导

/*  sy8_3.c  */
#include"stdlib.h"
#include"stdio.h"
#define NULL 0
typedef int KeyType ;
typedef struct{
  KeyType key;
}ElemType;
int Haxip(int m)  /*求小于等于m的质数p*/
 {int i,p,flag;
  for(p=m;p>=2;p--)
   { for(i=2,flag=1;i<=p/2&&flag;i++)
     if(p%i==0) flag=0;
     if(flag==1) break;
   }
  return p;
 }
int Haxi(KeyType key,int p)
 {   return key%p;
 }
void InputData(ElemType **ST,int n)   /*动态创建序列*/
{KeyType key;
int i;
(*ST)=(ElemType*)malloc(n*sizeof(ElemType));
printf("\n请输入%d个数据",n);
for(i=0;i<n;i++)
  scanf("%d",&((*ST)[i].key));
}
void CreateHaxi(ElemType **HASH,ElemType*ST,int n,int m,int p)
 {int i,j;  /*通过除留余数法分配序列地址*/
  (*HASH)=(ElemType*)malloc(m*sizeof(ElemType));
  for(i=0;i<m;i++) (*HASH)[i].key=NULL;
   for(i=0;i<n;i++)
   {j=Haxi(ST[i].key,p);
    while((*HASH)[j].key!=NULL)  /*线性探测法解决冲突*/
      j=(j+1)%m;
    (*HASH)[j].key=ST[i].key;
   }
  }
int Search(ElemType *HASH,KeyType key,int p,int *times)/* 哈希表的查找 */
  {int i;
   *times=1;
   i=Haxi(key,p);
   while(HASH[i].key!=0&&HASH[i].key!=key)
     { i++;++*times;}
   if(HASH[i].key==0) return -1;
   else return i;
  }
main()
  {ElemType *ST,*HASH;
   KeyType key;
   int i,n,m,p,stimes,times;
   char ch;
   printf("\n输入元素个数n和空间个数m(n<=m)");
   scanf("%d%d",&n,&m);
   InputData(&ST,n);
   p=Haxip(m); /*确定小于哈希表长m的质数p */
   printf("\n这个小于表长的质数是%d\n",p);
   CreateHaxi(&HASH,ST,n,m,p);    /*建立哈希表*/
   printf("\n这个哈希表是：\n");
   for(i=1;i<=n;i++) printf("%5d",i);
      printf("\n");
   for(i=1;i<=n;i++) printf("%5d",HASH[i].key);
   do{
     printf("\n输入要查找的元素的关键字:"); /*输入查找元素*/
     scanf("%d",&key);
     i=Search(HASH,key,p,&times);
     if(i!=-1)
       { printf("\n查找成功,位置是%d",i);/*输出查找成功的位置*/
         printf("\n比较次数是%d",times);
      }
     else
       { printf("\查找失败");
         printf("\n比较次数是%d",times);
      }
     printf("\是否继续？(Y/N):");
     ch=getch();
    }while(ch=='y'||ch=='Y');  /*是否继续？*/
   for(stimes=0,i=0;i<n;i++)
    {Search(HASH,ST[i].key,p,&times);
     stimes+=times;
    }
   printf("\n 平均查找长度是%5.2f",(float)stimes/n);
   ch=getch();
 }