用C语言写一个完整的代码(5)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C,其中B表的结点为A表中值小于零的结点,而C表的结点为A表中值大于零的结点(链表A中的元素为非零整数,要求B、C表利用A表的结点)。
时间: 2024-10-15 19:29:20 浏览: 23
试写出一个计算单链表中结点个数的算法,其中指针p指向该链表的第一个结点。
在C语言中,你可以使用迭代的方式来实现这个链表拆分的问题。这里是一个简单的示例,我们将创建三个节点结构体`Node`,并维护两个指针`pB`和`pC`分别指向B链表和C链表的头部。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
typedef struct Node {
int value;
struct Node* next;
} Node;
// 创建新节点
Node* createNode(int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->next = NULL;
return newNode;
}
// 分解链表
void splitList(Node* head, Node** pB, Node** pC) {
Node* current = head;
Node* prevB = NULL;
Node* prevC = NULL;
while (current != NULL) {
if (current->value < 0) { // 将负数节点添加到B链表
if (prevB == NULL) {
*pB = current;
} else {
prevB->next = current;
}
prevB = current;
} else { // 否则添加到C链表
if (prevC == NULL) {
*pC = current;
} else {
prevC->next = current;
}
prevC = current;
}
current = current->next;
}
// 连接剩余部分,如果B链表最后一个是正数,则连接到C链表
if (prevB && prevB->value >= 0) {
prevC->next = prevB;
} else if (prevC == NULL) {
*pB = prevB; // 如果C链表为空,B链表作为结果返回
}
}
int main() {
// 初始化链表A...
Node* head = createNode(1);
head->next = createNode(-2); // 示例数据
head->next->next = createNode(3);
Node* B_head = NULL;
Node* C_head = NULL;
splitList(head, &B_head, &C_head);
printf("B链表: ");
while (B_head != NULL) {
printf("%d -> ", B_head->value);
B_head = B_head->next;
}
printf("\n");
printf("C链表: ");
while (C_head != NULL) {
printf("%d -> ", C_head->value);
C_head = C_head->next;
}
printf("\n");
return 0;
}
```
阅读全文