链表中元素已经按从小到大有序排放,编程将用户输入的数据元素插入到表中适当位置,并保持链表的有序性。步骤定义结构体,建链表输入需要插入的数据按值确定插入位置插入新元素,输出链表
时间: 2023-11-09 17:05:53 浏览: 34
好的,接下来是我的回答:
首先,定义链表结构体,包含节点值和下一个节点指针。
```c++
struct Node{
int val;
Node* next;
};
```
然后,定义一个指向链表头部的节点指针。
```c++
Node* head = NULL;
```
接着,实现插入函数。从头遍历链表找到第一个比插入值大的节点,然后在该节点之前插入新节点。注意需要考虑插入值比所有节点都小和插入值比所有节点都大的两种情况。
```c++
void insert(int val){
Node* newNode = new Node;
newNode->val = val;
if(head == NULL || val < head->val){
newNode->next = head;
head = newNode;
}
else{
Node* cur = head;
while(cur->next != NULL && cur->next->val < val){
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
}
}
```
最后,输出链表。从头遍历所有节点,依次输出其值。
```c++
void print(){
Node* cur = head;
while(cur != NULL){
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
```
完整代码如下:
```c++
#include <iostream>
using namespace std;
struct Node{
int val;
Node* next;
};
Node* head = NULL;
void insert(int val){
Node* newNode = new Node;
newNode->val = val;
if(head == NULL || val < head->val){
newNode->next = head;
head = newNode;
}
else{
Node* cur = head;
while(cur->next != NULL && cur->next->val < val){
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
}
}
void print(){
Node* cur = head;
while(cur != NULL){
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
}
int main(){
for(int i = 0; i < 5; i++){
int val;
cin >> val;
insert(val);
}
print();
return 0;
}
```