编程实现,带头结点的单链表各种操作:查找、删除、插入等 要求:1.在程序的关键位置加注释,说明函数或语句的功能; 2.将程序和运行结果拍照;
时间: 2024-09-22 12:07:00 浏览: 65
C语言实现带头结点的链表的创建、查找、插入、删除操作
在编程中,带头节点的单链表是一种常见的数据结构,下面是其基本操作的C++示例:
```cpp
#include <iostream>
// 定义链表节点结构体
struct ListNode {
int val; // 节点值
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 构造函数
};
// 查找节点的操作 (线性搜索)
ListNode* search(ListNode* head, int target) {
// 添加注释:遍历链表直到找到目标值或到达末尾
ListNode* curr = head;
while (curr != NULL && curr->val != target) { // 如果当前节点非空且值不等于目标
curr = curr->next; // 移动到下一个节点
}
return curr; // 返回目标节点,如果未找到返回NULL
}
// 插入节点的操作
void insertNode(ListNode* &head, int val, int position = 0) {
// 添加注释:若position为0,在头部插入;否则遍历链表找到相应位置
if (position == 0) {
ListNode* newNode = new ListNode(val);
newNode->next = head;
head = newNode;
} else {
ListNode* curr = head;
for (int i = 0; i < position - 1 && curr != NULL; ++i) {
curr = curr->next;
}
if (curr != NULL) { // 如果找到了位置
ListNode* newNode = new ListNode(val);
newNode->next = curr->next;
curr->next = newNode;
}
}
}
// 删除节点的操作
void deleteNode(ListNode*& head, int target) {
// 添加注释:遍历链表查找目标节点,如果找到则删除它并调整链表
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr && curr->val != target) {
prev = curr;
curr = curr->next;
}
if (curr != nullptr) { // 找到了目标
if (prev == nullptr) { // 目标在头节点
head = curr->next;
} else {
prev->next = curr->next;
}
delete curr; // 释放内存
}
}
// 打印链表辅助函数
void printList(ListNode* head) {
ListNode* temp = head;
while (temp != NULL) {
std::cout << temp->val << " ";
temp = temp->next;
}
std::cout << "\n";
}
int main() {
// 创建链表并添加节点...
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
// 运行操作,例如查找、插入和删除,并打印链表
ListNode* foundNode = search(head, 2); // 查找节点2
if (foundNode) {
std::cout << "Found node at position " << findPosition(foundNode) << "\n";
}
insertNode(head, 4, 1); // 在第1个位置插入值4
deleteNode(head, 2); // 删除节点2
printList(head); // 输出修改后的链表
return 0;
}
```
注意:实际项目中,你需要实现`findPosition()`函数来获取节点在链表中的位置,这里为了简洁省略了。运行此代码后,你可以查看链表的操作效果以及相应的输出结果。
阅读全文