DS-Assignment 2 Solved

For this assignment, 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). It is OK if you share the words with classmates for this. 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:

1.                                         char * searchWord: word to search for (entered by the user)

2.                                         struct linkedList * linkedList: linked list to search (in your program, you can call the linked list node struct anything that makes sense)

3.                                         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 numberequals 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 the C course notes 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.