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(s tr2, 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,progr amData); //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;
}
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(s
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);//
system("PAUSE");
//create the sorted array to be used for table 5 and print table 2
copyArray(sortedData,progr
sortProgramData(sortedData
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
}
system("PAUSE");
return 0;
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
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
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.
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
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
ASKER
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