在双向链表中搜索多次找到成员

Question

我正在完成 PPPC++ 的练习，我有一个列表 class，其中包含多个神及其属性。

例如：{Thor, Norse, Chariot, Mjolnir} 或 {Hera, Greek, chariot, pomegranate} 其中托尔是北欧神，赫拉是希腊神。

我正在尝试编写代码来查找指向所有希腊神的指针。

而且我不明白为什么赫拉被发现了两次，而阿瑞斯却被发现了四次。怎么了？谢谢！

found 0x5586b65353f0 Poseidon
found 0x5586b6535350 Athena
found 0x5586b65351d0 Hera
found 0x5586b65351d0 Hera
found 0x5586b6534f50 Ares
found 0x5586b6534f50 Ares
found 0x5586b6534f50 Ares
found 0x5586b6534f50 Ares
found 0x5586b6534eb0 Zeus

密码是：

#include <iostream>
#include <stdexcept>
#include <string>
using namespace std;

struct God
{
    God(const string &n, const string &m, const string &v, const string &w)
        : name{n}, mythology{m}, vehicle{v}, weapon{w} {}

    string name;
    string mythology;
    string vehicle;
    string weapon;
};

class Link
{
public:
    God god; 
    Link(const string &n, const string &m, const string &v, const string &w, Link *p = nullptr, Link *s = nullptr)
        : god{n, m, v, w}, prev{p}, succ{s} {}
    Link *insert(Link *n);                 // insert n before this object
    Link *find_mythology(const string &s); // find s 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;
    if (this == nullptr)
        return n;
    n->succ = this;     // this object comes after n
    if (prev)           // if prev of this (object) is not zero - meaning there's a Link object before this object (or p)
        prev->succ = n; // perv->succ
    n->prev = prev;     // this object’s predecessor becomes n’s predecessor
    prev = n;           // n becomes this object’s predecessor
    return n;           // returns n(the new element) which is before the top node
}
Link *Link::find_mythology(const string &s) // find s in list;
{
    Link *p = this;
    while (p)
    {
        if (p->god.mythology == s)
            return p;
        p = p->succ; // move to the next node
    }
    return nullptr; // return nullptr for “not found”
}
void print_all(Link *p)
{
    while (p)
    {
        cout << " " << p->god.name << ", " << p->god.mythology << ", " << p->god.vehicle << ", " << p->god.weapon;
        if (p = p->next()) // moved to the next node
            cout << "\n";
    }
}

int main()
{
    Link *all_gods = new Link{"Zeus", "Greek", "chair", "lightning"};
    all_gods = all_gods->insert(new Link{"Ares", "Greek", "wings", "sword"});
    all_gods = all_gods->insert(new Link{"Odin", "Norse", "Sleipner", "Gungnir"});
    all_gods = all_gods->insert(new Link{"Thor", "Norse", "Chariot", "Mjolnir"});
    all_gods = all_gods->insert(new Link{"Freia", "Norse", "chariot", "Brisingamen"});
    all_gods = all_gods->insert(new Link{"Hera", "Greek", "chariot", "pomegranate"});
    all_gods = all_gods->insert(new Link{"Tyr", "Norse", "chariot", "spear of justice"});
    all_gods = all_gods->insert(new Link{"Athena", "Greek", "chariot", "thunderbolt"});
    all_gods = all_gods->insert(new Link{"Poseidon", "Greek", "the sea", "trident"});

    print_all(all_gods); // cout the type of the 1st element
    cout << "\n\n";

//while (all_gods)
//{
//    Link *p = all_gods->find_mythology("Greek"); // this returns a pointer where it finds a Norse
//     cout << "found " << p << ' ' << p->god.name << '\n';
//   all_gods = all_gods->next();
//}

Link *p = all_gods;
while (p)
{
    if (p->god.mythology == "Greek")
        cout << "found " << p << ' ' << p->god.name << '\n';
    p = p->next();
}
delete[] p;
// here I will still use all_gods before deleting it below
delete all_gods;

print_all(all_gods);
cout << "\n\n";
print_all(p);
cout << "\n\n";
}

编辑

我更改了 main() 中的 while 循环，现在它执行了我想要的操作。

Answer 1

你的代码看起来不错（虽然不是很 OO）。

它似乎也按照我期望的方式工作：

// When you start the list is:
//    Poseidon : Athena : Tyr : Hera ......
while (all_gods)
{
    // So first time threw this loop you find: Poseidon
    Link *p = all_gods->find_mythology("Greek");
    cout << "found " << p << ' ' << p->god.name << '\n';

    // Now you are altering the list (and leaking an object.
    // but thats another question).
    //
    
    all_gods = all_gods->next();
    // But you dropped "Poseidon" off the front so the list is now:
    // Athena : Tyr : Hera ......
}

所以你第二次围绕循环打印 Athena。然后从列表中删除 Athena，因此列表为 Tyr : Hera .......

所以你的第三次循环你将打印 Hera（第一个希腊神）。但是然后你删除 Tyr 所以列表是 Hera .......

所以第四次循环你将再次打印 Hera 因为她仍然在列表中并且是第一个希腊神。

在双向链表中搜索多次找到成员

Search in a Doubly-Linked List founds members multiple times

c++

doubly-linked-list

编辑