c++ - 链表 C++ 段错误

Question

我正在尝试从头开始制作一个简单的链表，供另一个类使用。错误好像是有时候Head没有设置为NULL。我说有时之前它不会一直出现错误。当它没有出现错误时，它会转到 else 语句。注意我只添加 1 个字符串。也许你们可以发现我没有看到的东西，干杯!

链表.h:

#include <string>
#include "Link.h"

using namespace std;

class LinkedList {
  Link *head;

public:
  LinkedList();
  void addFront(string key);
  void printList();
  //void addBack(string *);     

};

链表.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);

// }

链接.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();

};

链接.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;
}

哈希.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);


};

哈希.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;

// }

主要.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;
}

Answer 1

您的直接问题:哈希表中的链表数组是一个指针数组。声明为:

LinkedList *hashFN[100];

您似乎从未分配这些对象中的任何一个。所以你只有一个指针数组，其中包含 100 个指向垃圾的不确定指针。分配它们，或者更好的是，直接实例化它们:

LinkedList hashFn[100];

这将需要您更改对它们的引用，例如

hashFN[location]->addFront(k);

变成这样:

hashFN[location].addFront(k);

接下来，您将使用非常量成员变量 prime作为哈希函数的模数。因为这被硬编码为 101 ，您的 table 需要大小相同。 (事实上​​ ，我会完全失去成员变量，而只是你的 Hash.cpp 文件中的静态常量)。但除此之外，问题仍然存在。你的 table 太小一格了。您的模数可以来自 0..100 ，这意味着您需要一个表 [101]大小可以解决所有这些插槽。请记住，C/C++ 中的数组是 [0...(n-1)]针对大小为 n 的数组寻址

所以至少要这样声明你的表:

LinkedList hashFN[101];

我要发布的最后一件事。您的链接列表像泰坦尼克号一样泄漏。当列表被销毁时，您需要清理所有这些节点。在你的类中声明一个析构函数:

virtual ~LinkedList();

并在您的 .cpp 文件中像这样实现它:

LinkedList::LinkedList()
{
    while (head)
    {
        Link *victim = head;
        head = head->getNext();
        delete victim;
    }
}

好的。我撒了谎。还有一件事，直到您能够舒适地阅读和理解Rule of Three ，你应该让你的类不可复制。将以下内容放入 LinkedList 类声明的私有(private)部分:

class LinkedList
{
   ... other code...

private:
    LinkedList(const LinkedList&);
    LinkedList& operator =(const LinkedList&);
};

这将隐藏可能导致您主要问题的事情，直到您准备好正确实现它们。如果您发现自己遇到“无法访问私有(private)成员的错误”LinkedList(const LinkedList&) "然后你试图复制，如果没有适当保护你的头部指针，那是不行的。阅读三规则。

剩下的交给你了。

注意:有很多方法可以使用标准库( std::vector<> 、 std::unordered_map<> 等)更轻松地完成很多工作。事实上，std::unordered_map<>是所有这些的直接替代品。但是，如果您只是对使用该语言感兴趣以再次熟悉它，那么暂时使用裸机也不错。只需专注于重新学习，然后学习使用标准库必须提供的所有漂亮代码。