C ++ linked list Seg fault
I am trying to make a simple linked list from scratch that is used by another class. It looks like the error is that sometimes the head is not set to NULL. I say sometimes before he is not guilty all the time. The time during which it does not occur does not apply to the else clause. Note. I only add 1 line. Maybe you guys can spot something I can't see, hurray!
LinkedList.h:
#include <string>
#include "Link.h"
using namespace std;
class LinkedList {
Link *head;
public:
LinkedList();
void addFront(string key);
void printList();
//void addBack(string *);
};
LinkedList.cpp:
#include <cstring>
#include <string>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include "LinkedList.h"
using namespace std;
LinkedList::LinkedList() {
head = NULL;
}
void LinkedList::addFront(string key) {
//creates the new list segment
Link *l = new Link(key);
cout << "Made new Link " << key << endl;
// if the list is empty
if (head == NULL){
cout << "Going to set Head " << key << endl;
head = l;
cout << "Set Head to new link " << key << endl;
}
else {
cout << "Else statement " << key << endl;
l->setNext(head);
head = l;
}
}
void LinkedList::printList() {
//Check if list is empty
if(head == NULL)
cout << "NULL" << endl;
else {
Link *l = head;
for(;l != NULL; l=l->getNext())
cout << l->getValue() << endl;
}
}
// void LinkedList::addBack(string *f) {
// Link *l = new Link(f);
// }
Link.h
#include <cstdlib>
#include <cstring>
#include <string>
using namespace std;
class Link {
string key;
Link *next;
public:
Link(string key);
void setValue(char);
void setNext(Link *next);
string getValue();
Link *getNext();
void printList();
};
Link.cpp
#include <cstdlib>
#include <string>
#include <iostream>
#include "Link.h"
using namespace std;
Link::Link(string key) {
this->key = key;
next = NULL;
}
void Link::setNext(Link *l) {
cout << "setting new link "<<endl;
next = l;
cout<< "New link was set" << endl;
}
string Link::getValue() {
return key;
}
Link *Link::getNext() {
return next;
}
Hash.h
#include <iostream>
#include <cstring>
#include <string>
#include "LinkedList.h"
using namespace std;
class Hash{
//100 slot array for hash function
LinkedList *hashFN[100];
//preset prime number
int prime = 101;
int key;
unsigned int location;
public:
//Note: Both the key & values are the same
void insert(string key, string value);
// void deleteItem(int key);
// char* find(int key);
};
Hash.cpp:
#include <iostream>
#include <cstring>
#include <string>
#include "Hash.h"
using namespace std;
void Hash::insert(string k, string v){
//Get Hash for argv[2] aka value
size_t key = std::hash<string>()(k);
unsigned int location;
//check 1
cout << "Hash: " << key << endl;
//Find location
location = key % prime;
//check 2
cout << "Mod 101 Hash: " << location << endl;
hashFN[location]->addFront(k);
cout << "Success!" << endl;
}
// void Hash::deleteItem(int key){
// return;
// }
// char* Hash::find(int key){
// return;
// }
main.cpp
#include <iostream>
#include <functional>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include "Hash.h"
using namespace std;
int main(int argc, char *argv[]) {
Hash HashTable;
string Insert = string("insert");
string Delete = string("delete");
string Find = string("find");
string Argv(argv[2]); //Makes the argv[2] into string type
// check for Request & string parameters
if(argc != 3) {
cout << "Run program with 2 parameters. [Lower Case]" << endl;
cout << "[1] insert, find, or delete" << endl;
cout << "[2] string" << endl;
exit(1);
}
//Check for "insert"
if(strcmp(argv[1], "insert") == 0) {
HashTable.insert(Argv, Argv);
}
return 0;
}
source to share
Your immediate problem: your array of linked lists in your hashtable is an array of pointers. Declared as:
LinkedList *hashFN[100];
You never seem to highlight any of these objects. so you only have a pointer array of 100 undefined garbage pointers. Either highlight them, or better yet, just specify them directly:
LinkedList hashFn[100];
This will require changing the links to them, for example
hashFN[location]->addFront(k);
Becomes as follows:
hashFN[location].addFront(k);
Then you use a non-const member variable prime
as the hash function module. Since this is hardcoded before 101
, your table should be the same size. (and in fact, I would completely lose the member variable and only the static constant in your Hash.cpp file as much as possible). But besides, this question still remains. Your table has too little slot. Your modulo can be from 0..100
, which means you need a table [101]
to address all of those slots. Remember that arrays in C / C ++ are addressed [0...(n-1)]
for an array of sizen
So at least declare your table like this:
LinkedList hashFN[101];
The last thing I post. Your linked list is leaking out like Titanic. You need to clear all these nodes when the list is destroyed. Declare a destructor in your class:
virtual ~LinkedList();
And implement it like this in your .cpp file:
LinkedList::LinkedList()
{
while (head)
{
Link *victim = head;
head = head->getNext();
delete victim;
}
}
OK. I was lying. One more thing. Until you are comfortable reading and understanding the Rule of Three , you should make your class uncopyable. Place the following in the private section of your LinkedList class declarations:
class LinkedList
{
... other code...
private:
LinkedList(const LinkedList&);
LinkedList& operator =(const LinkedList&);
};
This will hide what can cause serious problems until you are ready to implement them correctly. If you find that you have an "error of something in action" cannot access the private member LinkedList(const LinkedList&)
, then you are trying to make a copy and without proper pointer protection on the head, not not ... read the rule of three .
I leave the rest to you.
Note. There are ways to make this easier with the standard library ( std::vector<>
, std::unordered_map<>
etc.). std::unordered_map<>
Is actually a replacement for all of these . But if you're just interested in getting to grips with the language to get to know it again, it might be a good idea to get a little closer to bare music. Just focus on retraining, then learn how to use all this beautiful code that the standard library has to offer.
source to share