Implementing Quadratic Probing & Chaining - Search Dictionary
<p>I have a few questions about an assignment that i need to do. It might seem that what im looking for is to get the code, however, what im trying to do is to learn because after weeks of searching for information im lost. I<code>m really new at</code>C`.</p>

<p>Here is the assignment : </p>

<ul>
<li>Given 3 files (<code>foo.txt</code> , <code>bar.txt</code> , <code>foo2.txt</code>) they all have a different amount of words (I need to use dynamic memory).</li>
</ul>

<p>Create a program that ask for a word and tells you if that word is in any of the documents (the result is the name of the document where it appears).</p>

<p>Example : </p>

<ul>
<li>Please enter a word: dog</li>
<li>"dog" is in foo.txt and bar.txt</li>
</ul>

<p>(I guess i need to load the 3 files, create a hash table that has the keyvalues for every word in the documents but also has something that tells you which one is the document where the word is at).</p>

<p>I guess i need to implement: </p>

<ul>
<li>A <code>Hash Function</code> that converts a word into a <code>HashValue</code></li>
<li>A <code>Hash Table</code> that stores the <code>HashValue</code> of every word (But i think i should also store the document index?).</li>
<li>Use of <code>dynamic allocation</code>.</li>
<li>Check for <code>collisions</code> while im inserting values into the hash table (Using <code>Quadratic Probing</code> and also <code>Chaining</code>).</li>
<li>Also i need to know how many times the word im looking for appears in the text.</li>
</ul>

<p>I've been searching about hashmaps implementations, hash tables , quadratic probing, hash function for strings...but my head is a mess right now and i dont really now from where i should start.</p>

<p>so far i`ve read :</p>

<p><a href="https://stackoverflow.com/questions/880559/algorithm-to-get-a-list-of-all-words-that-are-anagrams-of-all-substrings-scrabb/880637#880637">Algorithm to get a list of all words that are anagrams of all substrings (scrabble)?</a></p>

<p><a href="https://stackoverflow.com/questions/16184145/implementing-with-quadratic-probing">Implementing with quadratic probing</a></p>

<p><a href="https://stackoverflow.com/questions/16150867/does-c-have-hash-dictionary-data-structure">Does C have hash/dictionary data structure?</a></p>

<p><a href="https://gist.github.com/tonious/1377667" rel="nofollow noreferrer">https://gist.github.com/tonious/1377667</a></p>

<p><a href="https://stackoverflow.com/questions/7666509/hash-function-for-string">hash function for string</a></p>

<p><a href="http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=(CategoryAlgorithmNotes)" rel="nofollow noreferrer">http://www.cs.yale.edu/homes/aspnes/pinewiki/C(2f)HashTables.html?highlight=(CategoryAlgorithmNotes)</a></p>

<p><a href="https://codereview.stackexchange.com/questions/115843/dictionary-implementation-using-hash-table-in-c">https://codereview.stackexchange.com/questions/115843/dictionary-implementation-using-hash-table-in-c</a></p>

<p>Sorry for my english in advance.</p>

<p>Hope you can help me.</p>

<p>Thanks.</p>

<p><strong>FIRST EDIT</strong></p>

