我写了一个具有insertAtStart, insertAtEnd, removeFromStart, removeFromEnd成员函数的Double链表类。检查下面的代码

class Node {
    public:
        int val;
        Node *next;
        Node *prev;

        Node(int v)
            : val(v),
              next(nullptr),
              prev(nullptr) {}
};



#include<iostream>
using namespace std;

#include "../node.h"

class LinkedList {
    private:
        Node* start;
        Node* end;

    public:
        LinkedList(): start(nullptr), end(nullptr) { }

        void insertAtStart(int val) {
            Node* n = new Node(val);
            if(start == nullptr) {
                start = n;
                end = n;
            } else {
                n->next = start;
                start = n;
            }
        }

        void insertAtEnd(int val) {
            Node* n = new Node(val);
            if(end == nullptr) {
                end = n;
                start = n;
            } else {
                end->next = n;
                n->prev = end;
                end = n;
            }
        }

        void removeFromStart() {
            if(start == nullptr) return;
            if(start == end) {
                start = end = nullptr;
                return;
            }
            start = start->next;
            start->prev = nullptr;
        }

        void removeFromEnd() {
            if(end == nullptr) return;
            if(start == end) {
                start = end = nullptr;
                return;
            }
            end = end->prev;
            end->next = nullptr;
        }

        void printList() {
            Node *ptr = start;
            while(ptr != nullptr) {
                cout << ptr->val << " ";
                ptr = ptr->next;
            }
            cout << endl;
        }
};



我使用以下主要功能测试了上面的代码,它运行良好

#include "double-linked-list.h"

int main() {
    LinkedList l = LinkedList();
    l.insertAtStart(1);
    l.insertAtStart(2);
    l.insertAtStart(3);
    l.insertAtStart(4);
    l.insertAtStart(5);
    l.insertAtEnd(6);
    l.insertAtEnd(7);
    l.insertAtEnd(8);
    l.insertAtEnd(9);
    l.insertAtEnd(10);
    l.printList();
    l.removeFromStart();
    l.printList();
    l.removeFromStart();
    l.printList();
    l.removeFromEnd();
    l.printList();
    l.removeFromEnd();
    l.printList();
    return 0;
}



输出:

Inserting 1 at start
Linked list: 1
Inserting 2 at start
Linked list: 2 1
Inserting 3 at start
Linked list: 3 2 1
Inserting 4 at start
Linked list: 4 3 2 1
Inserting 5 at start
Linked list: 5 4 3 2 1
Inserting 6 at end
Linked list: 5 4 3 2 1 6
Inserting 7 at end
Linked list: 5 4 3 2 1 6 7
Inserting 8 at end
Linked list: 5 4 3 2 1 6 7 8
Inserting 9 at end
Linked list: 5 4 3 2 1 6 7 8 9
Inserting 10 at end
Linked list: 5 4 3 2 1 6 7 8 9 10
Removing from start
Linked list: 4 3 2 1 6 7 8 9 10
Removing from start
Linked list: 3 2 1 6 7 8 9 10
Removing from end
Linked list: 3 2 1 6 7 8 9
Removing from end
Linked list: 3 2 1 6 7 8


我现在写了一个从上述链接列表类派生的Queue类

#include "../double-linked-list/double-linked-list.h"

class Queue {
    private:
        LinkedList q;
    public:
        Queue() {}

        void enqueue(int val) {
            q.insertAtStart(val);
        }

        void dequeue() {
            q.removeFromEnd();
        }

        void printQueue() {
            q.printList();
        }
};


和以下主要功能进行测试

#include "queue.h"

int main() {
    Queue q = Queue();
    q.enqueue(1);
    q.printQueue();
    q.enqueue(2);
    q.printQueue();
    q.enqueue(3);
    q.printQueue();
    q.enqueue(4);
    q.printQueue();
    q.enqueue(5);
    q.printQueue();
    q.dequeue();
    q.printQueue();
    q.dequeue();
    q.printQueue();
}


入队似乎工作完美,但出队却没有。出队后甚至不打印任何内容。

输出:

Enqueuing 1
1
Enqueuing 2
2 1
Enqueuing 3
3 2 1
Enqueuing 4
4 3 2 1
Enqueuing 5
5 4 3 2 1
Denqueuing


为了调试,我在coutremoveFromEnd函数中放置了LinkedList语句。

void LinkedList::removeFromEnd(){
    if(end == nullptr) return;
    if(start == end) {
        start = end = nullptr;
        return;
    }
    end = end->prev;
    cout << "print statement 1";
    end->next = nullptr;
    cout << "print statement 2";
}


现在,当我再次运行队列的主要功能时,打印语句1正在控制台中打印,而第二个则不在。我不明白为什么。有人可以帮我弄清楚我在做什么错吗?

编辑:

阅读评论后,我对以下功能进行了更改

void insertAtStart(int val) {
    Node* n = new Node(val);

    // If start and end are null
    if(start == nullptr && end == nullptr) {
        start = end = n;
    }
    // There is at least 1 node in the list
    else {
        n->next = start;
        start->prev = n;
        // There is only one node in the list
        if(start->next == nullptr) {
            end->prev = n;
        }
        start = n;
    }
}

void insertAtEnd(int val) {
    Node* n = new Node(val);

    // If start and end are null
    if(start == nullptr && end == nullptr) {
        start = end = n;
    }
    // There is at least 1 node in the list
    else {
        n->prev = end;
        end->next = n;
        // There is only one node in the list
        if(end->prev == nullptr) {
            start->next = n;
        }
        end = n;
    }
}



这工作了。如果感兴趣,我将整个链接列表类发布为答案。

最佳答案

对于初学者,该程序存在内存泄漏,因为您没有删除分配的节点。

至于你的问题,那么这个功能

    void insertAtStart(int val) {
        Node* n = new Node(val);
        if(start == nullptr) {
            start = n;
            end = n;
        } else {
            n->next = start;
            start = n;
        }
    }


是无效的。将新节点添加到列表的开头时,它不会刷新数据成员end->prev(更确切地说是start->prev)。即end->prev始终等于nullptr

至少重写函数

    void insertAtStart(int val) {
        Node* n = new Node(val);
        if(start == nullptr) {
            start = n;
            end = n;
        } else {
            n->next = start;
            start->prev = n; // <===
            start = n;
        }
    }

关于c++ - 出队不适用于从双链表继承的Queue类,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/59047852/

10-12 00:32
查看更多