3.数列有序!
| 数列有序! Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 194132 Accepted Submission(s): 78855 Problem Description 有n(n<=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请将该数插入到序列中，并使新的序列仍然有序。 Input 输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。 Output 对于每个测试实例，输出插入新的元素后的数列。 Sample Input 3 3 1 2 4 0 0 Sample Output 1 2 3 4 Author lcy Source C语言程序设计练习（三） |
#include <iostream>
#include <stdexcept>
#define eleType long long
using namespace std;
struct ListNode {
eleType data;
ListNode* next;
ListNode(eleType x) :data(x), next(nullptr) {}
};
class LinkedList {
private:
ListNode* head;
int size;
public:
LinkedList() :head(nullptr), size(0) {}
~LinkedList();
void insert(int index, eleType value);
void remove(int index);
ListNode* find(eleType value);
ListNode* get(int index);
void update(int index, eleType value);
void print();
void append(eleType value);
void ascInsert(eleType value);
};
LinkedList::~LinkedList() {
ListNode* curr = head;
while (curr) {
ListNode* temp = curr;
curr = curr->next;
delete temp;
}
}
void LinkedList::insert(int index, eleType value) {
if (index<0 || index>size) {
throw std::out_of_range(“invalid position”);
}
ListNode* newNode = new ListNode(value);
if (index == 0) {
newNode->next = head;
head = newNode;
}
else {
ListNode* curr = head;
for (int j = 0; j < index – 1; j++) {
curr = curr->next;
}
newNode->next = curr->next;
curr->next = newNode;
}
size++;
}
void LinkedList::remove(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range(“invalid position”);
}
if (index == 0) {
ListNode* temp = head;
head = temp->next;
delete temp;
}
else {
ListNode* curr = head;
for (int j = 0; j < index – 1; j++) {
curr = curr->next;
}
ListNode* temp = curr->next;
curr->next = temp->next;
delete temp;
}
size–;
}
ListNode* LinkedList::find(eleType value) {
ListNode* curr = head;
while (curr != nullptr && curr->data != value) {
curr = curr->next;
}
return curr;
}
ListNode* LinkedList::get(int index) {
if (index < 0 || index >= size) {
throw std::out_of_range(“invalid position”);
}
ListNode* curr = head;
for (int j = 0; j < index; j++) {
curr = curr->next;
}
return curr;
}
void LinkedList::update(int index, eleType value) {
if (index < 0 || index >= size) {
throw std::out_of_range(“invalid position”);
}
get(index)->data = value;
}
void LinkedList::print() {
ListNode* curr = head;
while (curr) {
cout << curr->data;
curr = curr->next;
if (curr) {
cout << ” “;
}
else {
cout << endl;
}//如果后面还有值就打印空格 不然就打印换行
}
}
void LinkedList::append(eleType value) {
insert(size, value);
}
void LinkedList::ascInsert(eleType value) {
if (size == 0) {
insert(0, value);
return ;
}
ListNode* curr = head;
for (int i = 0; i < size; i++) {
if (value <= curr->data) {
insert(i, value);
return ;
}
curr = curr->next;
}
insert(size, value); //没有找到比它小的
}
int main() {
int n, x;
while (cin >> n >> x) {
if (!n && !x) {
break;
}
LinkedList l;
while (n–) {
int v;
cin >> v;
l.append(v);
}
l.ascInsert(x);
l.print();
}
return 0;
}