Thread: Hash Table Problem

  1. #1
    Unregistered
    Guest

    Hash Table Problem

    I'm trying to get text from a file and assign the individual words to a hash table - that's all!! I have the necessary functions but I'm having great difficulty putting it all together. Here is my main other stuff so far (I know - terrible!):

    #include <stdio.h>
    #define HASHSIZE 997

    typedef struct listNode
    {
    char Value;
    struct listNode *next;
    }HashTable[HASHSIZE];

    int hash(char *key);
    /*void CreateTable(char Table);*/
    void insert (int key);
    int search ( int key);
    int delete ( int key);

    int main()
    {
    FILE *file;
    int count;
    char word[15];

    if
    ((file = fopen("myfile.txt","r")) == NULL)
    printf("File could not open!!\n");

    /* This section below could be made into a separate create table function - not sure of parameters though*/

    else
    for(count = 0; count < HASHSIZE ; count++)
    {
    /* Getting an error before '[' below */
    HashTable[count] = NULL;
    }

    fscanf (file,"%s",word);
    hash(word);
    insert(hash_val);

    return 0;
    }

    I'm mainly not sure about the passing of parameters in this situation.

    Any tips are much appreciated (sorry about the long post).

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    typedef struct listNode
    {
    char Value;
    struct listNode *next;
    }HashTable[HASHSIZE];


    If you want to store words, then this needs to be something like
    typedef struct listNode
    {
    char Value[15]; // or perhaps a char* for variable length words you allocate
    struct listNode *next;
    }HashTable[HASHSIZE];


    In your loop
    HashTable[count].next = NULL;

  3. #3
    Unregistered
    Guest
    Still getting that damn parse error before the '[' in the for loop. (This line "HashTable[count] = NULL; ").

    Also, is the call to the insert function ok?

    Thanks so much.

  4. #4
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Unregistered said:
    >Still getting that damn parse error before the '[' in the for loop. (This line "HashTable[count] = NULL; ").

    Salem said:
    >In your loop
    >HashTable[count].next = NULL;
    --------------------------------------------------------------
    >Also, is the call to the insert function ok?
    What insert function? You only provided a prototype. And the variable hash_val is not defined.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  5. #5
    Unregistered
    Guest
    When I said I'm still getting the parse error I meant I changed the code. Salem's code is right - there's something else that's not working with it and it's driving me mad - I've spent hours on it.

    Hope this additional code helps:


    int hash(char *key)
    {
    unsigned int hash_val = 0;

    while(*key != '\0')
    hash_val += *(key++);

    return (hash_val % HASHSIZE);
    }


    void insert (int key)
    {
    struct listnode *newptr,
    *currentptr,
    *previousptr;
    int pos;

    newptr=(listnode *) malloc (struct listnode);

    if (newptr == NULL)
    error("Error - Not Enough Memory!\n");

    else
    {
    newptr->value = key;
    newptr->next = NULL;
    pos=hash(key);
    if (HashTable[pos] == NULL)
    HashTable[pos] = newptr;
    else
    {
    currentptr = HashTable[pos];
    while (currentptr != NULL)
    {
    previousptr = currentptr;
    currentptr = currentptr->next;
    }
    previousptr->next = newptr;
    }
    }
    }


    THANKYOU.

  6. #6
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Post your updated code (the last lot you posted is for a different function). Include the error message from the compiler.
    Last edited by Hammer; 05-20-2002 at 06:02 AM.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  7. #7
    Unregistered
    Guest
    This main and the 2 previous functions are what I'm trying to get working at the moment.

    #include <stdio.h>

    #define HASHSIZE 997

    typedef struct listNode
    {
    char Value[15];
    struct listNode *next;
    }HashTable[HASHSIZE];

    int hash(char *key);
    void insert (int key);
    int search ( int key);
    int delete ( int key);

    int main()
    {
    FILE *file;
    int count;
    char word[15];

    for (count = 0; count < HASHSIZE ; count++)
    HashTable[count].next = NULL;

    if
    ((file = fopen("myfile.txt","r")) == NULL)
    printf("File could not open!!\n");

    fscanf(file,"%s",word);
    hash(word);
    /*insert(hash_val);*/

    return 0;
    }


    Ta Hammer.

  8. #8
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    Your typedef'ing is incorrect. Compare this to what you have.
    Code:
    typedef struct lNode	
    {
    	char Value[15];
    	struct lNode *next; /* [EDITED] */
    } listNode;
    
    listNode HashTable[HASHSIZE];
    Doing the typedef this way means
    - You have a struct definition called lNode, so you can reference it via struct lNode

    - Your typedef'd name is listNode. So you can reference your struct lNode with the name listNode.

    - The HashTable is now a proper array.

    You could have also done it this way, which means you don't have a typedef'd name.
    Code:
    struct listNode
    {
    	char Value[15];
    	struct listNode *next;
    } HashTable[HASHSIZE];
    Also, this
    Code:
    if ((file = fopen("myfile.txt", "r")) == NULL) 
         printf("File could not open!!\n");
    needs to do something else, like return. It's no good printing an error message then just carrying on regardless.

    Please use code tags in future, too.
    Last edited by Hammer; 05-20-2002 at 08:45 AM.
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  9. #9
    Unregistered
    Guest
    In the struct:

    typedef struct lNode
    {
    char Value[15];
    struct listNode *next;
    } listNode;

    listNode HashTable[HASHSIZE];


    Should the pointer be:

    struct lNode *next;

    ????

    Also, is my parameter passing between functions right? (I don't think they are).

  10. #10
    End Of Line Hammer's Avatar
    Join Date
    Apr 2002
    Posts
    6,231
    New version:
    Code:
    typedef struct lNode
    {
    	char Value[15];
    	struct lNode *next;
    } listNode;
    
    listNode HashTable[HASHSIZE];
    An oversight by me <sorry>!

    >Also, is my parameter passing between functions right? (I don't think they are).
    Which ones are you querying?
    When all else fails, read the instructions.
    If you're posting code, use code tags: [code] /* insert code here */ [/code]

  11. #11
    Unregistered
    Guest

    Unhappy

    I've only posted a main and 2 functions here.

    If they are compiled there are quite a few errors - a lot due to the parsing I think.

  12. #12
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Well
    Code:
    newptr=(listnode *) malloc (struct listnode);
    Is certainly wrong, you should have
    newptr = malloc(sizeof (struct listNode));

    I think your hash function will work, but it's not supposed
    to be the best. Experiement and see how many collisions you get.

    Other than that, you probably do not want to do your hash table this way since you can only create one hash_table which limits yourself.

    Try to define your hash table like this

    Code:
        
    struct hash_table {
            struct node {
                    char* s;
                    struct node* next;
            } A[HASHSIZE];
    };
    
    typedef struct hash_table hash_table;
    And then have functions
    void hash_init(hash_table* h);
    hash_init just sets all of h->A[i] to NULL.

    void hash_insert(hash_table* h, char* s);
    hash_insert inserts s into the beginning of the list h->hash(s)] if s isn't already in there.

    void hash_delete(hash_table* h, char* s);
    hash_delete looks for s in the list h->A[hash(s)] and deletes
    it if found.

    void hash_destroy(hash_table* h);
    Destroys the list h->A

    char* hash_find(hash_table* h, char* s);
    hash_find looks for s in h->A[hash(s)]. If s is found it
    returns s, otherwise it returns NULL.

    Now, for example, you could implement a simple look up in the dictionary with

    if (hash_find(h, word) != 0) printf("Valid word\n");

  13. #13
    Unregistered
    Guest
    Thanks Nick, I fixed the malloc function. I tried the other stuff but I was getting lost with all the changes. The one hash table is all that is required.

    Could someone please point out what they think is wrong with my 'insert' function. I have commented where the problem is. I seem to be referencing things wrong but I can't see where or why.

    I have posted the lot (sorry) so you can see where I'm getting values etc, thought it might make it easier.

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <unistd.h>

    #define HASHSIZE 997

    typedef struct Node
    {
    char Value[15];
    struct Node *next;
    }listNode;

    listNode HashTable[HASHSIZE];

    int hash(char *key);
    int insert(char *key);


    int main()
    {
    FILE *file;
    int count;
    char word[15] = {'\0'};

    for (count = 0; count < HASHSIZE ; count++)
    {
    HashTable[count].next = NULL;
    }

    if
    ((file = fopen("myfile.txt","r")) == NULL)
    printf("File could not open!!\n");
    return(EXIT_SUCCESS);

    while(fscanf(file,"%s",word) == 1)
    {
    hash(word);
    insert(word);
    }
    fclose(file);
    return 0;
    }


    int hash(char *key)
    {
    unsigned int hash_val = 0;

    while(*key != '\0')
    hash_val += *(key++);

    return(hash_val % HASHSIZE);
    }

    int insert (char *key)
    {
    struct listNode *newptr,
    *currentptr,
    *previousptr;
    int pos = 0;

    newptr = malloc(sizeof(listNode));

    if (newptr == NULL){
    printf("Not Enough Memory!\n");
    exit(EXIT_SUCCESS);
    }

    /* ERRORS FROM HERE DOWN */

    else
    newptr->Value = key;
    newptr->next = NULL;
    pos = hash(key);

    if (HashTable[pos] = NULL)
    HashTable[pos] = newptr;
    else
    {
    currentptr = HashTable[pos];
    while (currentptr != NULL)
    {
    previousptr = currentptr;
    currentptr = currentptr->next;
    }
    previousptr->next = newptr;
    }
    return 1;
    }


    THANKS.

  14. #14
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    The problem is not just with your insert. You really defined your hash table wrong.
    Here's some code I think should work.

    Code:
    #include <stdio.h> 
    #include <stdlib.h> 
    #include <string.h> 
    
    #define HASHSIZE 997 
    #define FILENAME "myfile.txt"
    
    typedef struct Node  { 
    	char Value[128]; 
    	struct Node *next; 
    } listNode; 
    
    listNode* HashTable[HASHSIZE]; 
    
    int hash(char *key); 
    int hash_insert(char *key); 
    char* hash_find(char* key);
    void hash_destroy();
    
    int main() 
    { 
    	FILE *file; 
    	int count; 
    	char word[15] = {'\0'}; 
    	int quit = 0;
    	char* p;
    
    	for (count = 0; count < HASHSIZE ; count++)  { 
    		HashTable[count] = NULL; 
    	} 
    
    	if  ((file = fopen(FILENAME, "r")) == NULL) {
    		fprintf(stderr, "File could not open!!\n"); 
                   		return(EXIT_FAILURE); 
    	}
    	while(fscanf(file,"%s",word) == 1)  { 
    		hash_insert(word); 
    	} 
    	fclose(file); 
    
    	while(!quit) {
    		printf("Enter a word (Q to quit): ");
    		fflush(stdout);
    		if (fgets(word, sizeof word, stdin) != NULL) {
    			p = strchr(word, '\n');
    			if (p != NULL)
    				*p = '\0';
    			if ((word[0] == 'q' || word[0] == 'Q') && word[1] == '\0')
    				quit = 1;
    			else {
    				if (hash_find(word) != NULL)
    					printf("Word in dictionary\n");
    				else
    					printf("Word not in dictionary\n");
    			}
    		}
    	}
    	hash_destroy();
    
    	return 0; 
    } 
    
    
    int hash(char *key) 
    { 
    	unsigned int hash_val = 0; 
    
    	while(*key != '\0') 
    		hash_val += *(key++); 
    
    	return(hash_val % HASHSIZE); 
    } 
    
    char* hash_find(char* key)
    {
    	listNode* curr;
    	int pos;
    
    	pos = hash(key);
    	curr = HashTable[pos];
    	while(curr != NULL) {
    		if (!strcmp(curr->Value, key)) 
    			return key;
    		curr =  curr->next;
    	}
    
    	return NULL;
    }
    
    int hash_insert (char *key) 
    { 
    	listNode *newptr, *curr; 
    	int pos;
    
    	pos = hash(key);
    
    	/* make sure it's not already in the hash table */
    	curr = HashTable[pos];
    	while(curr != NULL) {
    		if (!strcmp(curr->Value, key)) 
    			return 1;
    		curr = curr->next;
    	}
    
    	newptr = malloc(sizeof(listNode)); 
    	if (newptr == NULL){ 
    		printf("Not Enough Memory!\n"); 
    		exit(EXIT_SUCCESS); 
    	} 
    	strcpy(newptr->Value, key); 
    
    
    	newptr->next = NULL; 
    	
    	if (HashTable[pos] == NULL) 
    		HashTable[pos] = newptr; 
    	else  {
    		listNode* headptr = HashTable[pos];
    		HashTable[pos] = newptr;
    		HashTable[pos]->next = headptr;
    	} 
    	return 1; 
    } 
    
    void hash_destroy()
    {
    	int i;
    	listNode* curr;
    	listNode* tmp;
    
    	for (i = 0; i < HASHSIZE; i++)  {
    		curr = HashTable[i];
    		while(curr != NULL) {
    			tmp = curr->next;
    			free(curr);
    			curr = tmp;
    		}
    	}
    }

  15. #15
    Unregistered
    Guest
    THANKS SO MUCH NICK. YOUR TIME IS APPRECIATED.

    (I'm getting a core dump after compiling, but I will fix that).

    THANKS AGAIN.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. trying to make a hash table......trouble w/ memory?
    By cuizy in forum C Programming
    Replies: 3
    Last Post: 05-11-2009, 04:47 PM
  2. Hash Table outputting incorrect number
    By Paul Skinner in forum C Programming
    Replies: 4
    Last Post: 11-20-2008, 06:19 AM
  3. Hash Table implementation
    By supaben34 in forum C++ Programming
    Replies: 6
    Last Post: 09-26-2003, 12:48 PM
  4. Problem with Hash Table Linear Probing
    By kirby1024 in forum C Programming
    Replies: 5
    Last Post: 10-23-2002, 06:03 AM
  5. help with creating a hash table
    By newbie40 in forum C++ Programming
    Replies: 3
    Last Post: 08-15-2002, 07:31 PM