1052. Linked List Sorting (25)

题目:

https://www.patest.cn/contests/pat-a-practise/1052

大概描述:

主要就是对链表进行排序

特征词:

链表

使用语言:

C++

解题思想:

再将链表存储好了之后,可以用依据链表元素值,对地址进行操作,(这基本是对链表题的通用解法,address data next,一般都是先依据关系存储到一个结构中,然后依据顺序提出address进行操作,然后依照规则输出,此时已经不需要管next了)

题目得分:

24

提交次数:

1

时间

25分钟

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXI = 100000;
int s[MAXI] ;
int aa[MAXI][2];

bool qq(int a,int b){
 return aa[a][0] < aa[b][0];
}
int main(){
 int num ;
 int fir;
 int i = 0;
 int a,b,c;
 scanf("%d %d",&num,&fir);
 for(i = 0;i < num;i++){
 scanf("%d %d %d",&a,&b,&c);
 aa[a][0] = b;
 aa[a][1] = c;
 }
 //printf("read finished\n");
 int r = fir;
 i = 0;
 while(r != -1){
 s[i ++] = r;
 r = aa[r][1];
 }
 //printf("will sort\n");
 sort(s,s + i ,qq);
 printf("%d %05d\n",i,s[0]);
 int j = 0;
 int flg = 0;
 for(j = 0;j < i;j++){
 if(flg == 0){
 printf("%05d %d ",s[j],aa[s[j]][0]);
 flg = 1;
 }
 else
 printf("%05d\n%05d %d ",s[j],s[j],aa[s[j]][0]);
 }
 printf("-1");
}

运行结果

24

 成长

对于链表,在存储好基本关系后,只需要对地址处理就可以了,这一题是对之前链表处理的练习

发表评论

电子邮件地址不会被公开。 必填项已用*标注