c++ - 哈希表中的段错误

Question

我不明白为什么我的程序会出现段错误。谁能解释一下这个问题？

#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
class HashTable {
private:
    int *A[1];
    int n;
    int bsize;
    vector<int> B;

public:
    HashTable(int size) {
        n = size;
        bsize = 0;
        *A = new int[n];
    }
    /*
    You should use another array B besides A. You do not initialize A, and thus the cells of A contain
    garbage initially. The array B is a std::vector which is initially empty. Use the same hash function
    h(x) = x. If A[x] contains i and B[i] contains x, it means that x exists in the hash table. If A[x]
    contains i but B[i] does not contain x or i is out of the range of B, it means that x does not exist in
    the hash table.
    */
    bool insert_hash(int x) {
        if (x >= n) {//sees if x is within the range of A
        } else {
            if (*A[x] > bsize){//sees if i is within the range of B
            } else {
                if (B[*A[x]] == x) {//sees if B[i] contains x

                    return false;
                }
            }

        }
        B.push_back(x);//adds key x to B
        bsize++;
        *A[x] = bsize;//store location at A
        return true;

    //The new key x should be pushed at the back of B and its location is stored at A[x]. This function
    //should return false if x already exists in the hash table, and returns true otherwise.
    }

    bool member_hash(int x) {
    //The function returns true if x exists in the hash table, and returns false otherwise.
        if (x <= n) {//sees if x is within the range of A
            if (*A[x] > bsize){//sees if i is within the range of B
                if (B[*A[x]] == x) {//sees if B[i] is x
                    return true;
                }
            }
        }
        return false;
    }

    bool delete_hash(int x) {
    //This function First checks whether x exists in the hash table: If no, then it returns false. Otherwise,
    //it stores -1 at the cell of B that contains x and then returns true.
        if (!member_hash(x)) {
            return false;
        } else {
            B[*A[x]] = -1;
            return true;
        }
    }
};

int main() {
    HashTable a(20);
    a.insert_hash(5);
    a.insert_hash(4);
    a.insert_hash(2);
    a.insert_hash(2);
    a.insert_hash(11);
    a.insert_hash(510);
    a.member_hash(11);
    a.delete_hash(11);
    a.member_hash(11);
    return 0;
}

我在 DevC++ 和 Code::Blocks 中编译代码都很好，但是当我尝试运行这段代码时，它最终没有响应，当我在 CodePad 上运行它时，我收到消息 Segmentation Fault。编辑:更具体地说，它说“段错误(核心转储)”编辑 2:似乎段错误始于 main 中的第一个 insert_hash，条件语句 (B[*A[x]] == x) 关于如何解决此问题的任何想法？编辑 3:B[*A[x]] == x，从 member_hash 开始，似乎是因为 B 是空的。但是，我很困惑 *A[x] 中的垃圾值是如何达到这种情况的，因为我有其他条件 (*A[x] < bsize) 和 (x < n) 来防止这种情况。解决方案？

Answer 1

int *A[1]; 表示您将 A 声明为指向 int 的指针的一个元素的数组。

你的数组分配编译但不好，你正在一个未知地址分配一个 int 数组(因为此时 A[0] 未定义)

如果我正确地理解了您要实现的目标，那么您希望 A 是一个包含 n 个 int 类型元素的数组。

所以我相应地更新了你的代码:

#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
class HashTable {
private:
    int *A;
    int n;
    int bsize;
    vector<int> B;

public:
    HashTable(int size) {
        n = size;
        bsize = 0;
        A = new int[n];
    }
    /*
    You should use another array B besides A. You do not initialize A, and thus the cells of A contain
    garbage initially. The array B is a std::vector which is initially empty. Use the same hash function
    h(x) = x. If A[x] contains i and B[i] contains x, it means that x exists in the hash table. If A[x]
    contains i but B[i] does not contain x or i is out of the range of B, it means that x does not exist in
    the hash table.
    */
    bool insert_hash(int x) {
        if (x >= n) {//sees if x is within the range of A
        } else {
            if (A[x] > bsize){//sees if i is within the range of B
            } else {
                if (B[A[x]] == x) {//sees if B[i] contains x

                    return false;
                }
            }

        }
        B.push_back(x);//adds key x to B
        bsize++;
        A[x] = bsize;//store location at A
        return true;

    //The new key x should be pushed at the back of B and its location is stored at A[x]. This function
    //should return false if x already exists in the hash table, and returns true otherwise.
    }

    bool member_hash(int x) {
    //The function returns true if x exists in the hash table, and returns false otherwise.
        if (x <= n) {//sees if x is within the range of A
            if (A[x] > bsize){//sees if i is within the range of B
                if (B[A[x]] == x) {//sees if B[i] is x
                    return true;
                }
            }
        }
        return false;
    }

    bool delete_hash(int x) {
    //This function First checks whether x exists in the hash table: If no, then it returns false. Otherwise,
    //it stores -1 at the cell of B that contains x and then returns true.
        if (!member_hash(x)) {
            return false;
        } else {
            B[A[x]] = -1;
            return true;
        }
    }
};

int main() {
    HashTable a(20);
    a.insert_hash(5);
    a.insert_hash(4);
    a.insert_hash(2);
    a.insert_hash(2);
    a.insert_hash(11);
    a.insert_hash(510);
    a.member_hash(11);
    a.delete_hash(11);
    a.member_hash(11);
    return 0;
}