实现一个双向有序列表，我该如何返回一个指针，以便给它一个值？

-1

我必须以特定的方式实现双向有序列表，并且我陷入了困境。我有一个Bag类，里面有一个Element类。现在问题出现在我想要将物品放入包中时。实现一个双向有序列表，我该如何返回一个指针，以便给它一个值？

一个元素有一个键（它的值），一个指向较小元素的指针（_down），另一个指向较大的（_up）。当我把一个新的元素袋子里面的代码如下（名称翻译，以便更容易理解）

void Bag::put(int e) { 
    if(_item_count==0){ 
     Element *element = new Element(e, nullptr, nullptr); 
     _bot = element; 
     _top = element; 
    }else{ 
     Element *p = _bot; 
     while(e > p->key()){ 
      p = p->up(); 
     } 
     Element *element = new Element(e, p, p->down()); 
     p->down() = element; 
    } 
}

所以问题是，P->向下（）是不可转让。我想我应该通过引用返回指针，但我不知道该怎么做。

下（）函数

Bag::Element *Bag::Element::down() { 
    return _down; 
}

我试图把&在许多地方，但我不能想出如何使这一切工作。

这里是完整的代码，如果需要的话，但它的变量主要是匈牙利语，如果需要，我会提供翻译。 Header on the left, cpp on the right

来源

2017-10-14 Viktor

嗯我很担心......如果你先把2加到你的清单上然后再加上3，该怎么办？ e会大于2，因此p = p-> up（），但p-> up（）元素应该为null，所以你的p-> key（）会被解引用null。 – Eddge

当我问这个问题时，我还没有把它放进去的实际程序，我只是想让它工作。但是你是对的，我在这里发布的代码还不是最终的（甚至没有接近它）。 – Viktor

这将返回一个非const左值参考指针，这是很好被分配到：

Bag::Element *&Bag::Element::down() { 
    return _down; 
}

或许你也应该提供一个const超载：

Bag::Element * const &Bag::Element::down() const { 
    return _down; 
}

中当然你应该相应地更新你的班级声明。

你也可以考虑使用一个结构来处理像Element这样简单的类，同时使指针字段成为public（这是结构的默认访问控制），通常情况下，你不会在C/C++中这样做， Java中，人们倾向于坚持使用私有领域和超级简单类的getter/setter（我不是说这个好或坏，只是一种约定。）

来源

2017-10-14 11:42:31

是的，这工作，谢谢 – Viktor

只需直接指定指针：

p->_down = element;

请注意，您只修改下一个元素的“向下”指针，还需要修改“up”poi前一个元素的中心。

还要注意，你的新元素可能是列表中的第一个或最后一个元素，你应该专门处理这些情况。一旦你这样做了，你可能会发现对空列表的特殊处理是不必要的。

来源

2017-10-14 11:48:47

实现一个双向有序列表，我该如何返回一个指针，以便给它一个值？

回答

相关问题