题目:http://pat.zju.edu.cn/contests/pat-a-practise/1052
题解:
模拟链表按值排序
注意:可能给多个链表,只要输出与头地址相连的部分
可能输入的长度为0
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff struct point { char add[10];//当前结点地址 int num;//当前结点值 char nextx[10];//下个结点地址 int idx; } node[100005]; map<string,int> mapx; bool cmpIdx(const struct point &a,const struct point &b) { return a.idx<b.idx; } bool cmpValue(const struct point &a,const struct point &b) { return a.num<b.num; } int main() { int n,x,i; char st[10]; string s; scanf("%d%s",&n,st); for(i=0; i<n; ++i) { scanf("%s%d%s",node[i].add,&node[i].num,node[i].nextx); mapx.insert(make_pair(string(node[i].add),i)); node[i].idx=999999; } s=string(st); if(n==0||mapx.find(s)==mapx.end())//输入的链表长度为0或者输入的链表头地址有误 { printf("0 -1\n"); } else { for(i=1; s!="-1"; ++i)//找出了输入的链表头地址相连的部分 { x=mapx.find(s)->second; node[x].idx=i; s=string(node[x].nextx); } sort(node,node+n,cmpIdx);//把上面求出的有效部分移动到前端 n=i-1; sort(node,node+n,cmpValue);//对有效链表部分按值从小到大排序 printf("%d %s\n",n,node[0].add); for(i=0; i<n; ++i) { printf("%s %d ",node[i].add,node[i].num); if(node[i+1].idx==999999||node[i+1].idx==0)//如果当前结点为最后一个结点或者当前下个结点为无效链表部分 { printf("-1\n"); break; } else printf("%s\n",node[i+1].add); } } return 0; }