CS210 Lab: Hash Table Postlab Answers

Postlab Answers:

Part 1

For the following two questions, use the following values:

   67 46 88 91 123 141 152 155 178 288 390 399 465 572 621 734

1. Draw a diagram to show how the values are inserted into a hash table with 20 positions. Use the division method of hashing and the linear probing method of resolving collisions.

   Step 1: Apply the Division Method to Get the Index
   67 % 20 = 7
   46 % 20 = 6
   88 % 20 = 8
   91 % 20 = 11
   . . .
   734 % 20 = 14
   

   Step 2: Create Table Using Linear Probing Method
   

2. Draw a diagram to show how the values are inserted into a hash table that uses the hash function key % 10 to determine into which of ten chains to put the value.

   Step 1: Apply the Division Method to Get the Index
   67 % 10 = 7
   46 % 10 = 6
   88 % 10 = 8
   91 % 10 = 1
   . . .
   734 % 10 = 4
   

   Step 2: Create Table Using Chaining Method
   

Part 2

This question is based on the lab exercise that you have just completed.

1. When implementing programs that take passwords, you might want to hide the user input, or display stars instead. You can do this using a couple of functions:
   • getch()--to get a character from the console without echo. (#include <conio.h>)
     
     • You may have to use type casting or type conversio n to change the integer return from getch() into a character.
     • The following format should work:
       (char)getch() or char(getch()) .

   • putchar('*')--to echo stars. (#include <stdio.h>)

   Look these up using "Help" and try to modify your code so that you program will run something like the following:

   Login: mary
   Password: ********
   Authentication successful
   Login:
   

   
   //add the following to your headers
   #include <stdio.h>
   #include <conio.h>
   #define MAXPASSCHAR 15  //maximum password length
   
   // prototypes 
   char *getpasswd(void); 
   .
   .
   .
   //replace two commented lines with the following
          // cout << "Password: ";
          // cin >> pass;
   	pass=getpasswd();
   .
   .
   .
   //define the following function at the end
   char *getpasswd(void) 
   { 
   	char temp; 
   	static char buf[MAXPASSCHAR+1]; //use static so that you can access data in buf from main
   	bool inputdone; 
   	unsigned int i; 
   
   	inputdone=false; 
   	i = 0; 
   
   	buf[i]='\0';  //initialize buff incase empty password
   
   	printf("Password: "); 
   
   	do 
   	{ 
   		//temp = (char)_getche();  //with echo
   		temp = (char)_getch(); 
   
   		if (temp=='\b') //backspace character
   		{
   			putchar('\b');
   			i--;
   		}
   		else if(temp != '\r') //carriage return 
   		{ 
   			putchar('*'); 
   			buf[i++] = temp; 
   		} 
   		else
   		{ 
   			inputdone = true; 
   			putchar(temp); 
   			buf[i]='\0'; 
   		} 
   
   	}while(!inputdone & (i<MAXPASSCHAR)); 
   
   	// if user inputted all MAXPASSCHAR characters, then 
   	// we need to put in an end of string for the 
   	// printf following 
   	if(i == MAXPASSCHAR) 
   		buf[i]='\0'; 
   
   	// this is just to see if it was inputted ok 
   	printf("\nPassword was %s\n", buf); 
   
   	return buf;
   } 
    

   ---

   Back to Exercise click here

   ---

   Back to Hash Table Lab click here

   ---