用c++实现:输入一个正整数 repeat (0<repeat<10),做 repeat 次下列运算: 输入一个正整数 n(0<n<=9)和一组(n个)升序的整数,建立单向链表,再输入一个整数 x,把 x 插入到这组数据中,使该组数据仍然有序。
时间: 2023-06-18 16:02:05 浏览: 126
以下是使用C++实现的代码:
```cpp
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* insert(ListNode* head, int x) {
ListNode* node = new ListNode(x);
if (!head || x < head->val) {
node->next = head;
return node;
}
ListNode* curr = head;
while (curr->next && curr->next->val < x) {
curr = curr->next;
}
node->next = curr->next;
curr->next = node;
return head;
}
ListNode* createList(int n) {
ListNode* dummy = new ListNode(-1);
ListNode* curr = dummy;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
curr->next = new ListNode(x);
curr = curr->next;
}
return dummy->next;
}
void printList(ListNode* head) {
ListNode* curr = head;
while (curr) {
cout << curr->val << " ";
curr = curr->next;
}
cout << endl;
}
int main() {
int repeat;
cin >> repeat;
while (repeat--) {
int n, x;
cin >> n;
ListNode* head = createList(n);
cin >> x;
head = insert(head, x);
printList(head);
}
return 0;
}
```
首先定义了链表节点 `ListNode`,包含一个整数值 `val` 和指向下一个节点的指针 `next`。在 `insert` 函数中,首先创建一个新节点,然后遍历链表找到插入位置,最后插入新节点。在 `createList` 函数中,根据输入的升序整数序列创建链表。在主函数中,根据输入的 `repeat` 参数,循环执行多次插入操作,每次创建链表并插入一个新节点,最后输出插入后的链表。
阅读全文