题目描述
单链表结点的存储结构包含两部分：数据、下一结点指针（默认为空）。
单链表包含头结点，存储实际数据的结点位置从1开始。
现输入一批无序的整数队列，编写程序完成以下要求
1）构建单链表并且把数据按递增顺序插入到链表中，并且统计非空指针发生变化的次数。
例如在初始只包含头结点的单链表中，依次插入3和2
当把3插入时，是头结点的next指针发生变化，初始头结点的next指针是空的，现在指向3的结点，所以不计入指针变化次数。
当把2插入时，它是插入到头结点和3结点之间，这时候头结点的next指针从指向3变成指向2，因此这次计入指针变化次数。
总之，如果是把一个空的next指针指向新的结点，则不计入变化次数；如果是把一个非空next指针修改指向新结点则计入变化次数。
2）实现对单链表的元素查找。输入一个链表位置，返回该位置对应的数据。如果位置非法则输出提示信息，看样例。
要求：必须使用单链表结构实现上述要求，并且不能用第三方算法库或容器类对象
输入
第一行：第一个数字n表示样本数目，其后跟n个样本。
第二行：查找测试次数m 后跟m个待查找的位置。
输出
第一行输出构建链表过程中，非空指针变化的总次数，格式看样本
第二行输出单链表创建后，从头到尾依次输出链表中元素数据
第三行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error
输入样例1
6 1 8 5 2 4 3
4 0 2 10 6
输出样例1
非空指针变化4次
1 2 3 4 5 8
error
2
error
8
思路分析
就是链表题，建立单向链表，链表元素的插入和查找。
建立起带头节点的链表，完了之后，记录一下空指针变换的次数即可。
AC代码
#include <iostream>
using namespace std;
struct Node{
int data;
Node*next=NULL;
};
class List{
Node*head=new Node();
int size=0,count=0;
public:
void insert(int&data){
Node*new_one=new Node();
new_one->data=data;
Node*h=head;
while(h->next&&h->next->data<data){
h=h->next;
}
new_one->next=h->next;
if(h->next)
count++;
h->next=new_one;
size++;
}
bool find(int index,int&data){
if(size<index||index<=0)
return false;
Node*h=head;
while(index&&h->next){
h=h->next;
index--;
}
data=h->data;
return true;
}
void show(){
cout<<"非空指针变化"<<count<<"次"<<endl;
Node*h=head;
while(h->next->next){
h=h->next;
cout<<h->data<<' ';
}
cout<<h->next->data<<endl;
}
};
int main() {
int t,temp,data;
List list;
cin>>t;
while(t--){
cin>>temp;
list.insert(temp);
}
list.show();
cin>>t;
while(t--){
cin>>temp;
if(list.find(temp,data))
cout<<data<<endl;
else
cout<<"error"<<endl;
}
return 0;
}
