跳过列表中的细分故障

Question

我正在实现跳过列表。插入功能正常运行，并且能够打印列表。但是现在，我正在尝试实现"查找"功能，在此功能中，我在循环的条件下会得到一个分段故障。当我调试代码时，除最后一个迭代外，所有迭代都可以正常工作。在条件检查期间的最后一次迭代中，循环循环进入该行的分割故障

while（x-> rgt-> key＆lt; searchKey）

我无法理解原因，因为当我掌握代码时，一切似乎都很好。请看一下，告诉我我在做什么错？

如果我搜索1和2，也可以找到功能正常，但是在3和4时发生故障。

。

class SkipList
{
private:
         struct node{
         int key;
         int data;
         int level;
         struct node* rgt = nullptr;
         struct node* dwn = nullptr ;
         node(int k, int value, int l):
         key(k), data(value), level(l)
            {}
        };

        //generates the ndde level in tha range [1,maxLevel).
        int randomLevel() const;
        //returns a set of pointers to the location at each node where new links are to be created
        std::vector<node*> update(int searchKey) const ;
        //creates a new node and returns a pointer to it
        static node* makeNode(int key, int val, int level);
        // Returns the first node for which node->key < searchKey is false
        node* lower_bound(int searchKey) const;
        const float probability;
        const int maxLevel;

        // head and tail vectors
        vector<node*> head;
        vector<node*> nil;

public:
        SkipList();
      // ~SkipList();
        void insert(int searchKey, int val);
        void find(int searchKey) const;
        void erase(int searchKey);
        void print() const;
 };

SkipList::SkipList() :
probability(0.5), maxLevel(4)
{
head.resize(maxLevel, nullptr);
nil.resize(maxLevel,nullptr);
int headkey = std::numeric_limits<int>::min();
int nilkey  = std::numeric_limits<int>::max();
   for(int i = 0; i < maxLevel ;i++)
   {
    head[i] = new node(headkey,0,maxLevel-1);
    nil[i] = new node(nilkey,0,maxLevel-1);
       if(i>0)
       {
         head[i]->dwn = head[i-1];
         nil[i] ->dwn = nil[i-1];
       }
       head[i]->rgt = nil[i];
 }

}

void SkipList::find(int searchKey) const
 {
 node* x = head[maxLevel-1];
for(int i = maxLevel-1 ; i>= 0 ;i--)
{
  while(x->rgt->key < searchKey)
  {
    x = x->rgt;
  }
   if(i != 0){x = x->dwn;}
 }
if ((x->rgt->key == searchKey))
   cout<<"Found"<<endl;
}

void SkipList::insert(int searchKey, int val)
{
vector <node*> preds  = update(searchKey);
node* temp;
const int newLevel = randomLevel();

for(int i = 0; i< newLevel; i++)
{
 node* ptr = makeNode(searchKey,val, newLevel-1);
 temp = preds[i]->rgt;
 preds[i]->rgt = ptr;
 ptr->rgt = temp;
 }
}


void SkipList::print() const
{
node *ptr = head[0]->rgt;
while(ptr->rgt != nullptr)
{
 cout<<"Key: "<<ptr->key<<"  Data: "<<ptr->data<<"  Level: "<<ptr->level<<endl;
 ptr = ptr->rgt;
}

}

int SkipList::randomLevel() const
{
int v = 1;
while (((double)std::rand() / RAND_MAX) < probability &&
    v < maxLevel)
{
    v++;
}
return v;
}

SkipList::node* SkipList::makeNode(int key, int value, int level)
{
return new node(key, value, level);
}

std::vector<SkipList::node*>SkipList::update(int searchKey) const
{
 int level = head[0]->level;
 std::vector<node*> result(level,nullptr);
 node* x ;
 for(unsigned int i = level;i-- >0;)
 {
 x = head[i];
 while(x->rgt->key < searchKey)
 {
   x = x->rgt;
 }
  result[i]= x;
}
return result;
}


int main()
{
SkipList s;
int x,y;
for(int i = 1;i< 5;i++)
{
s.insert(i,i);
}
s.print();
cout<<endl;
s.find(3);


return 0;
}

Answer 1

一个简单的调试在此循环中显示了这一点：

while(x->rgt->key < searchKey)
{
    x = x->rgt;
}

x的值变为 NULL。

我猜这是您尝试在列表末尾添加元素的情况。

如果是这样，那么您应该为这种情况提出其他解决方案。

例如：

while(x->rgt && x->rgt->key < searchKey)
{
    x = x->rgt;
}
if (x->rgt)
{
   // Use your original code
}
else
{
    // Handle this special case
}