Thread: hashing with linked list

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    67

    hashing with linked list

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    typedef struct List { char *word; struct List *next; } List;
    
    #define HASHSIZE 65536
    #define LEN 50
    
    static struct List *hashtab[HASHSIZE];
    
    static FILE *open_file (char *file, char *mode)
    {
      FILE *fp = fopen (file, mode);
    
      if (fp == NULL){
        perror ("Unable to open file");
        exit (EXIT_FAILURE);
      }
    	return fp;
    }
    
    int is_punctuation (int a)
    {
        return a == ' ' || a == '\n' ||
               a == EOF || a == ',' || 
               a ==';' || a =='.'||
               a =='!' || a =='?' || 
               a ==':' || a =='`';
    }
    
    unsigned rot_hash (void *key, int len)  // Rotating hash
    {
    	unsigned char *p = key;
    	unsigned h = 0;
    	int i;
    	
    	for (i = 0; i < len; i++)
    		h = (h << 4) ^ (h >> 28) ^ p[i];
    	return h % HASHSIZE;
    }
    
    struct List *lookup (char *s, int x)
    {
    	struct  List *np;
    	
    	for (np = hashtab[rot_hash(s, x)]; np != NULL; np = np -> next)
    		if (strcmp (s, np -> word) == 0)
    			return np;
    		return NULL;
    }
    
    int install (char *name, int x)
    {
    	struct List *current_list;
    	struct List *new_list;
    	unsigned int h = rot_hash (name, x);
    	if ((new_list = malloc (sizeof (List))) == NULL)
    		return 1;
    	current_list = lookup (name, x);
    	if (current_list != NULL)
    		return 2;
    	new_list -> word = strdup (name);
    	new_list -> next = hashtab[h];
    	hashtab[h] = new_list;
    	return 0;
    }
    		
    	
    int main (int argc, char *argv[])
    {
    	int x, i, k, count, comp;
    	char a, ans, word[LEN];
    	x = 0;
    	k = 0;
    	FILE *fp = open_file (argv[1], "r");
    	do{
    		a = fgetc (fp);
    		if (is_punctuation(a)){
    			if (x != 0){
    				word[x] = '\0';
    				k = install (word, x);
    				printf ("%d\n", k);
    				x = 0;
    				}
    		}else{
    			word[x] = tolower(a);
    			x++;
    			}
    	} while (a != EOF);
    	fclose (fp);
    	return 0;
    }
    i need it to read in a value into a hashtable and if there is a collision it inserts the word into a linked list. can anyone tell me if my install func is correct as i can't think of a way of testing it until i do search function later.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Your lookup function is correctly written, but not correctly indented (the return NULL statement is not part of the for loop). Otherwise, everything looks fine.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  2. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  3. array, linked list & hashing
    By laasunde in forum C++ Programming
    Replies: 5
    Last Post: 05-13-2003, 11:05 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM