链表的有序构建和查找/构建链表【数据结构】

本文介绍: 构建链表

题目描述
单链表结点的存储结构包含两部分：数据、下一结点指针（默认为空）。
单链表包含头结点，存储实际数据的结点位置从1开始。
现输入一批无序的整数队列，编写程序完成以下要求
1）构建单链表并且把数据按递增顺序插入到链表中，并且统计非空指针发生变化的次数。

例如在初始只包含头结点的单链表中，依次插入3和2，当把3插入时，是头结点的next 指针发生变化，初始头结点的next指针是空的，现在指向3的结点，所以不计入指针变化次数。

当把2插入时，它是插入到头结点和3结点之间，这时候头结点的next指针从指向3变成指向2，因此这次计入指针变化次数。

总之，如果是把一个空的next指针指向新的结点，则不计入变化次数；如果是把一个非空next指针修改指向新结点则计入变化次数。

2）实现对单链表的元素查找。输入一个链表位置，返回该位置对应的数据。如果位置非法则输出提示信息，看样例。

要求：必须使用单链表结构实现上述要求，并且不能用第三方算法库或容器类对象

#include<bits/stdc++.h&gt;
using namespace std;
struct node
{
    int value;
    node* next=NULL;
};
int main()
{
    int n;
    scanf("%d",&amp;n);
    //new了的就不是NULL
    node* list=new node;
    int change=0;
    for(int i=0;i<n;i++)
    {
        node* now=list;
        //先新建该节点
        node* th=new node;
        int a2;
        scanf("%d",&amp;a2);
        th-&gt;value=a2;
        //思路：找到第一个比该数大的插到其前面
        while(1)
        {
            if(now-&gt;next==NULL) 
            {
                now-&gt;next=th;
                break;
            }
            if(now->next->value>a2)
            {
                th->next=now->next;
                now->next=th;
                change++;
                break;
            }
            now=now->next;
        }
    }
    cout<<"非空指针变化"<<change<<"次"<<endl;
    list=list->next;
    cout<<list->value;
    node* no=list->next;
    int a[205];
    int index=2;
    a[1]=list->value;
    while(no!=NULL)
    {
        printf(" %d",no->value);
        a[index++]=no->value;
        no=no->next;
    }
    cout<<endl;
    int m;
    cin>>m;
    for(int i=0;i<m;i++)
    {
        int x;
        scanf("%d",&amp;x);
        if(x<1||x>n)
        {
            printf("errorn");
            continue;
        }
        printf("%dn",a[x]);
    }
    return 0;
}