于是,在本题中,你需要实现一个单链表 ,支持以下操作: 在单链表第 i 个数后面插入一个数 x 删除单链表第 i 个数 将单链表的奇偶位相互交换,若单链表长度为奇数,则剩下的最后一个元素无需交换。 将单链表前 i 个数整体往后移动 x 位。输出单链表第 i 个数 输出整个单链表,使用空格隔开 另外,在程序开始时,请先读入一个大小为n 的数组对单链表进行初始化。 请通过动态申请空间的方式完成单链表。在程序结束后,你应当释放所有动态申请的内存,使用C++语言,并使用下面的模版
时间: 2024-03-08 18:49:20 浏览: 44
用C++实现一个单链表
好的,我已经理解了你的要求。以下是单链表的实现代码,你可以根据需要进行修改:
```c++
#include <iostream>
using namespace std;
// 定义单链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 初始化单链表
ListNode* initList(int n, int* arr) {
ListNode* head = new ListNode(-1);
ListNode* tail = head;
for (int i = 0; i < n; i++) {
ListNode* node = new ListNode(arr[i]);
tail->next = node;
tail = node;
}
return head->next;
}
// 在单链表第 i 个数后面插入一个数 x
ListNode* insert(ListNode* head, int i, int x) {
ListNode* p = head;
while (i > 1 && p != NULL) {
p = p->next;
i--;
}
if (p != NULL) {
ListNode* node = new ListNode(x);
node->next = p->next;
p->next = node;
}
return head;
}
// 删除单链表第 i 个数
ListNode* remove(ListNode* head, int i) {
ListNode* p = head;
while (i > 1 && p != NULL) {
p = p->next;
i--;
}
if (p != NULL && p->next != NULL) {
ListNode* q = p->next;
p->next = q->next;
delete q;
}
return head;
}
// 将单链表的奇偶位相互交换
ListNode* swap(ListNode* head) {
ListNode* odd = head;
ListNode* even = head->next;
ListNode* evenHead = even;
while (even != NULL && even->next != NULL) {
odd->next = even->next;
odd = odd->next;
even->next = odd->next;
even = even->next;
}
odd->next = evenHead;
return head;
}
// 将单链表前 i 个数整体往后移动 x 位
ListNode* move(ListNode* head, int i, int x) {
ListNode* p = head;
while (i > 1 && p != NULL) {
p = p->next;
i--;
}
if (p != NULL) {
ListNode* tail = p;
while (x > 0 && tail->next != NULL) {
tail = tail->next;
x--;
}
if (tail != p) {
ListNode* q = p->next;
p->next = tail->next;
tail->next = NULL;
tail = q;
while (tail != NULL && tail->next != NULL) {
tail = tail->next;
}
tail->next = q;
}
}
return head;
}
// 输出单链表第 i 个数
int get(ListNode* head, int i) {
ListNode* p = head;
while (i > 0 && p != NULL) {
p = p->next;
i--;
}
if (p != NULL) {
return p->val;
} else {
return -1;
}
}
// 输出整个单链表,使用空格隔开
void printList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
// 释放单链表内存
void freeList(ListNode* head) {
ListNode* p = head;
while (p != NULL) {
ListNode* q = p->next;
delete p;
p = q;
}
}
int main() {
int n, m;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
ListNode* head = initList(n, arr);
cin >> m;
for (int i = 0; i < m; i++) {
int op;
cin >> op;
switch (op) {
case 1: { // 在单链表第 i 个数后面插入一个数 x
int i, x;
cin >> i >> x;
head = insert(head, i, x);
break;
}
case 2: { // 删除单链表第 i 个数
int i;
cin >> i;
head = remove(head, i);
break;
}
case 3: { // 将单链表的奇偶位相互交换
head = swap(head);
break;
}
case 4: { // 将单链表前 i 个数整体往后移动 x 位
int i, x;
cin >> i >> x;
head = move(head, i, x);
break;
}
case 5: { // 输出单链表第 i 个数
int i;
cin >> i;
cout << get(head, i) << endl;
break;
}
case 6: { // 输出整个单链表,使用空格隔开
printList(head);
break;
}
}
}
freeList(head);
delete[] arr;
return 0;
}
```
注意,在使用完单链表后,需要调用 `freeList` 函数释放单链表的内存。
阅读全文