/*

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

*/