#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    15
    Rep Power
    0

    Need help with creating my hash table


    Hello all! I am having difficulty getting my program to run. I have looked and looked many times trying to figure out what I am doing wrong. I have a hunch that it's my load function that's acting up, but from my perspective, my creation of my singly linked list looks good. From the creation of my singly linked list, does anything stand out as being abnormal to anyone? Please help! Thanks alL!





    Code:
    typedef struct Node {    
    
     char word[LENGTH+1];  
    
     struct Node *Next;    
     } Node;
    
    
    typedef struct hash_table_t {
    
    int size;
    struct Node **table;
    } hash_table_t;
    
    
    unsigned int hash(char(str[])
    {
    unsigned int hashval;
    
      for(; *str!='\0'; str++)
    hashval=*str+(hashval<<5)-hashval;
    return hashval % hashtable->size;
    }
     
    
    hash_table_t  *create_hash_table(int size)
    {
    hashtable = malloc(sizeof(hash_table_t));
    
    if (hashtable == NULL) 
    {
    
    return NULL;
    
    }
    
     hashtable->table= malloc(size* sizeof(struct Node *) )  ;
    
    if (hashtable->table== NULL)
    {
      return NULL;
    }
    for(int i=0; i<size; i++) 
    { 
      hashtable->table[i]=NULL;
      hashtable->size =size;
    
    }
     return hashtable;
    }
    
    
    boool load(const char* dictionary)
    {
    File *inptr;    
    
    Node* TempNode=NULL;    
    Node* new_node=NULL;
    Node* Head=NULL;
    
    char buffer[46];
    
    unsigned int hashval;
    
    int j=0;
    int count=0;    
    int update_counter=0;
    
    inptr= fopen(dictionary, "r"); 
    
    if (inptr == NULL)
    {
        printf("Could not open dictionary file");
        printf("\n");
        return 0;
    } 
    
    int ch = fgetc(inptr);   
    for ( ;; )     
    {        
        if ( ch == EOF )    //determines how many words are in the file        
        {           
            break;                
        }        
        if (isalpha(ch) || isdigit(ch) || ispunct(ch))        
        {           
            update_counter = 1;          
        }         
        if (isspace(ch) && update_counter )      
        {           
            count++;           
            update_counter = 0;       
        }     
    }
    if (update_counter) 
    {
        count++;
    } 
    
    sizeOfDictionary=count;
    rewind(inptr);
    
    hashtable=create_hash_table(sizeOfDictionary);
    
    while(fread(buffer,sizeof(buffer),1,inptr)!=0)
    {        
        if(Head==NULL)
        {
            hashval = hash(buffer);
            Head = malloc(sizeof(Node));
            strcpy(&Head->word[j],buffer); 
            Head->Next = hashtable->table[hashval];
    
            hashtable->table[hashval]=Head;
            Head=Head->Next;
    
            TempNode =  Head; 
        }
        else if(Head!=NULL)
        {
            new_node = malloc(sizeof(Node));
            hashval = hash(buffer);
            strcpy(&new_node->word[j],buffer);
            new_node->Next = hashtable->table[hashval];
            hashtable->table[hashval]=new_node;
            TempNode=new_node->Next;        
        } 
    }
    return true;
    }
    
    bool check(const char* word)
    {
     
     /**
     * Returns true if word is in dictionary else false.
     */
    int i=0;
    char DuplicateArray[LENGTH];
    int sizevalue=0;
    Node* NodePointer=NULL;
    unsigned int hashval=0;
    int counter=0;
    sizevalue=strlen (word);
        
    strncpy(&DuplicateArray[counter], word,sizevalue);
    //DuplicateArray[LENGTH] = '\0';
    hashval=hash(DuplicateArray);
    //NodePointer->word= '\0';       
     
     
       
    
     
     
     
     
       
        while ( DuplicateArray[i] != '\0' )
        {
       
        DuplicateArray[i] = tolower(DuplicateArray[i]);    
         
          i++;
          }
      
              
              
    
    
    
    
     
    
    printf("%s",NodePointer->word);
    
    
    
    
       for (NodePointer=hashtable->table[hashval];NodePointer !=NULL;NodePointer=NodePointer->Next)
          {
           i=0;
          
          i=strcmp(&DuplicateArray[sizevalue],&NodePointer->word[sizevalue]);
    
      
          if (i==0) 
             {  
              return true;
             }
          
          }
    
       return false;
       }
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    > char buffer[46];
    Why isn't this the same as char word[LENGTH+1];

    > while(fread(buffer,sizeof(buffer),1,inptr)!=0)
    This does not read words.
    This reads fixed sized blocks of 46 bytes. What is more, there is no guaranteed \0 at the end of buffer, so your following str.... functions are screwed.

    Use
    while ( fscanf(inptr,"%s",buffer) == 1 )

    > strcpy(&Head->word[j],buffer);
    j is always 0, so all you're doing is
    strcpy(Head->word,buffer);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    15
    Rep Power
    0
    Originally Posted by salem
    > char buffer[46];
    Why isn't this the same as char word[LENGTH+1];

    > while(fread(buffer,sizeof(buffer),1,inptr)!=0)
    This does not read words.
    This reads fixed sized blocks of 46 bytes. What is more, there is no guaranteed \0 at the end of buffer, so your following str.... functions are screwed.

    Use
    while ( fscanf(inptr,"%s",buffer) == 1 )

    > strcpy(&Head->word[j],buffer);
    j is always 0, so all you're doing is
    strcpy(Head->word,buffer);


    I have no idea why I didnt declare it the same as char[length+1], very good question. I always thought strcpy does a copy without incrementation of the array? Am I wrong on that?
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    Are you now using fscanf ?

    > I always thought strcpy does a copy without incrementation of the array? Am I wrong on that?
    This makes no sense.

    You wrote this
    > strcpy(&Head->word[j],buffer);
    j is always 0, so it becomes
    strcpy(&Head->word[0],buffer);
    or just simply
    strcpy(Head->word,buffer);
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    15
    Rep Power
    0
    Originally Posted by salem
    Are you now using fscanf ?

    > I always thought strcpy does a copy without incrementation of the array? Am I wrong on that?
    This makes no sense.

    You wrote this
    > strcpy(&Head->word[j],buffer);
    j is always 0, so it becomes
    strcpy(&Head->word[0],buffer);
    or just simply
    strcpy(Head->word,buffer);

    Yes I am. I have gotten over the seg fault I was experiencing, and it is reading from the buffer into the new_node->word array, which is what I want.Thank you for that! :). For whatever reason though, I cant get it to compare with the data coming from the main function(i.e. the const.char word parameter in my check function). Any thoughts on that? If you have any, or want to share of course. I dont want to bug you or become an annoyance lol..
  10. #6
  11. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    I see no functions called 'main' or 'check', so I really don't know.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    15
    Rep Power
    0
    Originally Posted by salem
    I see no functions called 'main' or 'check', so I really don't know.

    I just posted load.
  14. #8
  15. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,379
    Rep Power
    1871
    > sizevalue=strlen (word);
    OK (so far).

    > strncpy(&DuplicateArray[counter], word,sizevalue);
    You seem to lack a fundamental understanding of strings, char arrays and so on. Why do you keep writing &array[0]?
    Also, strncpy() where the length is set by the source string is no better than using strcpy() to begin with.

    > hashval=hash(DuplicateArray);
    OK.

    > DuplicateArray[i] = tolower(DuplicateArray[i]);
    Nowhere else in the code do you work on lower cased strings.
    Besides, you've already computed the hash for the string in whatever native case the string was in.
    Does your hash always produce the same results for "Hello" "HELLO" "hello" "heLLo" ?

    > i=strcmp(&DuplicateArray[sizevalue],&NodePointer->word[sizevalue]);
    Once again, you're messing with your head with the &array[pos] notation.
    Except this time, you're pointing at the ENDS of both strings (recall the earlier value)
    If you took out all the DuplicateArray stuff, and simply did

    hashval=hash(word);

    and then in the loop
    i=strcmp(word,NodePointer->word);

    then it should work fine at finding words you've already stored in your hash lists.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    15
    Rep Power
    0
    Originally Posted by salem
    > sizevalue=strlen (word);
    OK (so far).

    > strncpy(&DuplicateArray[counter], word,sizevalue);
    You seem to lack a fundamental understanding of strings, char arrays and so on. Why do you keep writing &array[0]?
    Also, strncpy() where the length is set by the source string is no better than using strcpy() to begin with.

    > hashval=hash(DuplicateArray);
    OK.

    > DuplicateArray[i] = tolower(DuplicateArray[i]);
    Nowhere else in the code do you work on lower cased strings.
    Besides, you've already computed the hash for the string in whatever native case the string was in.
    Does your hash always produce the same results for "Hello" "HELLO" "hello" "heLLo" ?

    > i=strcmp(&DuplicateArray[sizevalue],&NodePointer->word[sizevalue]);
    Once again, you're messing with your head with the &array[pos] notation.
    Except this time, you're pointing at the ENDS of both strings (recall the earlier value)
    If you took out all the DuplicateArray stuff, and simply did

    hashval=hash(word);

    and then in the loop
    i=strcmp(word,NodePointer->word);

    then it should work fine at finding words you've already stored in your hash lists.
    Its still not returning the any misspelled word. Just out of curiousity, if I have a pointer to the an array within a struct, do I need to null terminate it?
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    15
    Rep Power
    0
    Just out of curiousity, would you suspect that that strcmp is reading some extra characters and that buffer(the char array I created within the load functoin) needs to be null terminated in order to get a accurate comparison?

IMN logo majestic logo threadwatch logo seochat tools logo