用C语言编写一个程序,实现以单链表的首结点值x为基准值将该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前。
时间: 2024-10-08 19:26:22 浏览: 53
在C语言中,我们可以使用指针来操作链表结构,并通过遍历链表来实现这个功能。以下是一个简单的示例程序,它定义了一个链表节点结构体以及两个辅助函数:`insert_sorted`用于插入新元素到已排序的部分,`split_list`用于分割链表:
```c
#include <stdio.h>
#include <stdlib.h>
// 链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 插入节点并保持链表有序
Node* insert_sorted(Node* head, int data) {
if (head == NULL || data <= head->data) {
return (Node*) malloc(sizeof(Node));
}
Node* newNode = (Node*) malloc(sizeof(Node));
newNode->data = data;
newNode->next = head;
head = newNode;
while (head->next != NULL && head->next->data < data) {
head = head->next;
}
return head;
}
// 分割链表函数
void split_list(Node** head_ref, int x) {
Node* less_than_x = NULL;
Node* equal_or_greater_than_x = NULL;
*head_ref = insert_sorted(NULL, x); // 将x作为头节点,使其位于正确位置
while (*head_ref != NULL) {
if (*head_ref->data < x) {
less_than_x = insert_sorted(less_than_x, *head_ref->data);
} else {
equal_or_greater_than_x = insert_sorted(equal_or_greater_than_x, *head_ref->data);
}
*head_ref = (*head_ref)->next;
}
// 连接两部分链表
less_than_x->next = equal_or_greater_than_x;
}
int main() {
// 初始化链表(这里仅做演示,实际应用中需要添加自己的数据)
Node* list = create_linked_list(); // 假设有一个create_linked_list函数创建链表
int x = 5; // 基准值
split_list(&list, x);
// 打印分割后的链表
print_list(less_than_x); // 输出小于x的链表
print_list(equal_or_greater_than_x); // 输出等于或大于x的链表
return 0;
}
阅读全文