编写一个程序exp2-3.cpp,以单链表的首结点值x为基准将该单链表分割为两部分,使所有小于x的结点排在大于或等于x的结点之前。
时间: 2024-10-16 21:04:42 浏览: 67
在编写这个名为 `exp2-3.cpp` 的程序时,我们将使用 C++ 来实现单链表的分割功能。首先,我们需要定义一个单链表节点结构,并提供一些基本操作,如插入节点、查找节点以及遍历链表。然后,我们将找到链表中的第一个值 x,根据此值将链表分为两个部分。
这里是一个简单的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
// 插入节点到链表
ListNode* insertNode(ListNode* head, int val) {
ListNode* newNode = new ListNode(val);
if (!head) {
head = newNode;
} else {
ListNode* temp = head;
while (temp->next != nullptr && temp->next->val < val) {
temp = temp->next;
}
newNode->next = temp->next;
temp->next = newNode;
}
return head;
}
// 找到链表的第一个值 x
int findVal(ListNode* head) {
while (head) {
if (head->val >= 0) {
return head->val;
}
head = head->next;
}
return -1; // 如果链表全是负数,则返回默认值
}
// 主函数,分割链表并打印结果
void splitList(ListNode* head) {
int x = findVal(head);
if (x == -1) {
cout << "No positive value found in the list.\n";
return;
}
ListNode* smallerHead = head;
ListNode* largerHead = nullptr;
ListNode* temp = head;
while (temp) {
if (temp->val < x) {
smallerHead = insertNode(smallerHead, temp->val);
} else {
largerHead = insertNode(largerHead, temp->val);
}
temp = temp->next;
}
cout << "Smaller half of the list: ";
printList(smallerHead); // 自定义打印链表函数
cout << "\nLarger half of the list: ";
printList(largerHead);
}
// 辅助函数,打印链表
void printList(ListNode* head) {
while (head) {
cout << head->val << " -> ";
head = head->next;
}
cout << "nullptr" << endl;
}
// 示例链表构造函数
ListNode* createExampleList() {
// 创建一个链表示例,例如 4 -> 3 -> -2 -> 6 -> 5 -> -7
ListNode* list = nullptr;
list = insertNode(list, 4);
list = insertNode(list, 3);
list = insertNode(list, -2);
list = insertNode(list, 6);
list = insertNode(list, 5);
list = insertNode(list, -7);
return list;
}
int main() {
ListNode* head = createExampleList();
splitList(head);
return 0;
}
```
在这个代码中,我们首先创建了一个链表并初始化了一些值。然后在 `splitList` 函数中,我们找到基准值 x,根据这个值将链表分成两半。注意,这个例子假设输入的链表包含正数和负数,如果链表只包含负数,`findVal` 函数会返回 `-1`。
运行这个程序,它会根据提供的链表分割并分别打印出小于基准值的部分和大于等于基准值的部分。
阅读全文
相关推荐
![zip](https://img-home.csdnimg.cn/images/20241231045053.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)