极客笔记C++程序 对给定链表中元素进行成对交换
链表是一种常见的数据结构，其中每个节点都包含一个数据元素和一个指向下一个节点的指针。在很多情况下，我们需要对链表进行操作。其中一种常见的操作是对链表中的元素进行成对交换。本文将介绍如何使用C++编写一个对给定链表中元素进行成对交换的程序。
链表类的定义
在本程序中，我们需要定义一个表示链表的类。这个类应该至少包含两个属性：指向链表头部的指针和链表的大小。对于每个节点，我们可以用一个嵌套的结构体来表示它。每个节点应至少包含一个数据元素和指向下一个节点的指针。下面是一个链表类的定义：
“` C++
#include
using namespace std;
// 链表节点的类型定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class LinkedList {
public:
// 构造函数和析构函数
LinkedList();
~LinkedList();
// 链表操作
void append(int val); // 在链表尾部添加一个元素
void print(); // 输出链表的所有元素
void swapPairs(); // 将链表中的元素成对交换
private:
int size; // 链表的大小
ListNode *head; // 指向链表头部的指针
};
### 链表类的实现
在链表类的实现中，我们需要实现上面定义的三个公有函数以及一个私有函数。append函数用于在链表的尾部添加一个元素，print函数用于输出链表中的所有元素，swapPairs函数用于将链表中的元素成对交换。下面是一个链表类的实现：
``` C++
// 链表类的构造函数
LinkedList::LinkedList(){
head = NULL;
size = 0;
}
// 链表类的析构函数
LinkedList::~LinkedList() {
ListNode *current_node = head;
ListNode *next_node;
while(current_node != NULL) {
next_node = current_node->next;
delete current_node;
current_node = next_node;
}
}
// 在链表尾部添加一个元素
void LinkedList::append(int val) {
ListNode *new_node = new ListNode(val);
if(head == NULL) {
head = new_node;
} else {
ListNode *current_node = head;
while(current_node->next != NULL) {
current_node = current_node->next;
}
current_node->next = new_node;
}
size++;
}
// 输出链表的所有元素
void LinkedList::print() {
ListNode *current_node = head;
while(current_node != NULL) {
cout << current_node->val << " ";
current_node = current_node->next;
}
cout << endl;
}
// 将链表中的元素成对交换
void LinkedList::swapPairs() {
ListNode *pre_node = NULL;
ListNode *cur_node = head;
// 对于每一对节点，交换它们的位置
while (cur_node != NULL && cur_node->next != NULL) {
ListNode *next_node = cur_node->next;
cur_node->next = next_node->next;
next_node->next = cur_node;
// 更新前一个节点的指针
if (pre_node != NULL) {
pre_node->next = next_node;
} else {
head = next_node;
}
pre_node = cur_node;
cur_node = cur_node->next;
}
}
完整的程序
在上面的代码中，我们已经定义了链表类并实现了所需的三个公有函数以及一个私有函数。现在，我们将把这些函数结合起来并编写一个完整的程序，以便更好地理解它们的用法。下面是一个完整的程序：
“` C++
#include
using namespace std;
//// 链表节点的类型定义
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class LinkedList {
public:
// 构造函数和析构函数
LinkedList();
~LinkedList();
// 链表操作
void append(int val);
void print();
void swapPairs();
private:
int size;
ListNode *head;
};
LinkedList::LinkedList() {
head = NULL;
size = 0;
}
LinkedList::~LinkedList() {
ListNode *current_node = head;
ListNode *next_node;
while(current_node != NULL) {
next_node = current_node->next;
delete current_node;
current_node = next_node;
}
}
void LinkedList::append(int val) {
ListNode *new_node = new ListNode(val);
if(head NULL) {
head = new_node;
} else {
ListNode *current_node = head;
while(current_node->next != NULL) {
current_node = current_node->next;
}
current_node->next = new_node;
}
size++;
}
void LinkedList::print() {
ListNode *current_node = head;
while(current_node != NULL) {
cout << current_node->val << ” “;
current_node = current_node->next;
}
cout << endl;
}
void LinkedList::swapPairs() {
ListNode *pre_node = NULL;
ListNode *cur_node = head;
while (cur_node != NULL && cur_node->next != NULL) {
ListNode *next_node = cur_node->next;
cur_node->next = next_node->next;
next_node->next = cur_node;
if (pre_node != NULL) {
pre_node->next = next_node;
} else {
head = next_node;
}
pre_node = cur_node;
cur_node = cur_node->next;
}
}
int main() {
// 创建一个新的链表
LinkedList *list = new LinkedList();
// 添加元素到链表中
list->append(1);
list->append(2);
list->append(3);
list->append(4);
// 输出链表中的所有元素
cout << "Original list：" << endl;
list->print();
// 对链表中的元素进行成对交换
list->swapPairs();
// 输出交换后的链表
cout << "Swapped list：" << endl;
list->print();
// 释放链表对象
delete list;
return 0;
}
“`
在上面的程序中，我们创建了一个链表对象，将一些元素添加到链表中，并输出了原始的链表。然后，我们对链表中的元素进行成对交换，并输出交换后的链表。最后，我们释放了链表对象，以便释放程序的内存。
结论
在本文中，我们介绍了如何使用C++编写一个对给定链表中元素进行成对交换的程序。我们使用一个链表类来表示链表，并实现了三个公有函数以及一个私有函数来操作它。我们编写了一个完整的程序来演示这些函数的用法，以便更好地理解它们的工作原理。此外，我们还讨论了链表类的一些常见操作，如在链表的尾部添加元素和输出链表中的所有元素。