//words.txt

electroergometer scummer sendals subduer zimb presumers jiujitsu tingibility swellheads spendable serpenteau cytosols seston hematid sludgy unidle praisableness towerproof precontroversy yautias dissertational excremental ksar unmutinousness ipseand machination captance epithelioglandular inequitate micrognathic nonrecuperative atmolyzation exteriorized strutters decolourization supergloriously beefiest nitrosylsulfuric foredestining lutfisk pretty echoers folkmoter seasonable alpinesque autoregenerator gooders dictator coronad junctures thallogenic sulphapyrazine ungloom sceneshifter micropulsation riced pretransportation blazoned azoparaffin mattes unintendedly eighties oatmeals mist legislators searest heterotaxis nonreliable tonguing allusively viziers frownless azogallein constrained tummy unshness sinople paralipomena procaciously prerequiring swanned aphidophagous trowane bolus vicariates lanolin familiarised vaginally fluosilicic generalizability crossfoot yokels mintmark greenths sunblind deccennia cowsucker empiristic cunctatury hematocolpus tabular unremounted veiler angletwitch flippant poetry teazeling bloodspilling discontinuer pronouncedness adios isostasist keef skiptail tensure origins lockout foliating mealmonger exactors flammule bastardise subchancel maletolt overbraked outsucken budgie durzi faceplate jabiru unproselyte baserunning carposporous parasceve unscaffolded metallotherapeutic esophagocele androcephalous dartos pauciradiate godmothership ceroline pygopodine tracheochromatic repopularize telescopical sarcoplastic solander protoneme tenacities dux jobbish karyon cadying shortsightedness overliberal baggage cryesthesia dualin moderatos cubiform beacon hoodshy hyemal recoct silicononane redry uppluck cauligenous unifaced epidia noticeableness rivery anaptychus mijnheer subtersensual illuviate nonreputably furnished sidesaddles seminormalness beardie bonnetman offshoot scall metricist unforeign nouveautes silexite overtimed brutification weerish postdiastolic microchiropterous nonnutrient aggravatingly pistilline nonpopularity nematocyst outyield serrai centriscoid lamblike mutic coenenchymal bullhide grithman upbuoying phyllostomous fritniency clicked quaternal slainte cyclopedist ectostosis plungers semicomplicated economical fulcrum aromatophor yarners inheriting nonconfidentiality triodontoid prissies commonplacely matroclinous capitle cumulus vermily overmill parade snakestone semipagan underletter auriscopy areoles medicated parchmenter acetylenogen predispatcher nonvalent underlies ignominiousness utensils bowwood herdship hypanthia hastile interlapse downstream pontiffs dysphrasia anemotropism exteriorisation mitigant hooray stypticin economise pluralizing beslobber purin otherworldliness dustbin quinacrine pmk quadplex outcorner whitling awakens recanters qere bioecologically lezes appealed unrelievability pupillometer perilymphatic adjurer soave homolosine chordomesoderm unconcessible freshmen nonequalizing rusticly sarapes vesiculopustular aphidian ethicalness bargeload interscholastic nonodorous credences punctal oxazine superalbal voc subjectless arider pseudocapitulum ceraunia supernaturalize planetologists lymphomonocyte relatives nonfluidic sinterability lootsman whorly halenesses polyoicous brandyman chunari stratagematically yokeableness donnas exocoelar roseways missilery nonrepudiative unowed preclassified subtilis anastasis brittly reeducative comestible blousing rezbanyite ine flouters intermatting secularizing dullsome volcanicity imperceptive whoremastery shearsman octahedrally brushmaker eavesdropping ciliate workmaster miltier gentilish energeia terraqueous elute vengeant objected ekes nonviviparously fulvidness prevesical alacreatinin tivy smoothness unspeedy nooser behymn osmeterium hemicranic yokelish fafaronade corbeau sophical rosied winnable oesophagus postsigmoidal sylvestral dispermous hicatee outgloom awakenings semisucculent redye shanghais ecstasies cestoid euthycomic groins espiegle jeopardying radioautography dykage norie nauseam culicine sayst nonprohibitorily enchase reendowment cetylene ennuyant psychotic mareograph organella outstartling birks acrostic unsinuously unformatted suppressiveness deprivable introduces modicums mudrooms anthomedusan whippertail sardanas erbium nubbling incus rashly divaricatingly rockaways oxygenant sesquinona enrollee distemper euphonious mazed unfittable kempite imperfect untortuously fullom alinement ethnogeographically intercalate isocolon soulical scatophagoid unboastfully afterdays hypothallus rhabdoms harten adrenocorticosteroid peles maltreatment floatless acrinyl mise trudge sacahuiste tetroxide antecedence athyrosis postulance datapac sweeten filch overstrict dandify peculiarizing recircling posticous aforeward promonopolist endellionite interpollinating spiceries presoak forsteal jarvy inimicability semisomnolently andor innodate seawaters cotquean potations precalculate ackey intercedent outfeeling unsplattered diplonts postcribrate dispost preassign rebaptize plumbago preadviser holophotal artillerist skreighed cyesiology unpermeant rotonda always muleback interpermeating tetrobolon nonexpeditious autographing howlet

