Array of Linked Lists - Hash table

This is a discussion on Array of Linked Lists - Hash table within the C Programming forums, part of the General Programming Boards category; Hello, I am trying to write a program that simulates a hash table using chaining to prevent collision. I'm still ...

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    18

    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];
            }
        }

  2. #2
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Seems like it's adding a node whether the index value is NULL or not, doesn't it?

    Edit: what happens if the string isn't a repetition; does it start a new array of linked lists?
    Last edited by itCbitC; 02-25-2009 at 09:22 PM.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Posts
    18
    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.
    Last edited by FortinsM3; 02-25-2009 at 09:25 PM.

  4. #4
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Quote Originally Posted by FortinsM3 View Post
    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;
    }

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Quote Originally Posted by FortinsM3 View Post
    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.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    18
    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];
    
            }
    
        }

  7. #7
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Can you post the part of the code where the array curr[] is defined and the hash func too.

  8. #8
    Registered User
    Join Date
    Oct 2008
    Posts
    18
    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;
    }

  9. #9
    Registered User
    Join Date
    Oct 2008
    Posts
    18
    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];
            }

  10. #10
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    how about the entire code as it's hard to piece it together

  11. #11
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    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];
            }

  12. #12
    Registered User
    Join Date
    Oct 2008
    Posts
    18
    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;
    }

  13. #13
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Frankly I wasn't much of a help, you figured it all out

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 02:02 PM
  2. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 05:16 PM
  3. Linked Lists Integer addition ? HELP Please??
    By green_eel in forum C Programming
    Replies: 3
    Last Post: 03-12-2003, 04:36 PM
  4. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 10:48 AM
  5. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 07:25 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21