Programming Assignment 7 Optional – Hashing Solution

Problem:




Write a C++ program that does the following :




Create an integer array of size30.Assign * to each location in thearrayindicating that the array isempty..



Populate half of the array with random integer values between 125 and 425 inclusive. Use the following formula in order to hash and store each number in its properposition/location.



Generated Number % Table Size;




Should a collision occurs , use linear probing to find next available position / location. Use the following probing hashingfunction.



( Generated Number + 1 ) % Table Size;




Display and introduction message followed by the generated array. The generated array should be displayed in 2 lines. Each line contain 15 numbers separated by 2 spaces



The program then displays a menu on the screen allowing the user to do the following :




Display the generatedarray.



Search for a number ( between 125 – 425 ) in thearray.



Insert new number ( between 125 – 425 ) in thearray.



Delete a number ( between 125 – 425 ) from thearray.



End theprogram
Upon program termination ; The program shall display the following statistical information




The number of linear probes when each number is hashed and collision occurred when adding an element in thearray.



Include a signature line with your name – see samplerun.






NOTES:
Must use and modify the program that is provided in the my Hashing lecture notes.
Just one .cppfile.
A Message is displayed when searching for a number and number is not found.
A Message is displayed when deleting a number and number is notfound.
Modify the search and delete functions such that thefunctions uses hashing and rehashing functions when searching and deleting numbers form the table. You are not allowed to use sequential search for locating and deleting number from the tables.
Validation on menu selectionitems.
Rules :




This program must be done as an individual . Group work willnot be accepted and a grade of zero will beassigned.
Your programmust compileand run. The program will be tested using the latest version of Codeblocks for windows. No grades will be given for a program that compiles but does notrun.
You renot allowedvectors , linked lists. Must only usearrays.
Your program must be properlydocumented according the style above .See the website for the sample programming styleprogram.
You must name your program as:



3358_0_LastName_FirstName_Optional_PG7.cpp ( Section 0)
3358_1_LastName_FirstName_Optinoal_PG7.cpp ( Section 1)
3358_2_LastName_FirstName_Oprional_PG7.cpp ( Section 2)



Where LastName is your Last Name and FirstName is your First Name. For example , the file name should look something like :




3358_0_Gholoom_Husain_Optional_PG7.cpp(not .cbp)







You must upload your programs no later than the indicated time above on the due date. This a individual work andNo late assignments will beaccepted.



USE TRACS To upload your program .







You mustalsoturn in hard copy of your source code no later than the due date /time
. Should the hard copy consist of more than one page , then , the hard copy must bestapled. if you are unable to turn in a printout during class, you can take the program to the computer science department and hand it to the front desk personal (Comal211

) before the deadline. Make sure that the front office stamps the program. Make sure that include the date and time. Finally ,make sure that they place the program in my mailbox.




DO NOTslide your program under my office door – It willNOTbe accepted.




Also , No late submission hard copy of the assignment will be accepted and a grade of zero will be assigned .










The following points will be deducted if :






Incorrect file format such asuploading.cbp instead of .cpp , missing electronic copy , missing the hardcopy , compilationerrors, using vectors , linked lists , not using the indicated hashing and linear probing functions when Adding or searching for an element in the array or deleting an element from the array. Group work , Not using class in implementing this assignment( - 10 points )



Each logical error :( - 1.25 points)



Other :(2 pointseach) ifanyof the following takes a place:



Unable to read the source code due to unclearprinting
Incorrect program file name.
Hard copy is not stapled or printed in landscapeorientation.
Incorrect Stylesuch as but not limited tomissing Header , missing footer , missing comments or program documentations , missing roster number , missing sectionnumber, …etc
Style Guidelines:



At the beginning of your program ( andbeforethe #include statement ), include the following :




Header comments(file documentation block) should be at the top of each file and shouldcontain: Author / s, Due Date, Assignment Number, Course number and section, Instructor, and a brief description of the purpose of the code in the file. For example:

// RosterNumber: xxxxxxxxx

//

// Author : (Your namehere!!)

// Due Date:

// Programming Assignment Number 7 -Optional

//

// Spring 2018 - CS 3358 - Your SectionNumber

//

// Instructor: HusainGholoom.

//

// <Brief description of the purpose of theprogram







Variable names :



Must be meaningful.
The initial letter should be lowercase, following words should be capitalized, noother caps or punctuation(i.e. weightInPounds ).
Each variable must be declared on a separate line with a descriptivecomment.



Named constants :



Use for most numericliterals.
All capitals with underscores(i.e. TX_STATE_SALES_TAX )
Should occur at top of function, or global (only ifnecessary)



Line lengthof source code should be no longer than 80 characters (no wrapping of lines).

Indentation :



Use 2-4 spaces (but be consistent throughout yourprogram).
Indent blocks, within blocks,etc.
Use blank lines to separatesections.



Comments for variables :



All variable definitions should be commented as follows:




int gender; // integer value for thegender,

// 1

Sample Run







Welcome to my Hashing Program







Creates an integer array of size 30. Assigning * to each location in the array indicating that the array isempty.
Populates half of the array with random integervalues between 125 and 425inclusive.
If a collision occurs, linear probing will find thenext available position /location.
The generated array will be displayed in 2 lines. Each line contains 15 numbers separated by 2spaces.



Generated Array




* * * 243 * * 366 157 * * * 371 * 403 *

225 * * * 289 260 409 231 139 114 200 201 379 * *




Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: B




Enter a number you want to search (between 125-425): 409The number 409 was found in element 21




Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: C




Enter a number you want to insert (between 125-425): 409The number 409 was added.

Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: A Displaying the generatedarray.

* * * 243 * * 366 157 * * * 371 * 403 *

225 * * * 289 260 409 231 139 114 200 201 379 409 *




Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: D




Enter a number you want to delete (between 125-425): 225




225 Has been deleted




Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: A Displaying the generatedarray.

* * * 243 * * 366 157 * * * 371 * 403 *

* * * * 289 260 409 231 139 114 200 201 379 409 *




Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: D




Enter a number you want to delete (between 125-425): 125




125 not found in the array.







Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: P




*** Invalid Option ***







Select from the following menu options




Display the generatedarray.
Search for a number (between 125-425) in thearray.
Insert a new number (between 125-425) in thearray.
Delete a number (between 125-425) from thearray.
X. End theprogram.




Select your option: X




The number of times each position / location is hashed when adding an element in the array is 16




The number of linear probes when each number is hashed and collision occurred

when adding an element in the array is 34




This Hashing ProgramwasImplemented byHusain Gholoom - April 30,2017