Reputation: 111
issues with trying to add an item to a linked list
I'm working with a chained hash table and trying to append an entry in case one already exists with the same hash key. But I'm running into issues.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TABLE_SIZE 8
typedef struct stItem item;
struct stItem {
int key;
item *next;
};
void init(item * H[]) {
int i = 0;
for (i; i < TABLE_SIZE; i++)
H[i] = NULL;
}
int h(int k) {
// this does not work at all (but from exercise description), replaced with temp code
/*
int m = TABLE_SIZE;
int A = ( sqrt(5.0) - 1) / 2;
return m * (k * A % 1);
*/
return k % TABLE_SIZE;
}
void insert(int key, item * H[]) {
int keyHashed = h(key);
if (H[keyHashed] == NULL) {
printf("hashkey: %d (%d)\n", keyHashed,key);
item * temp = malloc(sizeof(item));
temp->key = key;
temp->next = NULL;
H[keyHashed] = temp;
}
else {
printf("hashkey: %d (%d) (duplicate)\n", keyHashed,key);
item * temp = malloc(sizeof(item));
temp->key = NULL;
temp->next = H[keyHashed]->next;
while (temp->next != NULL)
temp = temp->next;
temp->next = malloc(sizeof(item));
temp->next->key = key;
temp->next->next = NULL;
}
}
int search(int key, item * H[]) {
int keyHashed = h(key);
if (H[keyHashed] == NULL)
return -1;
else if (H[keyHashed]->key != key) {
item * temp = malloc(sizeof(item));
temp->key = NULL;
temp->next = H[keyHashed]->next;
while (temp->key != key && temp != NULL)
temp = temp->next;
if (temp->key == key) {
return keyHashed;
}
else
return -1;
}
else
return keyHashed;
}
void printHash(item * H[]) {
printf("\nTable size: %d\n", TABLE_SIZE);
int i = 0;
for (i; i < TABLE_SIZE; i++) {
if (H[i] != NULL) {
printf("i: %d key: %d",i,H[i]->key);
if (H[i]->next != NULL) {
printf("chaining print\n");
item * temp = malloc(sizeof(item));
temp->key = NULL;
temp->next = H[i]->next;
while (temp->key != NULL) {
printf(" -> %d", temp->key);
}
printf("\n");
}
else
printf("\n");
}
else
printf("i: %d key: none\n",i);
}
}
void test() {
// a)
int array[7] = {111,10112,1113,5568,63,1342,21231};
item *h[TABLE_SIZE];
init(h);
int i = 0;
for (i; i < 7; i++)
insert(array[i], h);
// b)
printHash(h);
// c)
printf("Search result for 1: %d", search(1, h));
printf("Search result for 10112: %d", search(10112, h));
printf("Search result for 1113: %d", search(1113, h));
printf("Search result for 5568: %d", search(5568, h));
printf("Search result for 337: %d", search(337, h));
}
int main() {
test();
}
Output:
hashkey: 7 (111)
hashkey: 0 (10112)
hashkey: 1 (1113)
hashkey: 0 (5568) (duplicate)
hashkey: 7 (63) (duplicate)
hashkey: 6 (1342)
hashkey: 7 (21231) (duplicate)
Table size: 8
i: 0 key: 10112
i: 1 key: 1113
i: 2 key: none
i: 3 key: none
i: 4 key: none
i: 5 key: none
i: 6 key: 1342
i: 7 key: 111
Process returned -1073741819 (0xC0000005) execution time : 0.385 s
Press any key to continue.
The search-output also isn't appearing. I think that is caused by the code breaking before it even reaches that part, probably when it tries to print the linked lists.
Thanks to Alan Au's help I have found and fixed the problems in the code (well, apart from the hash algorithm that I still need to figure out).
Here is the working code and output:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define TABLE_SIZE 8
typedef struct stItem item;
struct stItem {
int key;
item *next;
};
void init(item * H[]) {
int i = 0;
for (i; i < TABLE_SIZE; i++)
H[i] = NULL;
}
int h(int k) {
// this does not work at all (but from exercise description), replaced with temp code
/*
int m = TABLE_SIZE;
int A = ( sqrt(5.0) - 1) / 2;
return m * (k * A % 1);
*/
return k % TABLE_SIZE;
}
void insert(int key, item * H[]) {
int keyHashed = h(key);
if (H[keyHashed] == NULL) {
printf("hashkey: %d (%d)\n", keyHashed,key);
item * temp = malloc(sizeof(item));
temp->key = key;
temp->next = NULL;
H[keyHashed] = temp;
}
else {
printf("hashkey: %d (%d) (duplicate)\n", keyHashed,key);
item * temp = H[keyHashed];
while (temp->next != NULL)
temp = temp->next;
temp->next = malloc(sizeof(item));
temp->next->key = key;
temp->next->next = NULL;
}
}
int search(int key, item * H[]) {
int keyHashed = h(key);
if (H[keyHashed] == NULL)
return -1;
else if (H[keyHashed]->key != key) {
item * temp = H[keyHashed];
while (temp->key != key && temp->next != NULL)
temp = temp->next;
if (temp->key == key) {
return keyHashed;
}
else
return -1;
}
else
return keyHashed;
}
void printHash(item * H[]) {
item *temp;
int i;
printf("\nTable size: %d\n", TABLE_SIZE);
for (i = 0; i < TABLE_SIZE; i++) {
if (H[i] != NULL) {
printf("i: %d key: %d",i,H[i]->key);
temp = H[i]->next;;
while (temp != NULL) {
printf(" -> %d", temp->key);
temp = temp->next;
}
printf("\n");
}
else
printf("i: %d key: none\n",i);
}
printf("\n");
}
void test() {
// a)
int array[7] = {111,10112,1113,5568,63,1342,21231};
item *h[TABLE_SIZE];
init(h);
int i = 0;
for (i; i < 7; i++)
insert(array[i], h);
// b)
printHash(h);
// c)
printf("Search result for 1: %d\n", search(1, h));
printf("Search result for 10112: %d\n", search(10112, h));
printf("Search result for 1113: %d\n", search(1113, h));
printf("Search result for 5568: %d\n", search(5568, h));
printf("Search result for 337: %d\n", search(337, h));
}
int main() {
test();
}
.
hashkey: 7 (111)
hashkey: 0 (10112)
hashkey: 1 (1113)
hashkey: 0 (5568) (duplicate)
hashkey: 7 (63) (duplicate)
hashkey: 6 (1342)
hashkey: 7 (21231) (duplicate)
Table size: 8
i: 0 key: 10112 -> 5568
i: 1 key: 1113
i: 2 key: none
i: 3 key: none
i: 4 key: none
i: 5 key: none
i: 6 key: 1342
i: 7 key: 111 -> 63 -> 21231
Search result for 1: -1
Search result for 10112: 0
Search result for 1113: 1
Search result for 5568: 0
Search result for 337: -1
Process returned 26 (0x1A) execution time : 0.303 s
Press any key to continue.
Upvotes: 0
Views: 35
Answers (1)
Reputation: 14046
There are multiple problems in your code. It is hard to fix them all at the same time. Basically you aren't implementing linked lists properly. Here are some major problems.
In the collision case of insert you are creating two new nodes, chaining a dummy one before the head and another one at the end. I don't know how to describe it better than that but it's just completely wrong. It should be much simpler and something like the below. It just creates a new node and puts it at the front of the collision chain (left as an exercise for you if you want to put it at the end - not necessary for hash table).
item * temp = malloc(sizeof(item));
temp->key = key;
temp->next = H[keyHashed];
H[keyHashed] = temp;
Why are you mallocing memory in the printHash function? That's clearly wrong. Should never need new memory for traversing a linked list. And you should be using next not key to determine whether you have reached the end of the linked list. In fact, you never update next within the while loop so you aren't traversing the list at all. Here's an example of what it is supposed to look like.
void printHash(item * H[])
{
item *temp;
int i;
printf("\nTable size: %d\n", TABLE_SIZE);
for (i = 0; i < TABLE_SIZE; i++) {
if (H[i] != NULL) {
printf("i: %d key: %d\n",i,H[i]->key);
temp = H[i]->next;;
while (temp != NULL) {
printf(" -> %d\n", temp->key);
temp = temp->next;
}
} else {
printf("i: %d key: none\n",i);
}
}
}
There are other problems (notably in search which will crash your program). But I think that is enough for you to chew on for now.
My recommendation: Go back and revise the basic implementation of linked lists. Get that fully understood and working before you come back to use it in a hashed table.
Upvotes: 2
Related Questions
- Can't add new node to linked list
- Not able to add to the head of a Linked List
- Linked list infinite loop issue
- Trying to add a node into a linked list
- Hash Table with linked list
- unable to insert element into linked list
- C - Errors when trying to make a hashtable
- Failed to add a node to linked list
- Adding item to a linked list
- Can't add item to the end of Linked list