Question
C++ program: Please implement a hash table of 29 buckets to store string data use Radix Sort, reading and writing string in text file must
C++ program: Please implement a hash table of 29 buckets to store string data use Radix Sort, reading and writing string in text file
must use the doit Function:
x----character string
b----number of buckets
hash(x)=mod (doit)(x).b)
int doit (string x)
val=1;
for(i=0;i
{ val=val * 32+ (int)x[i];}
//remark: (int)x[i] should be ASCI Value
string in text file
Hishaam Esteban Kevin Matthew Brandon Joel Luis Jianwei Yechiel Taeyong Jiayu Jiade Phillip Russell Mohebullah Akshar Evgeniia Andres Marco Justin Robin Kelvin Zhiheng Jeffrey Yifei Yinyu Jiaxin Youyia Eleftherios Yuan Resfred Danielle Jason Lin ZhengZhong Han Chandra Conghui Christopher Christina Rashad Aaron Gregory Xihao Yuhuan Niraj Logan Ba Khoi Jiade Pinpin Seth Jacb Russell Win Thurein Karamvir Andres Shadman Rani Prince Patricio Christopher Angelo Denny Laert Zhiheng Taejoon Heesun Joseph Bee Sim Kenny Jasmin Ben Qisheng Michael Cheng Brandon Peter Oscar Qi Juan Brian Colin Harmandeep Brian Wei Yangfan Emanuel Huihui Cesar Shuhua
. inFile (use argv [1]): A text file contains a list of English words (strings). ******************************** II. outFile1 (use argv [2]): The final result of the hash table: 29 ordered linked list. The output format is given below. outFile2 (use argv [3]): All debugging outputs, for your eyes only!
Data structure: Must have all the object classes as given below.
********************************
- list Node class
- data (string)
- count (int) // initialize to zero
- next (listNode *)
methods:
- printNode (node) // use the format:
(this nodes data, this nodes count, next nodes data )
// see example below.
- A hashTable class
- bucketSize (int) // set to 29
- hashTableAry [bucketSize] (listNode *)
// An array of list node pointer, listNode *, size of bucketSize,
method:
- createHashAry (...) // The method dynamically allocate the hashTableAry,
//where each entry point to a dummy node: (dummy, 0, null)
// On your own! You should know how to do this.
- storeDataIntoHashTable () // reads a data from inFile, gets the index from hash function, and stores
// the data into the hash table
- (int) Doit () // Given an English word, the method returns the index of hashTableAry
// where the data will be insert into the linked list pointed by hashTableAry [index].
- listInsert () // Reuse the code in your previous projects
- findSpot () // Reuse code in your previous projects
- printHashTable ()
// The method calls printList method to print the entire 29 linked list of the hash table.
- printList ()
// The method calls printNode method to print each node in the entire linked list, pointed by the //hashTableAry[index] to a given outFile, using the following format:
hashTable[index] (this node data, this nodes count, next nodes data) (this node data, this nodes count, next nodes data) . . . . . NULL
For example: if index is 5
hashTable [5] ( dummy, 0, Adam) (Adam, 1, Ben) (Ben, 2, Brian) (Brian, 2, Chuck)........................ NULL
******************************************
IV. Main( )
******************************************
Step 1: inFile open input file using argv[1]
outFile1, outFile2 open outfiles using argv[2] and argv[3]
Step 2: createHashAry (hashTableAry, bucketSize) // on your own
Step 3: storeDataIntoHashTable (inFile, outFile2)
Step 4: printHashTable (outFile1)
Step 5: Close all files
******************************************
V. storeDataIntoHashTable (inFile, outFile2)
******************************************
Step 1: data get one string from inFile
Step 2: newNode get a new listNode (data,1, null)
Step 3: index Doit (data)
Step 4: listHead hashTableAry [index] // listHead is a local listNode* type
Step 5: listInsert (listHead, newNode)
Step 6: printList (index, outFile2) // debug prints
Step 7: repeat step 1 step 6 until the end of inFile
******************************************
VI. listInsert (listHead, newNode)
******************************************
Step 1: Spot findSpot (listHead, newNode)
Step 2: if Spot != null
newNodes next Spots next
Spots next newNode
******************************************
VII. (listNode *) findSpot (listHead, newNode)
******************************************
Step 1: Spot listHead
Step 2: if Spots next != null *and* Spots nexts data < newNodes data // string comparison!!
Spot Spots next
Step 3: repeat Step 2 until condition failed
Step 4: if Spots nexts data == newNodes data
Spots nexts count ++
Spot null
Step 5: return Spot
******************************************
VIII. printHashTable (outFile)
******************************************
Step 1: index 0
Step 2: printList(index, outFile)
Step 3: index ++
Step 4: repeat step 2 to step 3 while index < bucketSize
******************************************
VIII. printList (index, outFile)
******************************************
Step 0: output to outFile : hashTable [ index]
Step 1: printSpot hashTableAry[index]
Step 2: printNode (printSpot)
printSpot printSpots next
Steo 3: repeat step 2 while printNode != null
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started