我写了一个具有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
为了调试,我在
cout
的removeFromEnd
函数中放置了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/