1.构造一个空的单链表L。 2.在单链表L的第i个元素之后插入新的元素e。 3.在单链表L中删除第i个元素,并用e返回其值。 写好这3个函数,并在main函数中调用这3个函数,显示结果
时间: 2024-09-24 10:06:06 浏览: 40
在C++中,我们可以创建一个简单的单链表节点结构并实现上述三个功能。这里我会提供一个基础的实现:
```cpp
#include <iostream>
// 定义单链表节点结构
struct ListNode {
int data;
ListNode* next;
ListNode(int val) : data(val), next(nullptr) {}
};
// 1. 构造一个空的单链表L
ListNode* createEmptyList() {
return nullptr;
}
// 2. 在单链表L的第i个元素之后插入新的元素e
void insertAfter(ListNode*& L, int i, int e) {
if (i <= 0 || L == nullptr) {
std::cout << "Invalid index\n";
return;
}
ListNode* new_node = new ListNode(e);
ListNode* current = L;
for (int j = 0; j < i - 1 && current != nullptr; ++j) {
current = current->next;
}
if (current == nullptr) {
std::cout << "Index out of bounds, list is empty\n";
delete new_node;
return;
}
new_node->next = current->next;
current->next = new_node;
}
// 3. 在单链表L中删除第i个元素,并用e返回其值
int deleteAndReturn(ListNode*& L, int i) {
if (L == nullptr || i <= 0) {
std::cout << "Invalid index or empty list\n";
return 0;
}
ListNode* prev = nullptr;
ListNode* current = L;
for (int j = 0; j < i - 1 && current != nullptr; ++j) {
prev = current;
current = current->next;
}
if (current == nullptr) {
std::cout << "Index out of bounds\n";
return 0;
}
int value_to_return = current->data;
prev->next = current->next;
delete current;
return value_to_return;
}
// 主函数用于测试上述操作
int main() {
// 创建一个空链表
ListNode* L = createEmptyList();
// 插入元素
insertAfter(L, 0, 5); // 在头节点后插入5
insertAfter(L, 1, 10); // 在第二个节点后插入10
// 删除元素并打印删除前后的值
int removed_value = deleteAndReturn(L, 0); // 删除第一个节点,返回5
std::cout << "Removed element: " << removed_value << "\n";
// 遍历链表并展示结果
ListNode* temp = L;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << "\n";
// 清理内存
delete L;
return 0;
}
```
这个程序首先创建了一个空链表,然后在指定位置插入新元素,接着删除指定位置的元素并返回它的值,最后遍历链表显示结果。注意,在实际应用中,你需要处理更复杂的情况,例如链表可能会有循环等。
阅读全文