*/

#include #include #include typedef struct WordNodes{ char word[21]; struct WordNodes* next; }WordNodes;

unsigned long hash(char *str) { unsigned long hash = 0; int c = 0; while ((c = *str++) != '\0') hash = hash + c; return hash%11; //return index 0 to 10 } //Create a node WordNodes* createNode(char* value){ WordNodes* ptr=(WordNodes*)malloc(sizeof(WordNodes)); strcpy(ptr->word,value); ptr->next=NULL; return ptr; }

//Insert in linkedlist void insertSorted(WordNodes** head,char* value){ if(*head==NULL){ *head=createNode(value); return; } WordNodes* ptr=*head; if(valueword){ WordNodes* tmp=createNode(value); tmp->next=ptr; *head=tmp; } else{ while(ptr->next!=NULL){ if(value>ptr->next->word) ptr=ptr->next; else break; } WordNodes* tmp=createNode(value); tmp->next=ptr->next; ptr->next=tmp; }

} //Search function int search(WordNodes* head,char* value) { if(head==NULL) return 0; WordNodes* ptr=head; while(ptr!=NULL){ if(!strcmp(value,ptr->word))//COMPARE THE STRING return 1; ptr=ptr->next;

} return 0; }

void printList(WordNodes* head){ WordNodes* ptr=head; while(ptr){ printf("%s->",ptr->word); ptr=ptr->next; } printf(" "); } int main(void) { char word[21]; int index; WordNodes* arrbuck[11]={NULL}; while(1) { printf("Enter a word: "); fgets(word,21,stdin); if(word[0]=='.') break; char* ptr=strtok(word," "); //REMOVE THE index=hash(ptr); //get index 0 to 10 insertSorted(&arrbuck[index],ptr); //insert in list } int i; for(i=0;i

For this project, you will compare the efficiency of searching a sorted linked list and a hash table.

You should use a variation of your code for Mini-Assignment 3 for this.

Modifications from Mini-Assignment 3 Instead of getting the words to load into the hash table from the user, you must load at least 2000 words from a file called words.txt as input (using file I/O). Make sure that your words are sorted in random order (more about this later). The words.txt file must be in the same directory as your source code. It's OK to use more than 2000 words but don't have more than 10000.

When you load a word into the hash table, also load the words into one very long sorted linked list. You must use the same function for inserting into the sorted linked list as for inserting into the hash table bucket's linked list.

Make the hash table 127 buckets in size.

You must create a function called searchLinkedList that searches a sorted linked list for a word and returns a pointer to the node containing the word (if found) or NULL. This function must return NULL immediately after you pass the point in the linked list where the word would have been found if it was in the linked list. The function takes three parameters: char * searchWord: word to search for (entered by the user) struct linkedList * linkedList: linked list to search (in your program, you can call the linked list node struct anything that makes sense) int * comparisonCount: pointer to int filled in by the function with the count of strcmp comparisons done in searching the linked list

Create a search function called searchForWordTwice. It returns nothing and will have the following parameters: char * searchWord: word to search for (entered by the user) struct linkedList * linkedList: linked list to search struct linkedList * hashTable[]: hash table to search int comparisonCount[2]: array containing the count of strcmp comparisons done in searching the extremely-long sorted linked list (element 0) and in searching the hash table (element 1) It must call your linked list search function and then displays one of the following messages once the search is done: "word was found in the list in number comparisons", where word is the word being searched for, list is either "linked list" or "hash table bucket" and number equals the number of times that strcmp was called "word was NOT found in the list in number comparisons" You will use this search function to search the hash table bucket and the sorted linked list. Don't worry about the grammatical inconsistency of possibly displaying "1 comparisons". Indent the message displayed by one TAB ('\t').

Once you are finished the loop, display the total number of searches, the total number of comparisons done by searching the sorted linked list, and the total number of comparisons done by searching the hash table. Other Requirements Design your linked list code so that you do not have to duplicate code unnecessarily. This is very important.

Clean up all allocated memory before exiting.

Use constants to avoid magic numbers.

You can assume that all words will be in lowercase.

Your program must compile without warnings. If you have to use a #pragma as stated in order to get rid of the Microsoft-specific warnings, you should do so.

Your project must be named dsA2.

The source file that contains your main() function must be called dsA2.c or dsA2.cpp. Put all hash table-related code in hashing.c or hashing.cpp. Put all linked list-related code in linkedlist.c or linkedlist.cpp (and linkedlist.h if you are using a class). Create other .h files as needed to support compilation. Do not create any other source files.

Remember to put appropriate header comments at the top of ALL source files.

Create a JPG file called compare.jpg that contains a screenshot of your program running with a full screen of sample output (so that I can see the difference in comparison count between the methods for multiple successful and unsuccessful searches (do not skimp on the number of searches)). Make sure that it includes the final summary output. Put this file in the top directory of your project (so that it is submitted with your submission). A sample of this file is provided for you. Please follow the output format and contents exactly.

Provide your words.txt file in the same directory as your source code.

Call your ZIP file DSA2.zip.

Submit your submission to the appropriate dropbox as required by the SET Submission Standards document.

Hints An easy way to sort the input words in random order is the following:

Get 2000+ words, one per line. Copy the words to the clipboard. Start Excel. Paste the words into Excel (so that you have one column of 2000+ rows). In the next column, put random numbers using =rand(). Select all of the data. Sort the data using the column with the random number as the sorting key. Delete the random number column. Save the data into a text file. Here is a 500 word sample input file.

Unit testing your functions is a really good idea. You should not leave your unit testing code in your submitted source.

You can use the examples provided on the DS website and C website as long as you attribute credit in a comment. You must attribute credit for the djb2 hash function (credit the real author Dan Bernstein and state that you got it from lecture).

You can use either C or C++. Do not use C++ language features that you are not comfortable with.

C:AWINDOWS system32\cmd.exe tentative tentative was NOT found in the linked list in 1361 comparisons. tentative was NOT found in the hash table bucket in 11 comparisons. five five was NOT found in the linked list in 3076 comparisons. five was NOT found in the hash table bucket in 26 comparisons. chimed chimed was found in the linked list in 1438 comparisons chimed was found in the hash table bucket in 13 comparisons masked masked was NOT found in the linked list in 4833 comparisons. masked was NOT found in the hash table bucket in 32 comparisons. stateship stateship was found in the linked list in 1863 comparisons. stateship was found in the hash table bucket in 19 comparisons. airborne airborne was found in the linked list in 205 comparisons. airborne was found in the hash table bucket in 2 comparisons. serious serious was NOT found in the linked list in 2306 comparisons. serious was NOT found in the hash table bucket in 20 comparisons. series series was found in the linked list in 2307 comparisons. series was found in the hash table bucket in 17 comparisons. Total Number of Searches: 8 Total Number of Comparisons in Linked List: 17389 Total Number of Comparisons in Hash Table: 140 Press any key to continue C:AWINDOWS system32\cmd.exe tentative tentative was NOT found in the linked list in 1361 comparisons. tentative was NOT found in the hash table bucket in 11 comparisons. five five was NOT found in the linked list in 3076 comparisons. five was NOT found in the hash table bucket in 26 comparisons. chimed chimed was found in the linked list in 1438 comparisons chimed was found in the hash table bucket in 13 comparisons masked masked was NOT found in the linked list in 4833 comparisons. masked was NOT found in the hash table bucket in 32 comparisons. stateship stateship was found in the linked list in 1863 comparisons. stateship was found in the hash table bucket in 19 comparisons. airborne airborne was found in the linked list in 205 comparisons. airborne was found in the hash table bucket in 2 comparisons. serious serious was NOT found in the linked list in 2306 comparisons. serious was NOT found in the hash table bucket in 20 comparisons. series series was found in the linked list in 2307 comparisons. series was found in the hash table bucket in 17 comparisons. Total Number of Searches: 8 Total Number of Comparisons in Linked List: 17389 Total Number of Comparisons in Hash Table: 140 Press any key to continue