Thread: Array of Linked Lists - Hash table

Hello,
I am trying to write a program that simulates a hash table using chaining to prevent collision. I'm still kind of weak on linked lists so I am having trouble trying to work with an array of linked lists. The problem I am having is that if the index value that the hash function produces is a repetition then i need to add a node to the linked list in that array element. Code compiles but output is incorrect, can anybody tell me what I am doing wrong.
Thanks

Code:

while((fscanf(finp, "%s", string))!= EOF)
    {
      i = hash_function_one (string, size);

      if(curr[i]->string == NULL)
        {
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
        }
      if(curr[i]->string != NULL)
        {
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          curr[i]->next = head;
          head = curr[i];
        }
    }

Originally Posted by FortinsM3

Ahh yes, Ok i changed the second if to just an else. The output changed a little but is still incorrect. See anything else?

See my reply in post #2 and if that's that then the next element of the header node points to NULL ie

Code:

if(curr[i]->string == NULL)
{
    curr[i] = (list*)malloc(sizeof(list));
    strcpy(curr[i]->string, string);
    head = curr[i];
    head->next = NULL;
}

Originally Posted by FortinsM3

Ahh yes, Ok i changed the second if to just an else. The output changed a little but is still incorrect. See anything else?

It's not the string its the value produced from hash function, but in that case it just needs to be a single node in that array element. There is only 1 array, each element being LL with 1 or more nodes.
p.s. It does not matter where in the list I add that node, as long as it is in the right list.

Ah! yes I meant that a linked list is started from a new element of that array else you just add another node to the head of an exisiting linked list.

Yes exactly, still nothing though. code looks like this:

Code:

while((fscanf(finp, "%s", string))!= EOF)
    {
      i = hash_function_one (string, size);

      if(curr[i]->string == NULL)
        {
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          head = curr[i];
          head->next = NULL;
        }

      else
        {
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          curr[i]->next = head;
          head = curr[i];

        }

    }

Can you post the part of the code where the array curr[] is defined and the hash func too.

Code:

struct hash_list {
  char string[15];
  int val;
struct hash_list *next;
};
typedef struct hash_list list;

int main(int argc, char *argv[])
{
  int hash_function_one(char *s, int T);

  list *curr[MAXSIZE], *head, *temphead;

Here is the print loop(which maybe im messing up), and the function. I tested the function and it outputs the correct indexes

Code:

 for(i=0; i<17;i++)
    {
      printf("\n");
      while(curr[i])
        {
          printf("%s  ", curr[i]);
          curr[i] = curr[i]->next;
        }

    }

}

int hash_function_one (char *s, int T)
{
  int h = 0, a = 127, temp;

  for (; *s != 0; s++)
    {
      temp = (a * h + *s);
      if (temp < 0)
        temp = -temp;
      h = temp % T;
    }
  return h;
}

I think i got it, just had to add this.

Code:

else
        {
          head = curr[i]; // <-this
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          curr[i]->next = head;
          head = curr[i];
        }

how about the entire code as it's hard to piece it together

Maybe you meant temphead as in.

Code:

else
        {
          temphead = curr[i];
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          curr[i]->next = temphead;
          head = curr[i];
        }

Working code! Thanks for help again ItcBitc

Code:

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

#define MAXSIZE 10000


struct hash_list {
  char string[15];
  int val;
struct hash_list *next;
};
typedef struct hash_list list;

int main(int argc, char *argv[])
{
  int hash_function_one(char *s, int T);

  list *curr[MAXSIZE], *head, *temphead;
  FILE *finp, *fout;
  int char_int;
  int size;
  int hash;
  int i;
  char string[15];
  char *infile;
  char *outfile;


  infile = argv[1];
  outfile = argv[2];
  finp = fopen(infile, "r");
  fout = fopen(outfile, "w");
  head = NULL;


  fscanf(finp, "%d", &size);
  while((fscanf(finp, "%s", string))!= EOF)
    {
      i = hash_function_one (string, size);

      if(curr[i]->string == NULL)
        {
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          head = curr[i];
          head->next = NULL;
        }

      else
        {
          head = curr[i];   //<- had to add this
          curr[i] = (list*)malloc(sizeof(list));
          strcpy(curr[i]->string, string);
          curr[i]->next = head;
          // head = curr[i];   <- and get rid of this
        }

    }

  for(i=0; i<17;i++)
    {
      printf("\n");
      while(curr[i])
        {
          printf("%s  ", curr[i]);
          curr[i] = curr[i]->next;
        }

    }

}

int hash_function_one (char *s, int T)
{
  int h = 0, a = 127, temp;

  for (; *s != 0; s++)
    {
      temp = (a * h + *s);
      if (temp < 0)
        temp = -temp;
      h = temp % T;
    }
  return h;
}

Frankly I wasn't much of a help, you figured it all out