双向链表的输出

Question

我一直在尝试制作一个双向链表（我觉得我已经很接近了），但我似乎无法获得正确的输出。我的输出似乎向我抛出一些非常随机的值。我觉得问题是由于我的操作员超载造成的，但我似乎无法理解它并且早晨的太阳接近 XD。非常感谢大家的帮助！

同样为了方便起见，预期输出为：（忽略行间空格）

马西王子

乔尔·大卫·康拉德·马西王子

Nic Lindo Ernest Joel David Conrad Prince Massi

林多·欧内斯特·乔尔·大卫·康拉德·马西王子

Lindo Ernest Joel David Conrad Pince Massi Jesse Shane Richard

Lindo Ernest Joel David Conrad Pince Massi Jesse Shane

林多·欧内斯特·乔尔·大卫·康拉德·平斯·马西·杰西

林多·欧内斯特·乔尔·大卫·康拉德·平斯·马西

林多·欧内斯特·乔尔·大卫·康拉德·平斯

#include <cstdlib>
#include <string>
#include <iostream>

using namespace std;

class StringNode{
    public:
        string elem;
        StringNode* next;
        StringNode* prev;
        friend class StringLinkedList;
};

class StringLinkedList{
    public:
        StringLinkedList();
        ~StringLinkedList();
        bool isEmpty() const;
        const string& front() const;
        const string& back() const;
        void addFront(const string& e);
        void addBack(const string& e);
        void removeFront();
        void removeBack();
        friend ostream& operator<<(ostream& out, const StringLinkedList& obj);
    private:
        StringNode* head;
        StringNode* tail;
    protected:
        void add(StringNode* v, const string& e);
        void remove(StringNode* v);
};

StringLinkedList::StringLinkedList(){
    head = new StringNode;
    tail = new StringNode;
    head->next = tail;
    tail->prev = head;
}

StringLinkedList::~StringLinkedList(){
    while(!isEmpty()){
        removeFront();
    }
    delete head;
    delete tail;
}

bool StringLinkedList::isEmpty() const{
    return (head->next == tail);
}

const string& StringLinkedList::front() const{
    return head->next->elem;
}

const string& StringLinkedList::back() const{
    return tail->prev->elem;
}

void StringLinkedList::add(StringNode* v, const string& e){
    StringNode* u = new StringNode; u->elem = e;
    u->next = v;
    u->prev = v->prev;
    v->prev->next = v->prev = u;
}

void StringLinkedList::addFront(const string& e){
    add(head->next, e);
}

void StringLinkedList::addBack(const string& e){
    add(tail, e);
}

void StringLinkedList::remove(StringNode* v){
    StringNode* u = v->prev;
    StringNode* w = v->next;
    u->next = w;
    w->prev = u;
    delete v;
}

void StringLinkedList::removeFront(){
    remove(head->next);
}

void StringLinkedList::removeBack(){
    remove(tail->prev);
}

ostream& operator <<( ostream& out, const StringLinkedList &obj )
{
    for ( StringNode *temp = obj.head->next; temp != obj.tail; temp = temp->next )
    {
        out << temp->elem << ' ';
    }
    return out;
}

int main(void){
    StringLinkedList* myList = new StringLinkedList();
    myList->addFront("Massi");
    myList->addFront("Prince");
    cout<< *myList << endl;
    myList->addFront("Conrad");
    myList->addFront("David");
    myList->addFront("Joel");
    cout<< *myList << endl;
    myList->addFront("Ernest");
    myList->addFront("Lindo");
    myList->addFront("Nic");
    cout<< *myList << endl;
    myList->addFront("Sasha");
    myList->removeFront();
    cout<< *myList << endl;
    myList->removeFront();
    cout<< *myList << endl;
    myList ->addBack("Jesse");
    myList ->addBack("Shane");
    myList ->addBack("Richard");
    cout << *myList << endl;
    myList -> removeBack ();
    cout << *myList << endl;
    myList -> removeBack ();
    cout << *myList << endl;
    myList -> removeBack ();
    cout << *myList << endl;
    myList -> removeBack ();
    cout << *myList << endl;
    return 0;
}

Answer 1

假设 u 在序列中。

下面的代码

void StringLinkedList::add(StringNode* v, const string& e){
StringNode* u = new StringNode; u->elem = e;
u->next = v;
u->prev = v->prev;
v->prev->next = v->prev = u; // this line has the issue

}

执行以下过程（假设 1 = head，2 = v，3 = tail）

让我们在v = 2和tail = 3之间添加“4”，即执行add(tail, data)。

u = 4; 4的下一个是尾巴 4的前一个是tail(3)的当前前一个，也就是2 现在我们修改原始列表的向后链接。然后 3 的前一个是 4，但是 4（现在是 v->prev）的下一个是 4，也就是它自己。

逐行浏览代码确实很有帮助。使用橡皮鸭：

Answer 2

这位运营商

ostream& operator<<(ostream& out, const StringLinkedList& obj){
    StringNode* temp = obj.head;
    while(temp != NULL){
        out << temp->elem << ' ';
        temp = temp->next;
    }
    return out;
}

是错误的，因为它试图输出不存储字符串的 head 的数据成员 elem 和也不存储字符串且具有未初始化成员的 tail 的数据成员next.

函数可以这样定义

ostream& operator <<( ostream& out, const StringLinkedList &obj )
{
    for ( StringNode *temp = obj.head->next; temp != obj.tail; temp = temp->next )
    {
        out << temp->elem << ' ';
    }

    return out;
}

另外add函数的最后一句是错误的

v->prev->next = v->prev = u;

你应该把它分成两个语句。例如

void StringLinkedList::add( StringNode *v, const string &e )
{
    StringNode *u = new StringNode; u->elem = e;
    u->next = v;
    u->prev = v->prev;
    u->prev->next = u;
    v->prev = u;
}

双向链表的输出

Output of doubly linked list

c++

pointers

linked-list

operator-overloading

doubly-linked-list