<ul>
<li>Thanks for the quick responses.</li>
<li>I'm trying to put all together and try something, however @Shasha99 I cannot use the <code>TRIE</code> data structure, i'm checking the links you gave me.</li>
<li>@MichaelDorgan Thanks for posting a solution for beginners however i must use Hashing (It's for Algorithms and Structures Class) and the teacher told us we MUST implement a Hash Function , Hash Table and probably another structure that stores important information.</li>
</ul>

<p>After thinking for an hour I tried the following : </p>

<ul>
<li>A Structure that stores the word, the number of documents where it appears and  the index of those documents.</li>
</ul>

<pre class="lang-c prettyprint-override"><code>    typedef struct WordMetadata {
        char* Word;
        int Documents[5];
        int DocumentsCount;
    } WordMetadata;
</code></pre>

<ul>
<li>A function that Initializes that structure</li>
</ul>

<pre class="lang-c prettyprint-override"><code>       void InitTable (WordMetadata **Table) {
            Table = (WordMetadata**) malloc (sizeof(WordMetadata) * TABLESIZE);
            for (int i = 0; i &lt; TABLESIZE; i++) {
                Table[i] = (WordMetadata*) NULL;
            }
        }
</code></pre>

<ul>
<li><p>A function that Loads to memory the 3 documents and index every word inside the hash table.</p></li>
<li><p>A function that index a word in the mentioned structure</p></li>
<li><p>A function that search for the specific word using Quadratic Probing (If i solve this i will try with the chaining one...).</p></li>
<li><p>A function that calculates the hash value of a word (I think i will use <code>djb2</code> or any of the ones i found here <a href="http://www.cse.yorku.ca/~oz/hash.html" rel="nofollow noreferrer">http://www.cse.yorku.ca/~oz/hash.html</a>) but for now : </p></li>
</ul>

<pre class="lang-c prettyprint-override"><code> int Hash (char *WordParam) {

            for (int i = 0; *WordParam != '\0';) {

                i += *WordParam++;

            }

            return (i % TABLESIZE);}
</code></pre>

<p><strong>EDIT 2</strong></p>

<p>I tried to implement something, its not working but would take a look and tell me what is wrong (i know the code is a mess)</p>

<p><strong>EDIT 3</strong> </p>

<p>This code is properly compiling and running, however , some words are not finded (maybe not indexed i' dont know), i'm thinking about moving to another hashfunction as i mentioned in my first message.</p>

<ul>
<li><p>Approximately 85% of the words from every textfile (~ 200 words each) are correctly finded by the program.</p></li>
<li><p>The other ones are ramdom words that i think are not indexed correctly or maybe i have an error in my search function...</p></li>
</ul>

<p>Here is the current (Fully functional) code: </p>



<pre><code>#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;
#define TABLESIZE 4001
#define LINESIZE 2048
#define DELIMITER " \t"

typedef struct TTable {
    char*   Word;               /* The actual word  */
    int     Documents[5];           /* Documents Index */
    int     DocumentsCount;             /* Number of documents where the word exist */
} TTable;


int Hash (char *Word);
void Index (TTable **HashTable, char* Word, int DocumentIndex);
int Search (TTable **HashTable, char* Word);
int mystrcmp(char *s1, char *s2);
char* Documents[] = {"foo.txt","bar.txt","foo2.txt",NULL};


int main() {

    FILE* file;
    TTable **HashTable
    int DocumentIndex;
    char Line[LINESIZE];
    char* Word;
    char* Tmp;

    HashTable = (TTable**) malloc (sizeof(TTable)*TABLESIZE);
    for (int i = 0; i &lt; TABLESIZE; i++) {
      HashTable[i] = (TTable*) NULL;
    }

    for (DocumentIndex = 0; Documents[DocumentIndex] != NULL; DocumentIndex++) {

      file = fopen(Documents[DocumentIndex],"r");
      if (file == NULL) {

          fprintf(stderr, "Error%s\n", Documents[DocumentIndex]);
          continue;

      }


      while (fgets (Line,LINESIZE,file) != NULL) {

          Line[LINESIZE-1] = '\0';
          Tmp = strtok (Line,DELIMITER);

          do {

              Word = (char*) malloc (strlen(Tmp)+1);
              strcpy(Word,Tmp);
              Index(HashTable,Word,DocumentIndex);
              Tmp = strtok(NULL,DELIMITER);
          } while (Tmp != NULL);

      }

        fclose(file);

    }


        printf("Enter the word:");
        fgets(Line,100,stdin);
        Line[strlen(Line)-1]='\0'; //fgets stores newline as well. so removing newline.
        int i = Search(HashTable,Line);
        if (i != -1) {
          for (int j = 0; j &lt; HashTable[i]-&gt;DocumentsCount; j++) {
            printf("%s\n", Documents[HashTable[i]-&gt;Documents[j]]);
            if ( j &lt; HashTable[i]-&gt;DocumentsCount-1) {

                printf(",");
            }
          }
        }

        else {
          printf("Cant find word\n");
        }


        for (i = 0; i &lt; TABLESIZE; i++) {
          if (HashTable[i] != NULL) {

              free(HashTable[i]-&gt;Word);
              free(HashTable[i]);

          }
        }


return 0;
}

/* Theorem: If TableSize is prime and ? &lt; 0.5, quadratic
probing will always find an empty slot
*/
int Search (TTable **HashTable, char* Word) {

    int Aux = Hash(Word);
    int OldPosition,ActualPosition;

    ActualPosition = -1;

    for (int i = 0; i &lt; TABLESIZE; i++) {
      OldPosition = ActualPosition;
      ActualPosition = (Aux + i*i) % TABLESIZE;

      if (HashTable[ActualPosition] == NULL) {
        return -1;
      }

    if (strcmp(Word,HashTable[ActualPosition]-&gt;Word) == 0) {

        return ActualPosition;

    }
    }

    return -1; // Word not found
}


void Index (TTable **HashTable, char* Word, int DocumentIndex) {

    int Aux; //Hash value
    int OldPosition, ActualPosition;

    if ((ActualPosition = Search(HashTable,Word)) != -1) {

        for (int j = 0; j &lt; HashTable[ActualPosition]-&gt;DocumentsCount;j++) {

            if(HashTable[ActualPosition]-&gt;Documents[j] == DocumentIndex) {
              return;
            }

        }

        HashTable[ActualPosition]-&gt;Documents[HashTable[ActualPosition]-&gt;DocumentsCount] = DocumentIndex;        HashTable[ActualPosition]-&gt;DocumentsCount++;
        return;
    }

    ActualPosition = -1;
    Aux = Hash(Word);

    for (int i = 0; i &lt; TABLESIZE; i++) {

        OldPosition = ActualPosition;
        ActualPosition = (Aux + i*i) % TABLESIZE;
        if (OldPosition == ActualPosition) {
          break;
        }

    if (HashTable[ActualPosition] == NULL) {

        HashTable[ActualPosition] = (TTable*)malloc (sizeof(TTable));
        HashTable[ActualPosition]-&gt;Word = Word;
        HashTable[ActualPosition]-&gt;Documents[0] = DocumentIndex;
        HashTable[ActualPosition]-&gt;DocumentsCount = 1;
        return;
    }

    }

    printf("No more free space\n");

}


int Hash (char *Word) {

    int HashValue;
    for (HashValue = 0; *Word != '\0';) {
      HashValue += *Word++;
    }

    return (HashValue % TABLESIZE);
}
</code></pre>