1.先类型声明和定义头结点,建立一个空的单链表L; 2.在单链表L的第i个元素之后插入新的元素e; 3.在单链表L中删除第i个元素,并用e返回其值。
时间: 2024-12-06 19:22:07 浏览: 27
首先,在程序中,我们通常会创建一个结构体或类来表示链表节点,包含数据域和指向下一个节点的指针。对于头结点的声明和定义,我们可以这样写:
```c++
// 假设Node是一个链表节点,包含数据和next指针
typedef struct Node {
int data;
Node* next;
} ListNode;
// 创建一个空链表
ListNode* createEmptyList() {
return nullptr; // 或者你可以初始化一个指向null的指针
}
```
接下来,我们要在单链表的第i个位置插入新元素e,这需要遍历链表找到第i-1个节点,然后将新元素插入到其后面:
```c++
void insertAfter(int i, int e, ListNode* L) {
if (i <= 0 || L == nullptr) return; // 验证索引是否合法
ListNode* current = L;
for (int j = 0; j < i - 1 && current != nullptr; j++) {
current = current->next;
}
if (current == nullptr) {
printf("Index out of range.\n");
return;
}
ListNode* newNode = new ListNode{e, current->next};
current->next = newNode;
}
```
最后,删除第i个元素并返回其值需要先定位到该节点,然后更新前一个节点的next指针,如果i为1,则直接修改头指针,同时处理边界条件:
```c++
int removeAndReturn(int i, ListNode* L) {
if (i <= 0 || L == nullptr) return -1; // 如果链表为空或索引错误,返回-1作为标记
if (i == 1) {
ListNode* temp = L;
L = L->next;
delete temp;
return temp ? temp->data : -1; // 返回删除元素的值,若链表变为nullptr,说明删除的是头元素
} else {
ListNode* previous = L;
for (int j = 0; j < i - 1 && previous->next != nullptr; j++) {
previous = previous->next;
}
if (previous->next == nullptr) {
printf("Index out of range.\n");
return -1;
}
int value = previous->next->data;
ListNode* toDelete = previous->next;
previous->next = previous->next->next;
delete toDelete;
return value; // 返回删除的值
}
}
```
阅读全文