最近在看OF的类entry时涉及到了DLListBase::link这个内部结构,发现其中DLListBase的一个成员函数的函数体存在问题。该函数体源代码如下:
bool DLListBase::swapUp(DLListBase::link* a)
{
if (first_ != a)
{
link* ap = a->prev_;
if (ap == first_)
{
first_ = a;
}
if (a == last_)
{
last_ = ap;
}
if (a->next_)
{
a->next_->prev_ = ap;
}
if (ap->prev_)
{
ap->prev_->next_ = a;
}
a->prev_ = ap->prev_;
ap->prev_ = a;
ap->next_ = a->next_;//问题就出在这里,因为在定义link时当a为最后一个元素时a->next_=a的
a->next_ = ap;
return true;
}
else
{
return false;
}
}
其中问题就出在红色代码这一行,当函数参数a为链表尾部元素时,执行到这一行将出错。这主要是这里双向链表定义的问题,link的首元素的前向指针是指向其自身的,尾元素的后向也指向自身,当交换尾部两个元素时,执行到上面代码红色处使得交换之后的尾部元素(原倒数第二个元素)的后向指针并不是指向自身而是指向原尾部元素,从而再次进行两者交换时将出现错误。
解决以上问题有两种方法:
一、修改双向链表结构link定义使尾部元素的后向指针及首元素的前向指针都指向NULL,则不会出现上述问题;
二、修改上述函数的函数体如下:
bool DLListBase::swapUp(DLListBase::link* a)
{
if (first_ != a)
{
link* ap = a ->prev_;
link* app = ap->prev_;
link* an = a->next_;
if (ap == first_)
{
first_ = a;
}
if (a == last_)
{
last_ = ap;
}
if (app==ap)
{
a ->prev_ = a;
}
else
{
a->prev_=app;
app->next_=a;
}
if (an==a)
{
ap->next_ = ap;
}
else
{
ap->next_ = an;
an->prev_=ap;
}
a ->next_ = ap;
ap->prev_ = a;
return true;
}
else
{
return false;
}
}