Go Premium for a chance to win a PS4. Enter to Win

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 446
  • Last Modified:

Hash tales: having trouble incrementing through the array

This is a problem with hash funcitons, hash tables , function pointers and arrays.
First two arrays  done and now am onto the hash function portion.
I am able generate the initial hash value, now need to do table 3 which is as follows:

Table 3 is constructed within the function used to make the hashTable. Using the programData array send each word to the hash function for element 0-99. As the index value for each work is returned from the hash function store the word  and its index value in an appropriate data structure. Copy the word into the hashTable element based upon its index value using linear crash resolution where appropriate. Before applying the linear crash resolution, if required, increment a counterArray element by one to track the number of words which initially hashed to that index numer and finally get the next word.

I am confused about where to implement getting the subsequent vlues for the programData array and have been trying to the point of utter frustration...
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

#define MAXSIZE 139
#define DATA_FILE  "a:\\269data.txt"
#define SIZE 100

void getWords(char programData[][6])
{
    int idx=0;
    char word[7];
    FILE *fptr;
    fptr=fopen(DATA_FILE, "r"); //open file for reading
         if(fptr==NULL)
         {
          printf("file error-end program");
          exit(0);
         }
          while(fgets(word, 7,  fptr))
          {
             word[strlen(word)-1]= '\0';
             strcpy(programData[idx], word);
             idx++;
          }
         fclose(fptr);    //close file
}  //endfunc



void printTable(char array[][6])
{
     int idx=0;
     for(idx=0; idx<100; idx++)
       {
       printf("%-8s", array[idx]);
          if(idx+1 %10==0)
          printf("\n");
      }
}//endfunc


copyArray(char sortedData[][6], char programData[][6])     //copy programData into sortedData array for sorting
{

     int index, i, j,loc, x;
     char min[6];
     index=100;
     i=0;

     while(i<index)
     {
       strcpy(sortedData[i], programData[i]);
       i++;
      }
}//endfunc



int myCompare(const void *a1, const void *a2)
{
       int A;
       int result;
       A=strcmp((char *)a1,(char *)a2);

       if(A > 0)
           result=1;
        else if
          (A < 0)
            result=-1;
        else
            result=0;

        return result;
}


sortProgramData(char sortedData[][6])
{
    int x;
    qsort((void *)sortedData, SIZE, sizeof(char[6]), myCompare);

}


void initHashTable(char hashTable[MAXSIZE][6])
{

  int idx;

  for(idx=0; idx <MAXSIZE;idx++)
  {
    hashTable[idx][6]='\0';
    idx++;
   }

}



int hash1(char *str1)
{

   int sum=0;
   int key=0;
   int x=0;    //hash value count

      if(str1 == NULL) //if string has null value
          key = -1;     //result will be -1

      while(*str1)
       {
           sum += *str1;
           *str1++;
       }

      key=sum % MAXSIZE;
      return key;
}

int insertHashTable(char *hashTable, int key)
  {
     int keyCount=0;
     int idx=0;

       if(hashTable[idx]=='\0')
           hashTable[idx]=key;
       else
         {
            hashTable[idx++];
         }

     return keyCount;

}



/*int findHashEntry(char *hashTable, int key)
{

 }*/

void loadHashTable(char *str1, char *str2, int(*fp)(char *))
{

          int key;
          int keyCount;
          int i;

             key=hash1(str1);
             keyCount=insertHashTable(str2, key);
             printf("%d\n",key);

}


int main()
{
       int x;
       char programData[100][6]={'\0'};
       char sortedData[100][6]={'\0'};
       char hashTable[MAXSIZE][6];
       int(*fp)(char*)=(hash1);


        //read data file and print table 1
        getWords(programData);
        printf("\nTABLE 1 Initial Program Data as Read from 269data.txt\n");
        printTable(programData);//table1

        system("PAUSE");

       //create the sorted array to be used for table 5 and print table 2
        copyArray(sortedData,programData); //copy the array read from the file
        sortProgramData(sortedData);       //sort the array using "c" qsort)
        printTable(sortedData);            //print table 2

        system("PAUSE");

        //process the 4 hash functions
        for(x=0; x < 5; x++)
          {
           initHashTable(hashTable); //initialize hashTable to "empty state"
           loadHashTable(*programData, *hashTable, *fp);  //load the hash table and output Table 3

          }


           system("PAUSE");


return 0;

}



 
0
closet
Asked:
closet
  • 3
  • 2
1 Solution
 
