PAT1052 Linked List Sorting 最后一个样例不得分
思路:
构造好链表,然后按照键值从小到大排序,输出最后排好序的链表
易错点:
1.sort函数排序右区间应大于当前实际区间,右区间是开区间
例如我们要对node[100]中前50项排序
sort(node,node+49,cmp);
//是错误的,该函数排序区间【0,49)
正确写法应是:
sort(node,node+50,cmp);
//排序区间【0,50)
2.存在特判,在题目没说明链表不为空时,要注意链表不存在的情况,此时输出
0 -1
代码:
#include<algorithm>
#include<cstdio>
using namespace std;
struct Node{
int add,data,next;
}node[100005];
bool cmp(Node a,Node b)
{
return a.data<b.data;
}
int main()
{
int n,beginadd;
scanf("%d %d",&n,&beginadd);
Node result[n+5];
int address;
for(int i=0;i<n;i++)
{
scanf("%d",&address);
scanf("%d%d",&node[address].data,&node[address].next);
node[address].add=address;
}
int p=beginadd,count=0;
while(p!=-1)//链表连接
{
result[count]=node[p];
p=node[p].next;
count++;
}
//空链表,特判
if(count==0)
{
printf("0 -1\n");
return 0;
}
sort(result,result+count,cmp);
printf("%d %05d\n",count,result[0].add);
for(int i=0;i<count;i++)
{
if(i!=count-1)printf("%05d %d %05d\n",result[i].add,result[i].data,result[i+1].add);
else printf("%05d %d -1",result[i].add,result[i].data);
}
return 0;
}
还没有评论,来说两句吧...