我目前正在创建一个哈希表，该表使用单独的链接作为冲突解决方案。我实现了指向结构中下一个节点的下一个指针，类似于链表的结构。
每当我试图访问下一个节点的单词时，我都会收到一个内存错误，说Segmentation Fault(核心转储(。
cout<<hashTable[5].next->word; //this line produces the memory error
造成这种情况的原因是什么？我该如何解决？
#include <iostream>
using namespace std;
struct Node{
string word;
Node* next;
bool empty;
};
void hashInsert(Node table[], string word){
int index = 5; //should add hashFunction() if not testing
Node* current = &table[index];
if(table[index].empty){
table[index].word = word;
table[index].empty = false;
}
else{
while(current->next != nullptr){
current = current->next;
}
current = new Node();
current->word = word;
current->next = nullptr;
current->empty = false;
}
}
int main()
{
Node hashTable[10];
hashInsert(hashTable, "test");
hashInsert(hashTable, "test");
cout<<hashTable[5].next->word;
}
Node hashTable[10];
使其内容未初始化。这使得hashInsert中的一些东西比你想在计算机程序中看到的更像是一种冒险。使用
Node hashTable[10] = {};
to Zero初始化数组并获得更多可预测性。
但这并不能解决所有的问题。零初始化会将empty设置为false，但事实并非如此。您需要一个默认构造函数(或成员上的默认成员初始值设定项(来强制值为true或反转逻辑。
当您仔细观察这两种方法时，您会意识到只需要empty标志，因为列表中的第一个节点可能没有使用。但是，如果没有第一个节点，如果不需要第一个节点呢？empty的作业可以使用空指针进行处理。
Node * hashTable[10] = {}; // treat each entry in the hash table like a next
// without the rest of the node
这样可以将hashInsert缩小为
void hashInsert(Node * table[], string word) {
int index = 5; //should add hashFunction() if not testing
Node *current = table[index]; //
if (table[index] == nullptr)
{
table[index] = new Node{word, nullptr};
}
else
{
while (current->next != nullptr)
{
current = current->next;
}
current = new Node{word, nullptr};
}
}
注意：Node{word, nullptr};使用聚合初始化来创建Node，并在一个快照中设置其所有成员。非常方便。
但这不起作用，因为current是一个局部作用域的自动变量，所以一旦函数返回，分配给它的新Node就会丢失。我们需要更聪明的东西。
Ranoiaetep提出CCD_ 11。这会奏效，但我们可以变得更聪明。
void hashInsert(Node * table[], string word) {
int index = 5; //should add hashFunction() if not testing
Node **current = &table[index]; // point at the next pointer! Now we know
// the correct place to insert in ALL cases
if (*current == nullptr)
{
*current = new Node{word, nullptr};
}
else
{
while (*current != nullptr)
{
current = &(*current)->next;
}
*current = new Node{word, nullptr};
}
}
在这个版本中，您可能会注意到if (*current == nullptr)和while (*current != nullptr)并没有什么不同。在if中，当没有节点时，我们添加一个新节点。在while中，我们不查找节点，然后添加一个新节点。无论哪种方式，无节点都意味着添加一个节点。我们也许可以把它们结合起来。
void hashInsert(Node * table[], string word) {
int index = 5; //should add hashFunction() if not testing
Node **current = &table[index];
while (*current != nullptr) // look for end of list
{
current = &(*current)->next;
}
*current = new Node{word, nullptr}; // add to end of list
}
呜呜。4行代码和几个大括号。
整个事情看起来像
#include <iostream>
using namespace std;
struct Node {
string word;
Node *next;
};
void hashInsert(Node * table[], string word) {
int index = 5; //should add hashFunction() if not testing
Node **current = &table[index];
while (*current != nullptr)
{
current = &(*current)->next;
}
*current = new Node{word, nullptr};
}
int main() {
Node * hashTable[10] = {};
hashInsert(hashTable, "test");
hashInsert(hashTable, "test");
cout << hashTable[5]->next->word;
}
两件事：
bool empty默认为false，我假设您的意思正好相反- 打电话后：
while(current->next != nullptr){
current = current->next;
}
您的current实际上是最后一个非nullptr。因此，您随后拨打的任何电话都是对您插入的第一个Node进行的。
在while循环之后，您需要添加：
current->next = new Node();
current = current->next;
编辑：
在不改变其他结构的情况下，以下是代码：
#include <iostream>
using namespace std;
struct Node{
string word;
Node* next;
bool empty = true; // empty is now defaulted to true
};
void hashInsert(Node table[], string word){
int index = 5;
Node* current = &table[index];
if(table[index].empty){
table[index].word = word;
table[index].empty = false;
}
else{
while(current->next != nullptr){
current = current->next;
}
current->next = new Node(); // A new Node is added after current
current = current->next; // Now current is set to the next Node
current->word = word;
// current->next = nullptr; // This is not needed
current->empty = false;
}
}
int main()
{
Node hashTable[10];
hashInsert(hashTable, "test");
hashInsert(hashTable, "test");
cout << hashTable[5].word << ", ";
cout << hashTable[5].next->word;
}