Link to home
Start Free TrialLog in
Avatar of closet
closet

asked on

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;

}



 
ASKER CERTIFIED SOLUTION
Avatar of Kent Olsen
Kent Olsen
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of closet
closet

ASKER

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

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
Avatar of closet

ASKER

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.
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