PAT1052 Linked List Sorting 最后一个样例不得分

女爷i 2023-07-18 12:35 67阅读 0赞

思路:
构造好链表,然后按照键值从小到大排序,输出最后排好序的链表

易错点:
1.sort函数排序右区间应大于当前实际区间,右区间是开区间
例如我们要对node[100]中前50项排序

  1. sort(node,node+49,cmp);
  2. //是错误的,该函数排序区间【0,49)

正确写法应是:

  1. sort(node,node+50,cmp);
  2. //排序区间【0,50)

2.存在特判,在题目没说明链表不为空时,要注意链表不存在的情况,此时输出

0 -1

代码:

  1. #include<algorithm>
  2. #include<cstdio>
  3. using namespace std;
  4. struct Node{
  5. int add,data,next;
  6. }node[100005];
  7. bool cmp(Node a,Node b)
  8. {
  9. return a.data<b.data;
  10. }
  11. int main()
  12. {
  13. int n,beginadd;
  14. scanf("%d %d",&n,&beginadd);
  15. Node result[n+5];
  16. int address;
  17. for(int i=0;i<n;i++)
  18. {
  19. scanf("%d",&address);
  20. scanf("%d%d",&node[address].data,&node[address].next);
  21. node[address].add=address;
  22. }
  23. int p=beginadd,count=0;
  24. while(p!=-1)//链表连接
  25. {
  26. result[count]=node[p];
  27. p=node[p].next;
  28. count++;
  29. }
  30. //空链表,特判
  31. if(count==0)
  32. {
  33. printf("0 -1\n");
  34. return 0;
  35. }
  36. sort(result,result+count,cmp);
  37. printf("%d %05d\n",count,result[0].add);
  38. for(int i=0;i<count;i++)
  39. {
  40. if(i!=count-1)printf("%05d %d %05d\n",result[i].add,result[i].data,result[i+1].add);
  41. else printf("%05d %d -1",result[i].add,result[i].data);
  42. }
  43. return 0;
  44. }

发表评论

表情:
评论列表 (有 0 条评论,67人围观)

还没有评论,来说两句吧...

相关阅读