Project 2: You are to implement the Huffman coding algorithm step 2 -- Construct Huffman ordered linked list using insertion sort. ******************************** I. Language: C++ and Java ******************************** ******************************** II. Input : A text file contains a list of pairs with the following format. // note: The input prob are integer, has been multiplied by 100, i.e., a prob equal to .40 will be given as 40. ******************************** char 1 prob 1 char 2 prob 2 char 3 prob 3 : : char n prob n ******************************** II. Outputs (use argv): a text file. The output format is given below. ******************************** III. Data structure: Both of your C++ and Java must have all the object classes as given below. ******************************** - listNode class - chStr (string) - prob (int) - next (listNode *) - constructor(s) - linkedList class - listHead (listNode *) - constructor (..) - insertNewNode (listHead newNode) // Use the algorithm steptaught in class. - findSpot () // Use the findSpot algorithm steps taught in class. - printList () // print the list to outFIle, from listHead to the end of the list in the following format: listHead -->(dummy, 0, nexts chStr 1 )-->( chStr 1 , prob 1 , nexts chStr 2 )...... --> (chStr j , probj , NULL)--> NULL For example: listHead -->(dummy, 0, b)-->( b, 5, a) -->( a, 7, d)............ --> (x, 45, NULL)--> NULL

2 ****************************************** IV. Main(argv) ****************************************** Step 1: listHead get a newNode as the dummy listNode with (dummy ,0), listHead to point to. Step 2: inFile open input file using argv outFIle open ouput file using argv Step 3: chr get from inFile Prob get from inFile newNode get a new listNode newNode.chStr chr newNode.prob Prob newNode.next null Step 4: insertNewNode (listHead, newNode) // use algorithm steps given in class Step 5: printList (listHead) // Out put the list to outFile, use the format given in the above. Step 6: repeat step 3 step 5 until the end of inFile . Step 7: close inFile close outFile