need help on implementing a hash table

[CPT]

Hello everyone, I'm not that much of a talker so I'll get straight to the point: I need to implement a hash table in C++, After reading about this topic and algorithms from the book by Cormen, I started to implement it. I wrote it, but it doesn't work how it should. Ran out of ideas.
this is what I have so far:

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
int a,b,p;

//Here we define our list structure
 typedef struct _List_t{
  char *string;
  struct _List_t *next;
}List_t;

 //Here we define our hashtable itself
 typedef struct _HashTable_t{
  int size;
  List_t **table;
}HashTable_t;


 
 //Here we will create our hashtable and reserve memory for it
  HashTable_t CreateTable(int);
  HashTable_t CreateTable(int size)
   {
    HashTable_t *NewTable;
      NewTable=(HashTable_t*)malloc(sizeof(HashTable_t));
      NewTable->table=(List_t**)malloc(sizeof(List_t));

	  NewTable->size=size;
    //the table elements must be set to NULL
      for(int i=0;i<NewTable->size;i++)
          NewTable->table[i]=NULL;
  return *NewTable;
   }
//Defining the hash function
 unsigned int hash(HashTable_t,int*,int*,int*,char);
 unsigned int hash(HashTable_t hashtable,int *a,int *b,int *p, char str[])
  {
   int hashval=0;
 
   if (str!=NULL)
     {
		 for(int i=0;str[i];i++)
           hashval=str[i]* a);
		   hashval=(hashval+b)%p;
     }
   return hashval%hashtable.size;
  } 

//We need to define our search function
 List_t search(HashTable_t, char[]);
 List_t search(HashTable_t hashtable, char str[])
    {
    List_t *list;
    unsigned int hashval;
     list=(List_t*)malloc(sizeof(List_t));
	 hashval=hash(hashtable,a,b,p,str);
        for(list=hashtable.table[hashval];list->next!=NULL;list=list->next)
         if(strcmp(str,list->string))
          return *list;
     }

//We need the insertion function
 int insert(HashTable_t,char[]);
 int insert(HashTable_t hashtable, char str[])
  {
   List_t *NewList;
   List_t *CurentList;
   unsigned int hashval=hash(hashtable,*a,*b,*p,str);
  //CurentList is used as a sentinel, to see if our key is already in the table
     CurentList=(List_t*)malloc(sizeof(List_t));
	 *CurentList=search(hashtable,str);
	   if(CurentList)
		   printf("Element already  there, try again!");
	   free(CurentList);
	   exit(0);
//If the elemnt is not redundant we'll insert it
     NewList=(List_t*)malloc(sizeof(List_t));
     
	 strcpy(NewList->string, str);
	 NewList->next=hashtable.table[hashval];
     hashtable.table[hashval]=NewList;
   return 0;
  }

//The Clearkey function only erases the given key, Clear Table on the other hand erases the entire table

void ClearKey(HashTable_t hashtable,char str[]);
void ClearKey(HashTable_t hashtable,char str[])
 {
	List_t *list,*temp;
	int hashval=hash(hashtable,*a,*b,*p,str);
      //The index of the table is actually the head of the list
	  list=hashtable.table[hashval];
	  while(list!=NULL)
	  { 
      //If we found what we are looking for erase it
	    if(list->string=str)
	      {
	      temp=list;
	      list=list->next;
	      free(temp);
	      }
	   }
 }

 void ClearTable(HashTable_t);
 void ClearTable(HashTable_t *hashtable)
  {
	List_t *list,*temp;
	
	 if(hashtable!=NULL)
	   for(int i=0;i<hashtable->size;i++)
		{
		 list=hashtable->table[i];
	     while(list!=NULL)
	      {
		  temp=list;
		  list=list->next;
		  free(temp);  
	      }
	    }
	free(hashtable->table);
	free(hashtable);
  }

void main()
{
HashTable_t MyHashTable;
char s[20];
int a,b,p,selection,TableSize=12;

MyHashTable=CreateTable(TableSize);

printf("HashTable created!\n");
for(int i=0;i<MyHashTable.size;i++)
  printf("%d",MyHashTable.table[i]);
  printf("\n");
   
printf("The hash function is (A*Key+B)Mod P)Mod %d\n",MyHashTable.size);
   printf("enter the value for A:");scanf("%d",&a);
   printf("enter the value for B:");scanf("%d",&b);
   printf("enter the value for P:");scanf("%d",&p);

printf("Select an operation\n");
printf("1. Insert   2. Search   3. Erase   Other=Quit\n");
  scanf("%d",&selection);
  printf("Your selection is:%d",selection);

printf("\nEnter the key:");
 scanf("%c",s);

while(selection<5){
	if(selection=1)
		insert(MyHashTable,s);
	else if(selection=2)
		search(MyHashTable,s);
	else if(selection=3)
        ClearKey(MyHashTable,s);
	else
		printf("Invalid Selection");
	         }
getch();
}

