编写一个完整的C语言程序,以单链表的首结点值x为基准,将该单链表分为两部分,使所有小于x的结点排在大于或等于x的结点之前。
时间: 2024-09-28 07:05:19 浏览: 45
下面是一个完整的C语言程序,它使用单链表的头结点值作为基准,将链表分为两部分:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 插入节点到链表
void insert(Node** head, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = *head;
*head = newNode;
}
// 分割链表
void splitList(Node** head, Node** smallHead, Node** largeHead) {
Node* current = *head;
Node* smallerHead = *smallHead;
Node* largerHead = *largeHead;
while (current != NULL) {
if (current->data < (*smallHead)->data || *smallHead == NULL) { // 如果当前节点小于基准或链表为空
insert(smallHead, current->data);
} else {
insert(largeHead, current->data);
}
current = current->next;
}
}
// 打印链表
void printList(Node* head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
int main() {
Node* head = NULL;
// 初始化链表...例如添加一些节点
insert(&head, 5);
insert(&head, 3);
insert(&head, 8);
insert(&head, 2);
insert(&head, 10);
Node* smallHead = NULL;
Node* largeHead = NULL;
splitList(&head, &smallHead, &largeHead);
printf("Small list (values < x): ");
printList(smallHead);
printf("\nLarge list (values >= x): ");
printList(largeHead);
// 清理内存
free(head);
free(smallHead);
free(largeHead);
return 0;
}
```
这个程序首先初始化了一个链表,然后通过`splitList`函数分割链表。`splitList`函数遍历链表,将每个节点根据其值与基准进行比较,然后插入到对应的链表中。最后,分别打印出小于基准的链表(`smallHead`)和大于等于基准的链表(`largeHead`)。记得在主函数结束时释放所有的动态内存。如果你想要使用特定的值作为基准,只需在`main`函数中更改`insert`调用即可。
阅读全文