哈希表中存在分段错误

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：Segmentation错误似乎始于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;
}