用C++程序编写:使用单链表表示有序表,并进行操作: 1、从键盘输入一组整数,建立第一个有序单链表并输出 2、从键盘输入一组整数,建立第二个有序单链表并输出 3、将两个有序表合并,输出结果 4、输出合并后有序表的中位数
时间: 2024-09-13 21:09:54 浏览: 56
在C++中,我们可以使用结构体定义链表节点,并结合`std::vector`或自定义双向链表来实现有序列表。以下是关于操作的简要步骤:
1. **创建单链表**:
- 定义`Node`结构体,包含整数值和指向下一个节点的指针。
- 使用`std::vector`存储有序整数,每个元素都是一个`Node`的引用。
```cpp
struct Node {
int value;
Node* next;
};
std::vector<Node*> buildList(int input[], size_t size) {
std::vector<Node*> list;
for (size_t i = 0; i < size; ++i) {
Node* newNode = new Node{input[i], nullptr};
if (list.empty() || input[i] <= list.back()->value) {
list.push_back(newNode);
} else {
for (Node* it = list.begin(); it != list.end(); ++it) {
if (input[i] > it->value) {
it->next = newNode;
break;
}
}
}
}
return list;
}
```
2. **输入并输出有序链表**:
- 使用类似上面的函数,分别处理两次输入的数据。
3. **合并两个有序链表**:
- 创建一个新链表,遍历两个输入链表,每次取较小值添加到新链表。
```cpp
Node* mergeLists(Node* head1, Node* head2) {
Node* result = nullptr;
if (head1 && head2) {
if (head1->value <= head2->value) {
result = head1;
result->next = mergeLists(head1->next, head2);
} else {
result = head2;
result->next = mergeLists(head1, head2->next);
}
} else if (head1) {
result = head1;
} else {
result = head2;
}
return result;
}
```
4. **计算中位数**:
- 合并后的链表已经排序,对于长度为奇数的情况,中位数即为中间元素;长度为偶数时,中位数为中间两个元素的平均值。这里需要遍历链表找到对应的索引位置。
```cpp
double findMedian(Node* mergedHead) {
size_t length = 0;
for (Node* node = mergedHead; node; node = node->next) {
++length;
}
if (length % 2 == 0) {
Node* middle1 = findMiddle(mergedHead, length / 2);
Node* middle2 = findMiddle(middle1->next, length / 2 - 1);
return (middle1->value + middle2->value) / 2.0;
} else {
return mergedHead->value;
}
}
Node* findMiddle(Node* head, size_t index) {
size_t count = 0;
for (Node* node = head; node; node = node->next) {
++count;
if (count == index + 1) {
return node;
}
}
return nullptr;
}
```
完成以上代码后,你可以调用相应的函数来进行所需的操作,并打印出结果。请注意,这只是一个简化示例,实际编程时可能需要考虑更多的边界条件和内存管理。
阅读全文