c语言设计一个算法,删除递增有序链表中值大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数,其值可以和表中的元素相同,也可以不同)。构造测试用例进行测试。(教材P51习题2.8)
时间: 2024-10-09 17:08:29 浏览: 70
递增有序的单链表中删除值介于MINK和MAXK之间的.cpp
为了在C语言中设计一个算法删除递增有序链表中值大于`minK`且小于`maxK`的所有元素,我们可以采用迭代的方式来遍历链表。这里是一个基本的步骤描述:
1. 定义结构体`ListNode`表示链表节点,包含数据`val`和指向下一个节点的指针`next`。
```c
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
```
2. 创建一个函数`deleteInRange`,接受链表头节点`head`、最小值`minK`和最大值`maxK`作为输入参数。
```c
ListNode* deleteInRange(ListNode* head, int minK, int maxK) {
// 空链表或只有一个节点的情况
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* curr = head;
ListNode* prev = NULL;
// 遍历链表
while (curr != NULL) {
// 如果当前节点不在范围内,则更新prev和curr,然后移动到下一个节点
if (curr->val < minK || curr->val > maxK) {
if (prev != NULL) {
prev->next = curr->next;
} else {
head = curr->next; // 更新头节点
}
free(curr); // 释放已不需要的节点内存
curr = curr->next;
} else {
// 当前节点在范围内,将prev指向curr,继续遍历
prev = curr;
curr = curr->next;
}
}
return head;
}
```
接下来,我们需要编写一些测试用例来验证这个功能:
```c
// 测试用例
int main() {
// 构建链表示例
ListNode* list1 = createLinkedList({1, 3, 4, 6, 7, 9}); // 示例链表,递增顺序
// 删除范围内的节点
list1 = deleteInRange(list1, 2, 6);
// 打印处理后的链表
printLinkedList(list1); // 输出:1, 3, 7, 9
// 清理内存
destroyLinkedList(list1);
return 0;
}
// 辅助函数:创建链表、打印链表和清理内存
ListNode* createLinkedList(int* arr) {
// 创建链表并添加元素...
}
void printLinkedList(ListNode* head) {
// 打印链表...
}
void destroyLinkedList(ListNode* head) {
// 清除链表内存...
}
```
阅读全文