如何在链接的ilist中正确返回插入的元素

Question

我正在实现一个双链表的insert(在元素之前(和add(在元素之后(函数。我的问题是我必须返回的值的差异，以及它们为什么不同。

对于我的插入函数Link* insert(Link* n)，我必须使用return n。对于我的加法函数Link* add(Link* n)，我有return this。我已经测试了当我不这样做时会发生什么，前一个/后一个元素不会出现。我想知道为什么会这样，为什么我不能同时使用insert/add的return n(或return this(。

#include "std_lib_facilities.h"
class Link {
public:
string value; 
Link(const string& v, Link* p = nullptr, Link* s = nullptr)
: value{v}, prev{p}, succ{s} { }
Link* insert(Link* n) ;   // insert n before this object
Link* add(Link* n) ;      // insert n after this object
Link* erase() ;           // remove this object from list
Link* find(const string& s);    // find s in list
const Link* find(const string& s) const; // find s in list
Link* advance(int n) const;     // move n positions in list
Link* next() const { return succ; }
Link* previous() const { return prev; }
private:
Link* prev;
Link* succ;
};
//------------------------------------------------------------------------------
Link* Link::insert(Link* n)   // insert n before this object; return n
{
if (n == nullptr) return this;
n->succ = this;          
if (prev) prev->succ = n; 
n->prev = prev;        
prev = n;                 
return n;   // why?           
}
//------------------------------------------------------------------------------
Link* Link::add(Link* n)   // insert n after this object
{
if (n == nullptr) return this;
n->prev = this;
if (succ) succ->prev = n;
n->succ = succ;      
succ = n;      
return this; // why?
}
//------------------------------------------------------------------------------
Link* Link::erase()
{
if (succ) succ->prev = prev; // if (succ != nullptr)
if (prev) prev->succ = succ;
return succ;
}
//------------------------------------------------------------------------------
Link* Link::find(const string& s) // find s in list;
// return 0 for "not found"
{
Link* p = this;
while(p) {
if (p->value == s) return p;
p = p->succ;
}
return 0;
}
//------------------------------------------------------------------------------
void print_all(Link* p)
{
cout << "{ ";
while (p) {
cout << p->value;
if ( (p = p->next()) ) cout <<  ", ";
}
cout << " }";
}
//------------------------------------------------------------------------------
int main()
{
Link* norse_gods = new Link{"Thor"};
norse_gods = norse_gods->insert(new Link{"Odin"});
norse_gods = norse_gods->insert(new Link{"Zeus"});
norse_gods = norse_gods->insert(new Link{"Freia"});
Link* greek_gods = new Link{"Hera"};
greek_gods = greek_gods->add(new Link{"Athena"}); 
greek_gods = greek_gods->add(new Link{"Mars"});
greek_gods = greek_gods->add(new Link{"Poseidon"});
Link* p = greek_gods->find("Mars");
if (p) p->value = "Ares";
// Move Zeus into his correct Pantheon: 
{
Link* p = norse_gods->find("Zeus");
if (p) {
if (p==norse_gods) norse_gods = p->next();
p->erase();
greek_gods = greek_gods->insert(p);
}
}
// Finally, let's print out those lists:
print_all(norse_gods);
cout<<"n";
print_all(greek_gods);
cout<<"n";
}
//------------------------------------------------------------------------------

Answer 1

我认为函数insert和add的返回值不同的原因是，当函数insert应用于表示头节点的节点时，头节点发生了变化，新插入的节点变成了头节点。

另一方面，当在头节点之后添加新节点时，头节点保持不变。

因此，这两个函数都返回指向头节点的指针。

如果考虑主中的此代码片段

Link* norse_gods = new Link{"Thor"};
norse_gods = norse_gods->insert(new Link{"Odin"});
norse_gods = norse_gods->insert(new Link{"Zeus"});
norse_gods = norse_gods->insert(new Link{"Freia"});

则在成员函数insert的这些调用之后，头节点是包含字符串CCD_。也就是说，这些调用总是在头节点之前插入一个新节点，并且新插入的模式变为头节点。

在主中的这个代码片段中

Link* greek_gods = new Link{"Hera"};
greek_gods = greek_gods->add(new Link{"Athena"}); 
greek_gods = greek_gods->add(new Link{"Mars"});
greek_gods = greek_gods->add(new Link{"Poseidon"});

在函数add的这些调用之后，头节点是包含字符串CCD_ 11的节点。也就是说，在头节点之后插入新节点。指向头节点的指针保持不变。

在这两种情况下，在输出列表的函数中

void print_all(Link* p)
{
cout << "{ ";
while (p) {
cout << p->value;
if ( (p = p->next()) ) cout <<  ", ";
^^^^^^^^^^^^^
}
cout << " }";
}

您可以使用数据成员succ在一个向前的方向上遍历它

Link* next() const { return succ; }
^^^^^^^^^^^^