帮我用C++实现一个双链表,其中要包含swap函数,用于交换链表中的两个节点
时间: 2024-09-22 13:08:55 浏览: 45
好的,这里是一个简单的C++实现,包括了双链表结构和一个`swap`函数,用于交换链表中指定的两个节点:
```cpp
#include <iostream>
// 双链表节点定义
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};
// 双链表头结点定义
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// 插入节点到链表末尾
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (!head) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
// 删除节点
void deleteNode(int value) {
Node* current = head;
while (current) {
if (current->data == value) {
if (current->prev) {
current->prev->next = current->next;
} else {
head = current->next;
}
if (current->next) {
current->next->prev = current->prev;
} else {
tail = current->prev;
}
delete current;
return;
}
current = current->next;
}
}
// 交换链表中两个节点
void swapNodes(int index1, int index2) {
if (index1 < 0 || index2 < 0) {
throw std::invalid_argument("Indexes must be non-negative.");
}
Node* firstNode = findNode(index1);
Node* secondNode = findNode(index2);
if (!firstNode || !secondNode) {
throw std::out_of_range("Invalid indexes.");
}
// 临时存储第一个节点的信息
int tempData = firstNode->data;
Node* tempPrev = firstNode->prev;
Node* tempNext = firstNode->next;
// 更新节点之间的链接
firstNode->data = secondNode->data;
secondNode->data = tempData;
firstNode->prev = secondNode->prev;
secondNode->prev = tempPrev;
firstNode->next = secondNode->next;
secondNode->next = tempNext;
// 如果交换的是头节点,需要调整头指针
if (firstNode == head) {
head = secondNode;
}
// 同样,如果交换的是尾节点,需要调整尾指针
if (secondNode == tail) {
tail = firstNode;
}
}
// 查找节点(返回非nullptr则找到,否则返回nullptr)
Node* findNode(int index) {
Node* current = head;
for (int i = 0; current && i < index; ++i) {
current = current->next;
}
return current;
}
// 打印链表
void printList() {
Node* temp = head;
while (temp) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
};
int main() {
DoublyLinkedList list;
list.insertAtEnd(1);
list.insertAtEnd(2);
list.insertAtEnd(3);
list.insertAtEnd(4);
list.printList();
try {
list.swapNodes(1, 3);
list.printList();
} catch (const std::exception& e) {
std::cerr << "Error: " << e.what() << std::endl;
}
return 0;
}
```
这个程序首先定义了双链表节点结构和链表类,提供了插入、删除、查找和打印链表的功能,以及一个`swapNodes`方法用于交换两个节点。注意,你需要自己处理异常情况,例如检查索引是否有效。在`main`函数中,我们创建了一个链表并演示了如何使用`swapNodes`方法。
阅读全文