实现一个双向有序列表,我该如何返回一个指针,以便给它一个值?
我必须以特定的方式实现双向有序列表,并且我陷入了困境。我有一个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
这将返回一个非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(我不是说这个好或坏,只是一种约定。)
是的,这工作,谢谢 – Viktor
只需直接指定指针:
p->_down = element;
请注意,您只修改下一个元素的“向下”指针,还需要修改“up”poi前一个元素的中心。
还要注意,你的新元素可能是列表中的第一个或最后一个元素,你应该专门处理这些情况。一旦你这样做了,你可能会发现对空列表的特殊处理是不必要的。
嗯我很担心......如果你先把2加到你的清单上然后再加上3,该怎么办? e会大于2,因此p = p-> up(),但p-> up()元素应该为null,所以你的p-> key()会被解引用null。 – Eddge
当我问这个问题时,我还没有把它放进去的实际程序,我只是想让它工作。但是你是对的,我在这里发布的代码还不是最终的(甚至没有接近它)。 – Viktor