在链表中按顺序插入节点

Question

我正在尝试编写一个成员函数Link* add_ordered (Link* n)，它在列表中按字典顺序添加节点，但是，当我尝试打印有序列表时，只打印最后添加的节点，即"Poseidon"。

以下是我的节点界面：

struct God {
    // public members of God
    std::string name;
    std::string mythology;
    std::string vehicle;
    std::string weapon;
    // constructor
    God (std::string n, std::string m, std::string v = " ", std::string w = " ")
        : name(n), mythology(m), vehicle(v), weapon(w) { }
};
//------------------------------------------------------------------------
class Link {
public:
    God god;
    // consructor
    Link (God g, Link* p = 0, Link* s = 0)
        : god(g), prev(p), succ(s) { } 
    // modifying member functions
    Link* insert (Link* n);
    Link* add (Link* n);
    Link* add_ordered (Link* n);
    Link* erase (void);
    Link* find (const std::string& v);
    // non - modifying member functions
    Link* advance (int n);
    const Link* find (const std::string& n) const;
    Link* previous () { return prev; }
    Link* next () { return succ; }
private:
    Link* prev;
    Link* succ;
};

add_ordered():中使用的成员函数

Link* Link::insert (Link* n) {
    if (n == 0) return this;
    if (this == 0) return n;
    n->succ = this;
    n->prev = prev;
    if (prev) prev->succ = n;
    prev = n;
    return n;
}

最后，这里是执行节点排序的函数：

Link* Link::add_ordered (Link* n) {
    // check if nodes valid
    if (n == 0) return this;
    if (this == 0) return n;
    // pointer to this object
    Link *p = this;
    // order in lexicographically increasing order in terms of link's god's name
    while (p) {
        // if new node value smaller than the one in current node, insert before current node.
        if (n->god.name < p->god.name){
            insert(n);
            break;
        // otherwise go to previous node in the list
        } else { 
            p = prev;
        }
    } 
    // return the newly added, ordered Link
    return n;
}

以下是我如何尝试创建一个有序的双链接列表：

int main () {
    // God(name(n), mythology(m), vehicle(v), weapon(w)) 
    // Greek mythology list of Gods
    Link* greek_gods = new Link(God("Zeus", "Greek", "", "lightning"));
    greek_gods = greek_gods->add_ordered(new Link(God("Hera", "Greek" )));
    greek_gods = greek_gods->add_ordered(new Link(God("Athena", "Greek")));
    greek_gods = greek_gods->add_ordered(new Link(God("Ares", "Greek")));
    greek_gods = greek_gods->add_ordered(new Link(God("Poseidon", "Greek" )));
   // print the list
   std::cout <<"{";
   while (greek_gods) {
       std::cout << greek_gods->god.name <<", "
                 << greek_gods->god.mythology <<", "
                 << greek_gods->god.vehicle <<", "
                 << greek_gods->god.weapon;
       // I've tried both directions, using greek_gods->next()
       if (greek_gods = greek_gods->previous()) std::cout <<'n';
   }
   std::cout <<"}";
}

我已经尝试了一段时间，但没有成功，所以任何帮助都将不胜感激。我真的看不出add_ordered()出了什么问题。

---

附言：如果我使用add()或insert()创建相同的列表，那么整个列表将完美打印。

Answer 1

Link::add_ordered始终返回其参数（如果参数为null，则返回this，但在您的情况下不会执行该分支）。因此，所有

greek_gods = greek_gods->add_ordered(new Link(God("Hera", "Greek" )));

程序中的行将不断使greek_gods指向插入的链接。

Answer 2

根据@Frerich Raabe的备注，对函数add_ordered()进行了修改，使其始终返回列表的起始节点。此外，还会添加新的条件if语句，以检查新节点是否已按顺序排列，如果已按顺序，则将其添加到列表前面：

Link* Link::add_ordered (Link* n) {
    // check if nodes valid
    if (n == 0) return this;
    if (this == 0) return n;
    // pointer to this object
    Link *p = this;
    // if node already in order, add it in front of the list
    if (n->god.name < p->god.name) {
        add(n);
        // return current first node of the list
        return n;
    }
    // traverse existing list till new node's name smaller than current node's
    while (!(n->god.name < p->god.name) && p) {
        // previous node
        Link* temp = p;
        // if last node's name is smaller than new node's, add new at the end 
        if (!(p = p->prev)) {
            n->prev = nullptr;
            n->succ= temp;
            temp->prev = n;
            return this;
        }
    } 
    // add n in front of current node
    n->succ = p->succ;
    n->prev = p;
    if (p->succ){
        p->succ->prev = n;
   }
   p->succ = n;
   // return current first node
   return this;
}