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