!
PROGRAM P105
!
!
! CLASS LIST RETRIEVAL PROGRAM
! FIND SOME STUDENT GRADES
! USING A HASHING SCHEME WITH THE ID AS THE KEY
!
! DECLARE ARRAYS FOR FILE
!
IMPLICIT NONE
CHARACTER (LEN=25) :: NAMES(100),NAME
INTEGER :: ID(100),MARKS(100,7),GRADES(7)
!
INTERFACE
SUBROUTINE HASH(ID,NR)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT) :: ID(:),NR
END SUBROUTINE HASH
END INTERFACE
!
PRINT *, 'This is Program >> P105 = Hashing'
!
! Tell program where data for READ is coming from
OPEN(UNIT=5, FILE='P105.DAT')
! UNIT=5 is the default input
!
!
!===== ZERO OUT ALL ID'S FOR STARTERS
!
L1: DO J=1,100
ID(J)=0
END DO L1
!
!==== READ IN FILE AND STORE IN MAIN MEMORY
!
L2: DO J=1,100
READ 15,KD,NAME,GRADES
15 FORMAT(I7,1X,A25,7I3)
IF(KD == 0) GO TO 101
Print 15,KD,NAME,GRADES
CALL HASH(KD,NR)
31 IF(ID(NR) == 0) THEN
! STORE AWAY THE DATA IN ANY EMPTY SLOT
ID(NR)=KD
NAMES(NR)=NAME
L3: DO K=1,7
MARKS(NR,K)=GRADES(K)
END DO L3
!
!=== HERE WE DEAL WITH THE CASE OF A USED SLOT
! TRY THE NEXT OVER, BUT WATCH FOR END OF THE FILE
!
ELSE
NR=NR+1
! IF AT END - START AT BEGINNING
IF(NR > 100) NR=1
GO TO 31
END IF
END DO L2
PRINT 16
16 FORMAT(/'TOO MUCH DATA FOR DEFINED ARRAYS'/ & 'INCREASE ARRAY SIZE AND RERUN'//)
STOP
!
!==== READ AND PROCESS NAMES REQUESTED
!
101 NREC=J-1
PRINT 102,NREC
102 FORMAT(/'CLASS LIST PROGRAM - RETRIEVAL BY NAME'/ & I5,' RECORDS ON FILE')
NREQ=0
L4: DO J=1,NREC
READ 202,KID
202 FORMAT(I7)
IF(KID == 0) THEN
PRINT 203,NREQ
203 FORMAT(I5,' REQUESTS PROCESSED'/)
STOP
ELSE
NREQ=NREQ+1
CALL HASH(KID,NR)
231 IF(ID(NR) == 0) THEN
PRINT 205,KID
205 FORMAT(I9,' NOT ON FILE - CHECK SPELLING')
ELSE
IF(KID == ID(NR)) THEN
PRINT 206,KID,NAMES(NR),(MARKS(NR,I),I=1,7)
206 FORMAT(I9,' ',A25,7I5)
ELSE
NR=NR+1
IF(NR > 100) NR=1
GO TO 231
END IF
END IF
END IF
END DO L4
STOP
END PROGRAM P105
!
SUBROUTINE HASH(ID,NR)
IMPLICIT NONE
INTEGER ,INTENT(IN OUT) :: ID(:),NR
INTEGER :: NPRIME=97
NR=MOD(ID,NPRIME)+1
RETURN
END SUBROUTINE HASH
/*
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 0000000OUTPUT :
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
*/
{$G256}
{$P512}
{D+}
PROGRAM p105 ( input, output );
{
Class list retrieval program
Find some student grades
Using a hashing scheme with the id as the key
Declare arrays for file
}
TYPE
real_array = ARRAY[1..100] OF REAL;
char_array = ARRAY[1..25] OF CHAR;
VAR
names : ARRAY[1..100] OF char_array;
name : char_array;
marks : ARRAY [ 1..100, 1..7 ] OF INTEGER;
id : real_array;
grades : ARRAY[1..7] OF INTEGER;
i, j, k, nr, rec, req, looped, loop : INTEGER;
kd, kid : REAL;
PROCEDURE hash ( id : REAL;
VAR nr : INTEGER );
VAR
prime : integer;
BEGIN
prime := 97;
nr := trunc ( id / 1000.0 );
nr := ( nr mod prime ) + 1
END;
BEGIN
{
Zero out all id's for starters
}
FOR j := 1 TO 100 DO
id[j] := 0;
{
Read in file and store in main memory
}
j := 0;
REPEAT
j := j + 1;
read ( kd, name );
FOR i := 1 TO 7 DO
read ( grades[i] );
readln;
IF ( kd <> 0 ) THEN
BEGIN
hash ( kd, nr );
looped := 0;
WHILE ( ( id[nr] <> 0 ) AND ( looped < 2 ) ) DO
BEGIN
nr := nr + 1;
{
If at end - start at beginning
}
IF ( nr > 100 ) THEN
BEGIN
nr := 1;
looped := looped + 1
END { end if }
END;{ end while }
{
Store away the data in any empty slot
}
IF ( looped < 2 ) THEN
BEGIN
id[nr] := kd;
names[nr] := name;
FOR k := 1 TO 7 DO
marks [ nr, k ] := grades[k]
END { end if }
ELSE
BEGIN
writeln;
writeln ( 'too much data for defined arrays' );
writeln ( ' increase array size and rerun' )
END
END
ELSE
BEGIN
{
Read and process names requested
}
rec := j - 1;
writeln ( ^l );
writeln ( 'Class list program - retrieval by name' );
writeln;
writeln ( rec:5, ' records on file' );
writeln;
req := 0;
k := 0;
REPEAT
k := k + 1;
readln ( kid );
IF ( kid <> 0 ) THEN
BEGIN
req := req + 1;
hash ( kid, nr );
loop := 0;
WHILE ( ( loop < 2 )
AND ( kid <> id[nr] ) ) DO
BEGIN
nr := nr + 1;
IF ( nr < 100 ) THEN
BEGIN
nr := 1;
loop := loop + 1
END { end if }
END; { end while }
IF ( kid = id[nr] ) THEN
BEGIN
write ( kid:9:0, ' ':3, names[nr] );
FOR i := 1 TO 7 DO
write ( marks [ nr, i ]:5 );
writeln
END; { end if }
IF ( loop >= 2) THEN
writeln ( kid:9:0, ' not on file - check spelling' )
END
ELSE
BEGIN
writeln;
writeln ( req:5, ' requests processed' );
writeln
END { end else }
UNTIL ( ( kid = 0 ) OR ( k > rec ) OR ( loop > 2 ) )
END
UNTIL ( ( j > 100 ) OR ( looped > 2 ) OR ( kd = 0 ) )
END.
DATA: 7611684 Opus 15 16 16 17 17 39 76 7613986 Bloom Milo 16 17 16 18 17 41 79 7412978 Dallas Steven 13 12 11 13 14 31 64 7613693 Cat Bill the 18 18 19 17 19 41 82 7515010 John Cutter 15 16 15 15 15 38 77 7510633 Jones Oliver W 17 17 18 17 17 42 80 7513221 Mike Binkley 19 19 19 18 19 45 91 0000000 Dummy 0 0 0 0 0 0 0 7611684 7613693 7511522 7513221 0000000
Last modified: 08/07/97