Kent OlsenData Warehouse Architect / DBACommented:

Hi closet,

There are some pretty big pieces of your design missing.  Even so, I think that I can shed some light here.

The purpose of a hash table is to mathematically reduce sparce keys so that they are nearly consecutive.  When a key is reduced, it may be unique within the set of known keys or it might be a duplicate.  If it is a duplicate it might be the first duplicate or just 1 of any number of duplicates.

What I don't see in your solution is a way to resolve duplicates.  And because your design isn't shown, let me demonstrate two "general" way to solve this.


The first is with a linked list.  Each node contains a pointer to another node.  The hashtable contains the address of the first node in the chain with a given key.  The chain contains the rest of the nodes with the same key.

#define TableSize 100

typedef struct
{
  char NodeName[24];                   /*  This is the value to hash  */
  /*  User data  */
  node_t  *Next;
}  node_t;

node_t *HashTable[TableSize];

int GenerateHash (char *string)
{
  int KeyValue;                             /*  Compute a generic value based on the passed string  */
  return (KeyValue % TableSize);  /*  Reduce to a value that will fit into the table  */
}

int AddItem (node_t *Node)
{
  node_t *TmpNode;
  int       Index;

  Index = GenerateHash (Node->NodeName);
  if (HashTable[Index])                          /*  A node with this key is already saved  */
  {
    TmpNode = HashTable[Index];
    while (TmpNode->Next)                    /*  Find last node on this chain  */
      TmpNode = TmpNode->Next;
    TmpNode->Next = Node;                  /*  Add the new node to the end of the chain  */
  }
  else
    HashTable[Index] = Node;


The second solution requires a bit more effort and code.  The hash table points to a buffer that contains some number of nodes and some control information.  Instead of a linked list of nodes, you maintain a linked list of buffers.  The advantage here is that searaching and maintaining a linked list of buffers can more efficiently utilize system resources than a linked list of nodes.  The disadvantage is that maintaining a linked list of nodes is easier to code and maintain.

If this doesn't point you in the right direction, just give me a little more detail on what you need and I'll give you some more feedback.

Good Luck,
Kent

0
 
closetAuthor Commented:
Kent
This is the part of the problem that is confusing me,
Copy the word into the hashtable element based upon its index value using linear crash resolution.

I originally thought this would be your second solution, but now I am not sure. What do you think?
Thanks
Closet
0
 
Kent OlsenData Warehouse Architect / DBACommented:

Hi closet,

Here's the AddItem() function that I included earlier:

1>  int AddItem (node_t *Node)
2>  {
3>    node_t *TmpNode;
4>    int       Index;
5>  
6>    Index = GenerateHash (Node->NodeName);
7>  if (HashTable[Index])                          /*  A node with this key is already saved  */
8>    {
9>       TmpNode = HashTable[Index];
10>      while (TmpNode->Next)                    /*  Find last node on this chain  */
11>      TmpNode = TmpNode->Next;
12>      TmpNode->Next = Node;                  /*  Add the new node to the end of the chain  */
13>    }
14>    else
15>      HashTable[Index] = Node;

Lines 6 and 15 do what the instructions say:  Line 15:  "Copy the word into the hashtable element", Line 6:  "based upon its index value using linear crash resolution."

GenerateHash() performs the calculations that reduce the key field to an index into the Table.  Once the index is derived, it's either placed directly into the table, or append to the chain as an overflow item.  Note that the code inserts the item as the last item on the chain.  If the order isn't important, you can put it on the front of the chain by replacing lines 7-15 with these two lines:

Node->Next = HashTable[Index];
HashTable[Index] = Node;

In either case, you will have saved the node as an element that can be later retrieved by it's hash key.


Kent
0
 
closetAuthor Commented:
Okay, good.
I was working on that solution while waiting for your reply. I have one more question though.
My prof hated using typedefs for structs so I am not great at using them for structures. Usually I declare the struct node *whatever, then when I send the parameter to a function I send the address of the link (&head) list. I am not sure what to send the add item using the typedef structure. Can you tell me? Thanks Closet.
0
 
Kent OlsenData Warehouse Architect / DBACommented:
Sure.

You don't have to typedef the struct.  I do simply out of habit.

struct node_t;

struct
{
  char NodeName[24];                   /*  This is the value to hash  */
  /*  User data  */
  struct node_t  *Next;
}  node_t;

struct node_t *HashTable[TableSize];

int AddItem (struct node_t *Node);


That's the same thing, but the structs aren't typedef'd.

Kent
0

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now