单链表的基本操作,参考附件的代码,完成单链表的创建(尾插法和头插法)、输出链表、查找链表的第k个结点、在链表的第k个结点后插入新结点、在链表的第k个结点前插入新结点、删除链表的第k个结点等函数。查看各个运行结果图
时间: 2024-11-20 15:35:15 浏览: 1
test3-插入.rar_尾插法_有头插法_链表 插入创建
单链表是一种基础的数据结构,它的节点由数据域和指向下一个节点的指针组成,但没有双向链接。以下是单链表的一些基本操作:
1. **创建链表** (尾插法 - 遇到尾节点时插入):
- 定义一个`Node`结构体,包含`data`和`next`两个字段。
- 尾插法函数`add_to_tail`:
```cpp
void add_to_tail(Node* &head, int data) {
if (!head) {
head = new Node{data};
} else {
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = new Node{data};
}
}
```
2. **创建链表** (头插法 - 插入在头部):
- `add_to_head`函数:
```cpp
void add_to_head(Node* &head, int data) {
Node* newNode = new Node{data};
newNode->next = head;
head = newNode;
}
```
3. **输出链表**:
- 使用迭代或递归遍历链表,打印每个节点数据。
4. **查找第k个节点**:
- `find_kth_node` 函数:
```cpp
Node* find_kth_node(Node* head, int k) {
if (!head || k <= 0) return nullptr;
for (int i = 1; i < k && head; ++i) {
head = head->next;
}
return head;
}
```
5. **在第k个节点后插入**:
- `insert_after_kth` 函数:
```cpp
void insert_after_kth(Node* &head, Node* kthNode, int data) {
if (!kthNode) return;
Node* newNode = new Node{data};
newNode->next = kthNode->next;
kthNode->next = newNode;
}
```
6. **在第k个节点前插入**:
- 类似于插入后,只需调整插入位置即可:
```cpp
void insert_before_kth(Node* &head, Node* kthNode, int data) {
if (!kthNode || !head) return;
Node* newNode = new Node{data};
newNode->next = head;
if (kthNode == head) {
newNode->next = kthNode->next;
} else {
Node* prevKth = nullptr;
while (prevKth != kthNode) {
prevKth = kthNode;
kthNode = kthNode->next;
}
prevKth->next = newNode;
}
}
```
7. **删除第k个节点**:
- `delete_kth_node` 函数:
```cpp
void delete_kth_node(Node* &head, int k) {
if (!head || k <= 0) return;
if (k == 1) {
Node *temp = head;
head = head->next;
delete temp;
return;
}
Node* prevKth = nullptr;
for (int i = 1; i < k && head; ++i) {
prevKth = head;
head = head->next;
}
if (!prevKth) return;
prevKth->next = head->next;
delete head;
}
```
每完成一个操作后,你可以通过遍历并打印链表验证其正确性,同时也需要处理边界情况。在实际应用中,记得处理`nullptr`指针异常以及无效的`k`值。
阅读全文