Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define M 12
#define N 467
/*
size of hash table is 467
Which is a prime number and in form of 4(j)+3
j=116
4*116+3=467
So suitable for square probe hashing
*/
typedef struct student{
char name[50];
char sex[10];
char number[M];
}ST;
void initTable(ST *A);
void readFromFile(ST *A);
int hashFun(char *number);
void query(ST *A, char *number);//search
int getPrime(int n);
void initTable(ST *A){
for(int i=0;i<N;i++){
strcpy(A[i].name,"-");
strcpy(A[i].sex,"-");
strcpy(A[i].number,"-");
}
}
int hashFun(char *number){
/*FOLDING METHOD*/
/*3digit+3digit+3digit+2*/
int temp,hashNum=0;
for(int i=0;i<M-2;i++){
temp=0;
temp+=(number[i]-'0');
if(i+1<M-1){
temp*=10;
temp+=(number[++i]-'0');
if(i+1<M-1){
temp*=10;
temp+=(number[++i]-'0');
}
}
hashNum+=temp;
}
//printf("%s\t%d\t%d\n",number,hashNum,hashNum%N);
return hashNum%N;
}
void readFromFile(ST *A){
ST temp;
FILE *file;
file = fopen("data4.txt","r");
int rehash=0;
while(fscanf(file,"%s %s %s",temp.name,temp.sex,temp.number)>0){
int index=hashFun(temp.number);
int tempRehash=0;
if(A[index].number[0]=='-'){
strcpy(A[index].name,temp.name);
strcpy(A[index].sex,temp.sex);
strcpy(A[index].number,temp.number);
}
else{
int n=1;
int tempIndexLeft=index-(n*n)%N;
int tempIndexRight=index+(n*n)%N;
while( !(A[tempIndexLeft].number[0]=='-' || A[(tempIndexRight)%N].number[0]=='-' ) ){
n++;
tempIndexLeft=index-(n*n)%N;
tempIndexRight=index+(n*n)%N;
tempRehash++;
}
if(A[(index+(n*n))%N].number[0]=='-')
index=(index+(n*n))%N;
else
index=(index-(n*n))%N;
strcpy(A[index].name,temp.name);
strcpy(A[index].sex,temp.sex);
strcpy(A[index].number,temp.number);
}
if(rehash<tempRehash)
rehash=tempRehash;
}
printf("\nHash table built successfully.\n");
printf("Maximum rehash time: %d\n",rehash);
}
void query(ST *A, char *number){
printf("test");
char exitCondition[]="-";
int index=hashFun(number);
int rehash =0; //+1 for first hash later
//int boolFound=0;//current false
int tempIndexLeft=index-(rehash*rehash)%N;
int tempIndexRight=index+(rehash*rehash)%N;
printf("%d\t%d",tempIndexLeft,tempIndexRight);
while( !(strcmp(A[tempIndexLeft].number,number)==0 || strcmp(A[tempIndexRight].number,number)==0) ){
rehash++;
//printf("test");
if(strcmp(A[tempIndexLeft].number,"-")!=0)
tempIndexLeft=index-(rehash*rehash)%N;
if(strcmp(A[tempIndexRight].number,"-")!=0)
tempIndexRight=index+(rehash*rehash)%N;
if(strcmp(A[tempIndexLeft].number,exitCondition)==0 && strcmp(A[tempIndexRight].number,exitCondition)==0)
break;
}
printf("After %d time(s) hash,",rehash+1);
if(strcmp(A[tempIndexLeft].number, number)==0){
printf("Record found:\n%s %s %s\n",A[tempIndexLeft].name,A[tempIndexLeft].sex,A[tempIndexLeft].number);
}
else if(strcmp(A[tempIndexRight].number, number)==0){
printf("Record found:\n%s %s %s\n",A[tempIndexRight].name,A[tempIndexRight].sex,A[tempIndexRight].number);
}
else{
printf("Record not found.\n");
}
}
int main(){
ST A[N];
char phoneNumberInput[M];
char exitConditon[]={"0"};
initTable(A);
readFromFile(A);
//for(int i=0;i<N;i++){
// printf("%s %s %s\n",A[i].name,A[i].sex,A[i].number);
//}
//if(strcmp(A[0].number,"13267729168")==0)
// printf("True");
while(1){
printf("\nPlease input phone number: ");
scanf("%s",phoneNumberInput);
printf("test");
if(strcmp(phoneNumberInput,exitConditon)==0)
break;
printf("test");
query(A,phoneNumberInput);
}
}