编写一个C语言程序,以单链表的首结点值x为基准,将该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前。
时间: 2024-09-28 07:12:42 浏览: 38
在C语言中,你可以通过遍历链表并创建两个新的链表头节点来实现这个功能。首先,你需要创建一个新的链表来存储小于x的元素,另一个链表则用于存储大于或等于x的元素。下面是一个简单的步骤描述:
1. 定义结构体`Node`表示链表节点,包含数据`data`和指向下一个节点的指针`next`。
```c
typedef struct Node {
int data;
struct Node* next;
} Node;
```
2. 创建函数`splitList`,接受链表头节点`head`和基准值`x`作为输入。
```c
Node* splitList(Node* head, int x) {
// 初始化两个空链表头节点
Node* smallerHead = NULL;
Node* largerHead = NULL;
// 当链表非空时
while (head != NULL) {
// 检查当前节点的数据
if (head->data < x) {
// 如果小于x,添加到较小链表
if (smallerHead == NULL) {
smallerHead = head;
} else {
smallerHead->next = head;
}
head = head->next;
} else {
// 否则,添加到较大链表
if (largerHead == NULL) {
largerHead = head;
} else {
largerHead->next = head;
}
head = head->next;
}
}
return largerHead; // 返回较大的链表的新头节点
}
```
3. 调用`splitList`函数,并处理返回结果。
```c
int main() {
// 初始化和构建单链表...
Node* list = createLinkedList(); // 假设createLinkedList()函数返回链表头节点
// 获取基准值x
int x = ...;
// 分割链表
Node* result = splitList(list, x);
// 打印新链表
printList(result); // 假设printList()函数用于打印链表
return 0;
}
```
注意,这只是一个基本的示例,实际应用中需要考虑链表是否为空以及边界情况。同时,链表的创建和操作依赖于你自己定义的链表相关函数,例如`createLinkedList()`、`printList()`等。
阅读全文