请根据上面的框架完成一个单链表 ,支持以下操作: 1.在单链表第 i 个数后面插入一个数 x 2.删除单链表第 i 个数 3.将单链表的奇偶位相互交换,若单链表长度为奇数,则剩下的最后一个元素无需交换。 4.将单链表前 i 个数整体往后移动 x 位。 5.输出单链表第 i 个数 6.输出整个单链表,使用空格隔开 另外,在程序开始时,请先读入一个大小为n 的数组对单链表进行初始化。 请通过动态申请空间的方式完成单链表。在程序结束后,你应当释放所有动态申请的内存。用C++语言完成
时间: 2024-03-07 13:49:47 浏览: 76
链表的基本操作:插入、删除、查找。c++语言实现
4星 · 用户满意度95%
好的,以下是我为你完成的代码,希望能够帮到你:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
class LinkedList {
public:
LinkedList(int* a, int n) {
head = new ListNode(-1);
ListNode* p = head;
for (int i = 0; i < n; i++) {
p->next = new ListNode(a[i]);
p = p->next;
}
}
void insert(int i, int x) {
ListNode* p = head;
for (int j = 0; j < i; j++) {
p = p->next;
}
ListNode* new_node = new ListNode(x);
new_node->next = p->next;
p->next = new_node;
}
void erase(int i) {
ListNode* p = head;
for (int j = 0; j < i; j++) {
p = p->next;
}
ListNode* del_node = p->next;
p->next = del_node->next;
delete del_node;
}
void swap() {
ListNode* p = head;
while (p->next != NULL && p->next->next != NULL) {
ListNode* node1 = p->next;
ListNode* node2 = node1->next;
ListNode* next_node = node2->next;
node2->next = node1;
node1->next = next_node;
p->next = node2;
p = node1;
}
}
void moveback(int i, int x) {
ListNode* p = head;
for (int j = 0; j < i - 1; j++) {
p = p->next;
}
ListNode* node1 = p->next;
ListNode* node2 = node1;
for (int j = 0; j < x && node2 != NULL; j++) {
node2 = node2->next;
}
if (node2 == NULL) {
return;
}
p->next = node2;
while (node2->next != NULL) {
node2 = node2->next;
}
node2->next = node1;
}
int query(int i) {
ListNode* p = head->next;
for (int j = 0; j < i - 1; j++) {
p = p->next;
}
return p->val;
}
void printAll() {
ListNode* p = head->next;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
~LinkedList() {
ListNode* p = head;
while (p != NULL) {
ListNode* del_node = p;
p = p->next;
delete del_node;
}
}
private:
ListNode* head;
};
int main() {
int n;
cin >> n;
int* a = new int[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
LinkedList List(a, n);
delete[] a;
int m, op, i, x;
cin >> m;
while (m--) {
cin >> op;
if (op == 1) {
cin >> i >> x;
List.insert(i, x);
}
else if (op == 2) {
cin >> i;
List.erase(i);
}
else if (op == 3) {
List.swap();
}
else if (op == 4) {
cin >> i >> x;
List.moveback(i, x);
}
else if (op == 5) {
cin >> i;
cout << List.query(i) << endl;
}
else if (op == 6) {
List.printAll();
}
}
return 0;
}
```
上述代码中,我们使用了一个 ListNode 结构体来表示链表中的每一个节点。在 LinkedList 类中,我们定义了链表的基本操作,包括插入、删除、交换、移动、查询、打印等。我们在类的构造函数中,根据给定的数组创建了一个单链表。在主函数中,我们先读入一个大小为 n 的数组,然后调用 LinkedList 的构造函数初始化单链表。接着,我们通过循环来读取用户输入的操作指令 op,并根据指令类型来调用对应的链表操作函数。最后,我们通过析构函数释放链表所占用的内存,程序结束。
希望这份代码能够满足你的需求,如有问题欢迎继续询问。
阅读全文