用C++编写:使用单链表表示有序表,并进行操作: 1、从键盘输入一组整数,建立第一个有序单链表并输出 2、从键盘输入一组整数,建立第二个有序单链表并输出 3、将两个有序表合并,输出结果 4、输出合并后有序表的中位数
时间: 2024-09-13 21:09:34 浏览: 51
在C++中,我们可以使用`std::list`结构来创建单链表,它本身就支持自动排序插入元素,因此可以轻松地实现这个功能。以下是简单的步骤:
1. 定义节点类`ListNode`,包含数据成员值`int data`和指向下一个节点的指针`std::list<int>::iterator next`。
```cpp
#include <iostream>
#include <list>
struct ListNode {
int data;
std::list<int>::iterator next;
};
```
2. 创建函数来构建有序链表,例如从键盘输入整数添加到链表中。
```cpp
void buildList(std::list<int>& list) {
int num;
while (std::cin >> num) {
list.push_back(num);
}
}
```
3. 分别创建两个链表,并输出它们。
```cpp
void printList(const std::list<int>& list) {
for (const auto& item : list) {
std::cout << item << " ";
}
std::cout << "\n";
}
// 创建两个链表
std::list<int> list1, list2;
buildList(list1);
printList(list1); // 输出 list1 的内容
buildList(list2);
printList(list2); // 输出 list2 的内容
```
4. 合并两个已排序的链表,可以先遍历每个链表,每次取较大的值放到新的合并链表中。
```cpp
ListNode* mergeSortedLists(ListNode* head1, ListNode* head2) {
ListNode dummy(0), *current = &dummy;
while (head1 && head2) {
if (*head1 <= *head2) {
current->next = head1;
head1 = head1->next;
} else {
current->next = head2;
head2 = head2->next;
}
current = current->next;
}
current->next = (head1 ? head1 : head2);
return dummy.next;
}
// 合并 list1 和 list2
ListNode* mergedList = mergeSortedLists(list1.begin(), list2.begin());
printList(mergedList); // 输出合并后的链表
```
5. 要找到合并后链表的中位数,如果链表长度是奇数,则直接返回中间元素;如果是偶数,需要找到中间两个元素,然后取平均值。
```cpp
double findMedian(std::list<int>::iterator begin, std::list<int>::iterator end) {
int len = std::distance(begin, end);
if (len % 2 == 0) { // 偶数个元素
const auto mid = begin + len / 2;
return static_cast<double>(*mid + *(mid - 1)) / 2;
} else { // 奇数个元素
return static_cast<double>(*begin + *(begin + len / 2 - 1)) / 2;
}
}
// 计算并输出中位数
double median = findMedian(mergedList, mergedList.end());
std::cout << "Median: " << median << "\n";
```
以上就是使用C++实现的有序链表操作示例。记得处理异常,比如用户输入非数字的情况。
阅读全文