数据结构与算法创建程序文件exp1-2.cpp,实现单链表存储及其基本操作后,完成线性表链表的逆置操作
时间: 2024-10-18 11:10:08 浏览: 46
数据结构与算法基础课程 C语言C++程序语言设计教程 2_3线性表-链表 共43页.pptx
在C++中,为了创建一个名为`exp1-2.cpp`的程序文件,我们将使用数据结构单链表并实现一些基本操作,如插入、删除和遍历。接下来,我们将添加函数来逆置这个链表。首先,我们需要定义节点类`Node`和链表类`LinkedList`。
```cpp
#include <iostream>
// 定义链表节点
class Node {
public:
int data;
Node* next;
Node(int value) : data(value), next(nullptr) {}
};
// 链表类,包含基本操作
class LinkedList {
private:
Node* head;
public:
LinkedList() : head(nullptr) {}
// 插入节点
void insert(int value) {
if (head == nullptr) {
head = new Node(value);
} else {
Node* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = new Node(value);
}
}
// 删除节点
void remove(int value) {
if (head == nullptr) return;
if (head->data == value) {
Node* temp = head;
head = head->next;
delete temp;
return;
}
Node* current = head;
while (current->next != nullptr && current->next->data != value) {
current = current->next;
}
if (current->next != nullptr) {
Node* temp = current->next;
current->next = current->next->next;
delete temp;
}
}
// 遍历链表
void traverse() {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << "\n";
}
// 逆置链表
void reverse() {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next; // 保存当前节点的下一个节点
current->next = prev; // 将当前节点的next指向前一个节点
prev = current; // 更新前一个节点
current = next; // 更新当前节点
}
head = prev; // 设置新的头节点
}
};
int main() {
LinkedList list;
list.insert(1);
list.insert(2);
list.insert(3);
list.traverse(); // 输出:1 2 3
list.reverse();
list.traverse(); // 输出:3 2 1
return 0;
}
```
在这个程序中,我们实现了单链表的基本操作以及链表的逆置。运行`main()`函数会显示原始链表和逆置后的链表。
阅读全文