Double linked list is overwriting string items
-
Hi, I made a program which hashes string items in a table. The table has 5 index positions. When the table is full with string items, the linked list is overwriting the existing string items. This is my code from Table: Table::Table(int listSize) { size = listSize; list = new List[size]; } // hash function int Table::hash(string item) { unsigned int hval, g; char *str = &item[0]; /* Compute the hash value for the given string. */ hval = 0; while (*str != '\0') { hval <<= 4; hval += (unsigned int) *str++; g = hval & ((unsigned int) 0xf << (HASHWORDBITS - 4)); if (g != 0) { hval ^= g >> (HASHWORDBITS - 8); hval ^= g; } } return hval%size; } Node* Table::find(string item) { int hashValue = hash(item); return list[hashValue].find(item); } Node* Table::insert(string item) { int hashValue = hash(item); return list[hashValue].insert(item); } bool Table::isMember(string item) { int hashValue = hash(item); return (list[hashValue].find(item) != NULL); } void Table::remove(string item) { int hashValue = hash(item); list[hashValue].remove(item); } void Table::print() { for(int index = 0; index < size; index++) { cout << "Index: " << index << ": "; list[index].print(); cout << endl; } } The double linked list class: List::List() { head = NULL; } List::~List() { Node* previousNode; Node* node = head; while(node != NULL) { previousNode = node; node = node->next; delete previousNode; } } Node* List::insert(string item) { head = new Node(head, item); return head; } void List::remove(string item) { Node* previousNode; Node* node = head; while(node != NULL) { if(head->value == item) { // Link previous node to next node if(previousNode != NULL) previousNode->next = node->next; else head = node->next; delete node; break; } previousNode = node; node = node->next; } } Node* List::find(string item) { Node* previousNode; Node* node = head; while(node != NULL) { if(head->value == item) return node; previousNode = node; node = node->next; } return NULL; } void List::print() { Node* node = head; if(node != NULL) { cout << node->value << " "; node = node->next; } cout << endl; } Node class: Node::Node(Node* n, string s) { next = n; valu
-
Hi, I made a program which hashes string items in a table. The table has 5 index positions. When the table is full with string items, the linked list is overwriting the existing string items. This is my code from Table: Table::Table(int listSize) { size = listSize; list = new List[size]; } // hash function int Table::hash(string item) { unsigned int hval, g; char *str = &item[0]; /* Compute the hash value for the given string. */ hval = 0; while (*str != '\0') { hval <<= 4; hval += (unsigned int) *str++; g = hval & ((unsigned int) 0xf << (HASHWORDBITS - 4)); if (g != 0) { hval ^= g >> (HASHWORDBITS - 8); hval ^= g; } } return hval%size; } Node* Table::find(string item) { int hashValue = hash(item); return list[hashValue].find(item); } Node* Table::insert(string item) { int hashValue = hash(item); return list[hashValue].insert(item); } bool Table::isMember(string item) { int hashValue = hash(item); return (list[hashValue].find(item) != NULL); } void Table::remove(string item) { int hashValue = hash(item); list[hashValue].remove(item); } void Table::print() { for(int index = 0; index < size; index++) { cout << "Index: " << index << ": "; list[index].print(); cout << endl; } } The double linked list class: List::List() { head = NULL; } List::~List() { Node* previousNode; Node* node = head; while(node != NULL) { previousNode = node; node = node->next; delete previousNode; } } Node* List::insert(string item) { head = new Node(head, item); return head; } void List::remove(string item) { Node* previousNode; Node* node = head; while(node != NULL) { if(head->value == item) { // Link previous node to next node if(previousNode != NULL) previousNode->next = node->next; else head = node->next; delete node; break; } previousNode = node; node = node->next; } } Node* List::find(string item) { Node* previousNode; Node* node = head; while(node != NULL) { if(head->value == item) return node; previousNode = node; node = node->next; } return NULL; } void List::print() { Node* node = head; if(node != NULL) { cout << node->value << " "; node = node->next; } cout << endl; } Node class: Node::Node(Node* n, string s) { next = n; valu
-
Have you tried to debug it? Perhaps single stepping through the insert function when it overwrites?
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."