我正在尝试实现van emde boas树，但是当我调用插入函数两次以上时，我得到了一个Segmentation Fault 11。当我尝试在insert函数中打印值时，我意识到问题是当我将簇初始化为NULL时。我不明白为什么在使用for循环时会出现这种情况。我也尝试使用calloc，但它给了我同样的错误。我的代码看起来像这样：
class vEB
{
int u;
int *m;
int *M;
vEB *summary;
vEB **cluster;
public:
vEB(int);
bool member(int);
void insert(int);
void Delete(int);
int min();
int max();
int* pred(int);
int* succ(int);
};
vEB::vEB(int u){
this -> u = u;
this -> m = NULL;
this -> M = NULL;
if (u == 2){
this -> summary = NULL;
this -> cluster = NULL;
} else {
int subSize = (int)sqrt(u);
this -> summary = new vEB(subSize);
this -> cluster = new vEB*[subSize];
for (int i=0;i<=subSize;i++){
cluster[i]=NULL;
}
}
}
bool vEB::member(int x){
if (u == 2){
if (m == NULL){
return false;
}
if (x == 0){
return ((*m) == 0);
} else if (x == 1){
return ((*M) == 1);
}
return false;
}else{
if (m == NULL) {
return false;
}
if (x < (*m) || x > (*M)){
return false;
}else if (x == (*m) || (x == (*M))){
return true;
}else{
int subSize = (int)sqrt(u);
int hi = x / subSize;
int lo = x % subSize;
if (cluster[hi] == NULL){
return false;
} else{
return cluster[hi] -> member(lo);
}
}
}
}
void vEB::insert(int x) {
if (u == 2) {
if (x == 0) {
if (m == NULL){
m = new int;
M = new int;
(*m) = (*M) = x;
} else {
(*m) = x;
}
} else if (x == 1) {
if (M == NULL){
m = new int;
M = new int;
(*m) = (*M) = x;
} else{
(*M) = x;
}
}
} else {
if (m == NULL) {
m = new int;
M = new int;
(*m) = (*M) = x;
} else {
if (x < (*m)) {
int currMin = (*m);
(*m) = x;
this -> insert(currMin);
}else {
int subSize = (int)sqrt(u);
int hi = x / subSize;
printf("%d - %d\n",x, hi);
int lo = x % subSize;
printf("%d - %d\n",x, hi);
if (cluster[hi] == NULL){
cluster[hi] = new vEB(subSize);
cluster[hi] -> insert(lo);
summary -> insert(hi);
}else {
cluster[hi] -> insert(lo);
}
if (x > (*M)){
(*M) = x;
}
}
}
}
}
void vEB::Delete(int x){
if (u == 2) {
if (x == 0) {
if ((*M) == 0){
m = M = NULL;
} else{
(*m) = 1;
}
} else if (x == 1) {
if ((*m) == 1) {
m = M = NULL;
}
else {
(*M) = 0;
}
}
}else{
int subSize = (int)sqrt(u);
int hi = x / subSize;
int lo = x % subSize;
if (x == (*m)){
if (x == (*M)){
m = M = NULL;
} else {
int nextMinHi = summary -> min();
int nextMinLo = cluster[summary -> min()] -> min();
int nextMin = nextMinHi * subSize + nextMinLo;
this -> Delete(nextMin);
(*m) = nextMin;
}
} else {
cluster[hi] -> Delete(lo);
if (cluster[hi] -> m == NULL){
summary -> Delete(hi);
delete cluster[hi];
cluster[hi] = NULL;
}
if (x == (*M)){
if (summary -> m == NULL) {
(*M) = (*m);
} else{
int nextMaxHi = summary -> max();
int nextMaxLo = cluster[summary -> max()] -> max();
(*M) = nextMaxHi * subSize + nextMaxLo;
}
}
}
}
}
int vEB::min() {
return (*m);
}
int vEB::max() {
return (*M);
}
int* vEB::pred(int x){
if (u == 2){
if (x == 0) {
return NULL;
} else if (x == 1){
if (m == NULL){
return NULL;
}
if ((*m) == 1){
return NULL;
}
return m;
}
else {
return NULL;
}
} else {
if (m == NULL) {
return NULL;
}
if (x <= (*m)) {
return NULL;
}
if (x > (*M)) {
return M;
}
int subSize = (int)sqrt(u);
int hi = x / subSize;
int lo = x % subSize;
if (cluster[hi] == NULL){
int* prev = summary -> pred(hi);
int* ret = new int;
(*ret) = (*prev) * subSize + cluster[(*prev)] -> max();
return ret;
} else {
int *newLo, *newHi;
newHi = new int;
newLo = new int;
(*newHi) = hi;
int minInCluster = cluster[hi] -> min();
if (lo > minInCluster){
newLo = cluster[hi] -> pred(lo);
}else {
newHi = summary -> pred(hi);
(*newLo) = cluster[(*newHi)] -> max();
}
int *ret = new int;
(*ret) = (*newHi) * subSize + (*newLo);
return ret;
}
}
}
int* vEB::succ(int x) {
if (u == 2) {
if (x == 1) {
return NULL;
}else if (x == 0) {
if (M == NULL) {
return NULL;
}
if ((*M) == 0) {
return NULL;
}
return M;
}else {
return NULL;
}
}else{
if (m == NULL) {
return NULL;
}
if (x >= (*M)) {
return NULL;
}
if (x < (*m)) {
return m;
}
int subSize = (int)sqrt(u);
int hi = x / subSize;
int lo = x % subSize;
if (cluster[hi] == NULL) {
int* next = summary -> succ(hi);
int* ret = new int;
(*ret) = (*next) * subSize + cluster[(*next)] -> min();
return ret;
} else {
int *newLo, *newHi;
newHi = new int;
newLo = new int;
(*newHi) = hi;
int maxInCluster = cluster[hi] -> max();
if (lo < maxInCluster){
newLo = cluster[hi] -> succ(lo);
}else {
newHi = summary -> succ(hi);
(*newLo) = cluster[(*newHi)] -> min();
}
int *ret = new int;
(*ret) = (*newHi) * subSize + (*newLo);
return ret;
}
}
}
int main(){
vEB *vEB = new class vEB(8);
vEB -> insert(1);
vEB -> insert(2);
vEB -> insert(5);
vEB -> insert(6);
vEB -> insert(7);
printf("%d\n", (*vEB -> pred(2)));
printf("%d\n", (*vEB -> succ(2)));
vEB -> Delete(2);
return 0;
}
有没有一种正确的方法来初始化指向我不知道的指针？任何建议将不胜感激。谢谢。
虽然off-by-one错误很糟糕，但是你有一个更糟糕的错误：可能的无限递归。
在你的VEC构造函数中，你检查了u == 2，但如果u是例如，会发生什么3？然后你会进入else案例，你得到3的平方根，它将被截断为整数1。然后你做new VEC(1)，它用值1（不等于2）调用构造函数，进入else分支并得到1的平方根，它等于1。然后你做new VEC(1)（再次！）等等，永远。
您需要检查是否u <= 2以避免这种情况。
在vEB::vEB(int u)
for (int i=0;i<=subSize;i++){ cluster[i]=NULL; }
一定是
for (int i=0;i<subSize;i++){ cluster[i]=NULL; }
因为this -> cluster = new vEB*[subSize];而不是this -> cluster = new vEB*[subSize+1];
当我调用插入函数两次以上时，我收到了分段错误11。
当你做vEB -> insert(5);时，hi的值太高而且cluster[hi]不在簇中。
这不是您的问题的解决方案，但我希望它有所帮助。通过一些调试，我发现你的问题就是你调用insert（5）。产生segfault的代码是：
if (cluster[hi] == NULL) {
cluster[hi] = new vEB(subSize);
cluster[hi]->insert(lo);
summary->insert(hi);
}
else {
cluster[hi]->insert(lo); //here something is wrong with cluster[hi]
}
我找不到答案是什么，但是如果你把你的代码放在IDE中并进行调试，你就有更好的机会解决问题，因为你比我更了解你的代码。
我的发现与布鲁诺的相同。这是一个live test of your code。您可以修复它并再次测试它。
===========开始＃0 stensal运行时消息===========
运行时错误：[越界写入] 继续执行会导致未定义的行为，中止！
-
- Writing 4 bytes to 0x8aaa078 will corrupt the adjacent data.
-
- The memory-space-to-be-written (start:0x8aaa070, size:8 bytes) is allocated at
- file:/src/new.cpp::54, 17
-
- 0x8aaa070 0x8aaa077
- +------------------------------+
- |the memory-space-to-be-written|......
- +------------------------------+
- ^~~~~~~~~~
- the write starts at 0x8aaa078 that is right after the memory end.
-
- Stack trace (most recent call first) of the write.
- [1] file:/prog.cc::35, 13
- [2] file:/prog.cc::290, 10
- [3] [libc-start-main]
-
============＃0 stensal运行时消息结束============