/*
Searching program with hashing method.
*/
#include<stdio.h>
#include<stdlib.h>
#define MAXSTUDENTS 50 /* Constants */
#define HASH_SIZE 61
int hash( long int key, int n ){
return( (int) ( key % (int)(n*1.4) ) ) ;
}
main()
{
/* Declaration Statements */
char names[HASH_SIZE][25], temp_name[25];
long int id[HASH_SIZE], key, temp_id;
int i, n, hash_index, cont, counter,
probe_worked, yes_no;
printf("Zeroing all elements of the array\n\n");
for( i=0; i < (HASH_SIZE); i++)
id[i] = 0;
do{
printf("How many students? (<%4d)",MAXSTUDENTS);
scanf("%d",&n);
}while( n>MAXSTUDENTS );
printf("Enter students' names and ID #'s\n");
printf("in this format ->Name:Doe,John[ENTER] (no spaces)\n");
printf(" ->ID:9421234[ENTER]\n");
/* The following is along loop that carries out the hashing
algorithm as each student is
added to the list. */
for( i=0; i<n; i++){
printf("Student #%d:",i+1);
printf("Name:");
scanf("%s",temp_name);
printf("ID:");
scanf("%ld",&temp_id);
hash_index = hash( temp_id,n );
/* This hash is legal! */
/* Now, this is the part where we will check for collisions, and take
appropriate action. */
if( id[ hash_index ] == 0 ) {
id[hash_index] = temp_id;
strcpy( names[hash_index], temp_name );
}
else { /* What to do if we had a collision */
probe_worked = 0;
do{
/* Check the next slot */
hash_index++;
/* If we're at the end of the list, go back to beginning */
if( hash_index >= HASH_SIZE )
hash_index = 0;
/* If the next slot was empty, fill it, and get out of loop */
if( id[ hash_index ] == 0 ){
id[hash_index] = temp_id;
strcpy( names[hash_index],
temp_name );
probe_worked = 1; /* A flag to exit the linear probing loop */
} /* end if */
}while( probe_worked == 0 ); /*
end of linear probing loop */
} /* endif - this was the if that
checked for a collision */
} /* end of outer loop that prompts
user for names and id#'s */
/* This part of the program lets the user search the list
using the hashing function */
do {
/* Keep on looking up names until
user wants to quit */
printf("Enter search key\n\n ID# :");
scanf("%ld",&key);
printf("\n **SEARCHING**\n");
hash_index = hash( key, n );
/* Now, we will check for collisions, and take
appropriate action. */
if( id[ hash_index ] == key ) {
strcpy( temp_name, names[hash_index] );
}
else { /* What to do if we had a collision when storing */
/* the ID # that the
user is requesting */
/* Initialize a counter to make sure that we don't
keep probing the whole list over and over again. */
counter = 0;
i = 0;
do{
counter++;
/* Check the next slot */
hash_index++;
/* If we're at the end of the list, go back to beginning */
if( hash_index >= HASH_SIZE )
hash_index = 0;
/* If the next slot was the key, get name and get out of loop*/
if( id[ hash_index ] == key ){
strcpy( temp_name, names[hash_index]
);
i=1; /* This is a flag to exit the linear probing loop */
} /* end if */
}while( i==0 && counter
<= HASH_SIZE); /*end of linear probe*/
} /* endif - this was the "if"
that checked for a collision */
cont = 0;
if(counter > n){
printf("Search key not found - check spelling\n");
printf("Try again (1 for yes/0 for no)? ");
scanf("%d",&yes_no);
}
else {
printf(" **FOUND**\n");
printf("ID#:%ld Name:%s\n\n", key, temp_name);
printf("Look up another student (1 for yes/0 for no)? ");
scanf("%d",&yes_no);
} /* End of if{} statement */
}while(yes_no == 1);
}
/* End of Hash.c program */
/*
Input :
8
Milo,Bloom 9611684
Cat,theBill 9613986
Dallas,Steven 9412978
Cutter,John 9613693
Jones,Oliver 9515010
Binkley,Mike 9510633
Opus,Holland 9513221
Dummy,One 0000000
Output :
Zeroing all elements of the array
How many students? (< 50) 8
Enter students' names and ID #'s
in this format ->Name:Doe,John[ENTER] (no spaces)
->ID:9421234[ENTER]
Student #1:
Name:Milo,Bloom
ID #:9611684
Student #2:
Name:Cat,theBill
ID #:9613986
Student #3:
Name:Dallas,Steven
ID #:9412978
Student #4:
Name:Cutter,John
ID #:9613693
Student #5:
Name:Jones,Oliver
ID #:9515010
Student #6:
Name:Binkley,Mike
ID #:9510633
Student #7:
Name:Opus,Holland
ID #:9513221
Student #8:
Name:Dummy,One
ID #:0000000
ID# :9800012
**SEARCHING**
Search key not found - check spelling
Try again (1 for yes/0 for no)? 0
*/