C++设计程序从键盘中输入5个无序的整数,插入到顺序表和单链表中,并保证插入后顺序表和单链表中的数据要从小到大进行排序。
时间: 2024-10-20 22:13:13 浏览: 12
C++ STL 和 泛型编程1
在C++中,你可以通过以下步骤设计这样的程序:
1. 定义数据结构:首先,你需要创建两个数据结构,一个是顺序表(如数组或动态数组),另一个是单链表。对于顺序表,可以使用`std::vector<int>`;对于单链表,可以使用`struct ListNode`表示节点,包含一个整数值和指向下一个节点的指针。
```cpp
#include <iostream>
#include <vector>
// 单链表节点定义
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
```
2. 输入5个无序整数:使用`cin`从用户那里获取5个整数。
```cpp
std::vector<int> seqList;
ListNode* head = nullptr;
for (int i = 0; i < 5; ++i) {
int input;
std::cout << "请输入第" << i + 1 << "个整数: ";
cin >> input;
seqList.push_back(input); // 顺序表
insertToLinkedList(input, head); // 将输入添加到链表
}
```
3. 插入并排序:对于顺序表,可以直接插入并保持递增顺序。对于单链表,可以在`insertToLinkedList`函数中先插入然后对链表进行排序(例如使用冒泡排序或者插入排序)。
```cpp
void insertToLinkedList(int num, ListNode*& head) {
ListNode* newNode = new ListNode(num);
if (!head) {
head = newNode;
} else {
ListNode* current = head;
while (current->next && current->next->val < num) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
// 对链表进行排序(这里仅示例冒泡排序)
void sortLinkedList(ListNode* &head) {
if (head == nullptr || head->next == nullptr) return;
ListNode* end = nullptr;
for (auto iter = head; iter != end; ) {
if (iter->val > iter->next->val) {
std::swap(iter->val, iter->next->val);
}
end = iter;
if (end->next != nullptr) iter = end->next;
else break;
}
}
```
4. 输出结果:最后,遍历并打印顺序表和链表的内容,展示它们已经按升序排列。
```cpp
// 打印顺序表
std::cout << "顺序表排序后的元素: ";
for (const auto& num : seqList) {
std::cout << num << " ";
}
// 打印链表
std::cout << "\n链表排序后的元素: ";
while (head) {
std::cout << head->val << " ";
head = head->next;
}
```
阅读全文