[mike_2000_17]

When I look at this code, I remember why people don't program in C so much any more... This post probably belongs in the C programming forum instead.

Anyhow, there is one definite problematic line, that is line 28. I found it, because that's always the first thing I look at when looking for a bug: where / how is memory allocated, where / when / how is the memory freed, where / how is it used, then is the algorithm sound. (in that order of priority!). So, the error is that you allocate the space for one struct object of type List_t, then assign the resulting pointer to a pointer-to-pointer to type List_t, and then fill it up in a for-loop with bound "size". So my awesome power of deduction tells me you intended that line 28 to be:

NewTable->table = (List_t**) malloc( size * sizeof( List_t* ) );

That should help, for the rest, it's harder to tell where the problems might be, try going through that same order of priority in checking your code.

BTW, why do you double each function definition? It's the first time I see that and it looks horrible! And it is completely useless. There is no point in putting the prototype of the function right before its definition. A prototype announces the existence of a function before it is defined, to the code that follows. But if, immediately after, you have the definition itself, the prototype is completely meaningless.

[Narue]

>After reading about this topic and algorithms from the book by Cormen, I started to implement it.
I've written some articles on the subject with C as the implementation language. You may find them more helpful than your book as the code can be plugged in directly rather than requiring translation from pseudocode. They consist of hashing, hash tables, and a sample implementation.

[CPT]

By the way I forget to mention that my project has some requirements(sorry about that), these are:
-the program must compile with at least 2 diferent compilers;
-the program must be modularized(must contain at least 2 .c files and at least one .h(header) file;
-input from stdin, output to stdout(for testing purposes stdin and stdout will be redirected to the command line);

[CPT]

I took in consideration what both of you said so I did some modifications on the program:
this is my hash function(thanks to narue's links)

//The hash function uses Dan Bernstein's algotihm
 
 unsigned hash(char *str)
  {
  char *p=str;
  unsigned hashval;
  int i;
	for(i=0;p[i];i++)
       hashval=33*hashval +p[i];
   return hashval;
  }

, this is my Create Table function:

//Here we will create our hashtable and reserve memory for it
  HashTable_t CreateTable(int size)
    {
	  int i;
      HashTable_t *NewTable;
      
	  NewTable=(HashTable_t*)malloc(sizeof(HashTable_t));
      NewTable->table=(List_t**)malloc(sizeof(List_t*));
      
	  NewTable->size=size;
      for(i=0;i<=NewTable->size;i++)
         NewTable->table[i]=NULL;
      return *NewTable;
    }

, this is the search function

List_t search(HashTable_t *NewTable, char *str)
    {
    List_t *list;
    unsigned int hashval;
     
	hashval=hash(str);
	list=NewTable->table[hashval];
     while(list !=NULL)
	 {
	    if(list->string!=str)
		   list=list->next;
	 }
	 return *list;
     }

the insertion function

void insert(HashTable_t *NewTable, char *str)
  {
   List_t *TempList,*NewList;
   unsigned int hashval=hash(str);
   
   TempList=NewTable->table[hashval];
   while(TempList !=NULL)  //we position ourselves to the last element of the list
      {
	    TempList=TempList->next;
	  }
   NewList=(List_t *) malloc(sizeof(List_t));
   NewList->string=str;
   NewList->next=NULL;
  
   TempList->next=NewList;
  }

the Erase key function

void EraseKey(HashTable_t *NewTable,char *str)
 {
	List_t *List,*TempList;
	int hashval=hash(str);
	  
	*List=search(NewTable,str);//the first element of the list will always be the one we are erasing
	TempList->next=List->next;
	List->next=TempList;
	free(List);
	
 }

and last the clear table function

void ClearTable(HashTable_t *NewTable,char *str)
  {
	List_t *list,*temp;
	int i;
	
	while(NewTable!=NULL)
	{
	   for(i=0;i<=NewTable->size;i++)
		{
		 list=NewTable->table[i];
	     while(list!=NULL)
	       {
		   temp=list;
		   list=list->next;
		   free(temp);  
	       }
	    }
	}
	free(NewTable->table);
	free(NewTable);
  }

I still don't know how to code the main function to use the above functions