于是,在本题中,你需要实现一个单链表 ,支持以下操作: 1.在单链表第 i 个数后面插入一个数 x 2.删除单链表第 i 个数 3.将单链表的奇偶位相互交换,若单链表长度为奇数,则剩下的最后一个元素无需交换。 4.将单链表前 i 个数整体往后移动 x 位。 5.输出单链表第 i 个数 6.输出整个单链表,使用空格隔开 另外,在程序开始时,请先读入一个大小为n 的数组对单链表进行初始化。 请通过动态申请空间的方式完成单链表。在程序结束后,你应当释放所有动态申请的内存。用C++语言完成
时间: 2024-03-07 15:49:39 浏览: 64
以下是实现代码:
```c++
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
Node(int x) : val(x), next(nullptr) {}
};
class LinkedList {
private:
Node* head;
int size;
public:
LinkedList(int* arr, int n) {
head = new Node(-1);
Node* cur = head;
for (int i = 0; i < n; i++) {
cur->next = new Node(arr[i]);
cur = cur->next;
}
size = n;
}
~LinkedList() {
Node* cur = head;
while (cur != nullptr) {
Node* temp = cur->next;
delete cur;
cur = temp;
}
}
void insert(int i, int x) {
if (i < 0 || i > size) return;
Node* cur = head;
for (int j = 0; j < i; j++) {
cur = cur->next;
}
Node* temp = cur->next;
cur->next = new Node(x);
cur->next->next = temp;
size++;
}
void remove(int i) {
if (i < 0 || i >= size) return;
Node* cur = head;
for (int j = 0; j < i; j++) {
cur = cur->next;
}
Node* temp = cur->next;
cur->next = cur->next->next;
delete temp;
size--;
}
void swap() {
Node* cur = head->next;
while (cur != nullptr && cur->next != nullptr) {
int temp = cur->val;
cur->val = cur->next->val;
cur->next->val = temp;
cur = cur->next->next;
}
}
void move(int i, int x) {
if (i < 0 || i >= size) return;
Node* cur = head;
for (int j = 0; j < i; j++) {
cur = cur->next;
}
Node* tail = cur;
while (tail->next != nullptr) {
tail = tail->next;
}
for (int j = 0; j < x; j++) {
tail->next = cur->next;
cur->next = cur->next->next;
tail->next->next = nullptr;
tail = tail->next;
}
}
int get(int i) {
if (i < 0 || i >= size) return -1;
Node* cur = head->next;
for (int j = 0; j < i; j++) {
cur = cur->next;
}
return cur->val;
}
void print() {
Node* cur = head->next;
while (cur != nullptr) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
};
int main() {
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
LinkedList list(arr, n);
delete[] arr;
int q;
cin >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int i, x;
cin >> i >> x;
list.insert(i, x);
} else if (op == 2) {
int i;
cin >> i;
list.remove(i);
} else if (op == 3) {
list.swap();
} else if (op == 4) {
int i, x;
cin >> i >> x;
list.move(i, x);
} else if (op == 5) {
int i;
cin >> i;
cout << list.get(i) << endl;
} else if (op == 6) {
list.print();
}
}
return 0;
}
```
解释如下:
我们首先定义一个 Node 结构体来表示链表的一个节点,其中包含一个 val 域和一个指向下一个节点的指针 next。
然后定义一个 LinkedList 类,其中包含一个头指针 head 和一个表示链表长度的 size 变量。构造函数中,我们使用输入的数组 arr 来初始化链表,首先创建一个头结点,然后遍历数组,将每个元素插入到链表的末尾。析构函数中,我们需要释放链表中所有动态申请的内存。
接下来是题目中要求的六个操作:
1.在单链表第 i 个数后面插入一个数 x
我们首先需要判断插入位置是否合法,即 i 是否在 [0, size] 的范围内。然后遍历到第 i 个节点,将新节点插入到该节点后面即可。
2.删除单链表第 i 个数
同样需要判断删除位置是否合法,然后遍历到第 i 个节点,将该节点删除即可。
3.将单链表的奇偶位相互交换,若单链表长度为奇数,则剩下的最后一个元素无需交换。
我们从第二个节点开始遍历,每次交换当前节点和下一个节点的值即可。
4.将单链表前 i 个数整体往后移动 x 位。
我们首先需要判断移动位置是否合法,然后遍历到第 i 个节点,将第 i+1 个节点作为移动后的头结点,然后遍历到链表末尾,将末尾节点的 next 指针指向原先的头结点,重复这个过程 x 次即可。
5.输出单链表第 i 个数
我们首先需要判断输出位置是否合法,然后遍历到第 i 个节点,返回该节点的值即可。
6.输出整个单链表,使用空格隔开
直接遍历链表,输出每个节点的值即可。
最后,我们读入输入数据,依次执行各个操作即可。
阅读全文