C++分离链哈希实现出现无限循环问题求助

核心问题分析 #

1. 局部变量引发的野指针（insertSepChain函数） #

在插入逻辑的else分支中，你创建了栈上的局部变量ListNode temp(value)，随后将arr[index].next指向该变量的地址。函数执行结束后，局部变量会被销毁，对应的内存会被系统回收或覆盖，此时arr[index].next就变成了野指针——指向一块无效内存。这直接导致读取时出现垃圾值，后续遍历链表时，野指针的next成员可能是随机值而非nullptr，进而触发无限循环。

2. 链表遍历的逻辑漏洞（display函数） #

原遍历代码：

while (temp.next != nullptr) {
    cout << temp.value << ", ";
    temp = *temp.next;
}

这个循环只会输出到倒数第二个节点，因为当temp指向最后一个节点时，temp.next为nullptr，循环直接终止，最后一个节点的value永远不会被输出。同时，如果遇到野指针，temp.next不会是nullptr，就会持续循环导致无限遍历。

3. 冗余的初始化操作 #

HashTest构造函数中手动循环给arr[i]赋值ListNode(0)，但ListNode的默认构造函数已经会将value设为0、next设为nullptr，这步操作完全多余。

修复后的完整代码 #

#include <iostream>

class ListNode {
public:
    int value;
    ListNode* next;
    ListNode(int newValue) : value(newValue), next(nullptr) {}
    ListNode() : value(0), next(nullptr) {}
};

class HashTest {
private:
    int size;
    ListNode arr[17];
public:
    HashTest(int size) : size(size) {} // 移除冗余初始化

    void insertSepChain(int value) {
        int index = hash(value);

        if (arr[index].value == 0) {
            arr[index].value = value;
        } else {
            // 动态分配节点，避免局部变量销毁问题
            ListNode* newNode = new ListNode(value);
            // 遍历到链表尾部追加新节点（原代码直接覆盖next会丢失之前的链）
            ListNode* current = &arr[index];
            while (current->next != nullptr) {
                current = current->next;
            }
            current->next = newNode;
        }
    }

    int hash(int value) {
        return value % size;
    }

    void display() {
        using namespace std;
        for (int i = 0; i < size; i++) {
            if (arr[i].value == 0) {
                cout << "0\n";
            } else {
                cout << "chain: ";
                ListNode* current = &arr[i];
                // 遍历所有节点，包括首节点
                while (current != nullptr) {
                    cout << current->value;
                    if (current->next != nullptr) {
                        cout << ", ";
                    }
                    current = current->next;
                }
                cout << "\n";
            }
        }
    }

    // 析构函数释放动态分配的节点，避免内存泄漏
    ~HashTest() {
        for (int i = 0; i < size; i++) {
            ListNode* current = arr[i].next;
            while (current != nullptr) {
                ListNode* temp = current;
                current = current->next;
                delete temp;
            }
        }
    }
};

int main() {
    HashTest testing(17);

    testing.insertSepChain(9);
    testing.insertSepChain(34);
    testing.insertSepChain(49);
    testing.insertSepChain(16);
    testing.insertSepChain(32);
    testing.insertSepChain(51);

    testing.display();

    return 0;
}

额外说明 #

• 修复插入逻辑：现在会遍历到链表尾部再追加新节点，避免原代码直接覆盖next导致的链丢失问题
• 添加析构函数：动态分配的节点必须手动释放，否则会造成内存泄漏
• 简化遍历逻辑：直接用指针遍历，避免拷贝节点，同时确保所有节点都被输出

内容的提问来源于stack exchange，提问作者www139