PTA甲级 1052 Linked List Sorting (25分)

文章目录

题目原文Input Specification:Output Specification:Sample Input:Sample Output: 生词如下:题目大意:思路如下:注意点:测试点4出错的原因 代码如下:柳神的代码 强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

还有就是非常非常有用的 算法笔记 全名是

算法笔记 上级训练实战指南 //这本都是PTA的题解 算法笔记

PS 今天也要加油鸭

题目原文

A linked list consists of a series of structures, which are not necessarily adjacent in memory. We assume that each structure contains an integer key and a Next pointer to the next structure. Now given a linked list, you are supposed to sort the structures according to their key values in increasing order.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive N (<105) and an address of the head node, where N is the total number of nodes in memory and the address of a node is a 5-digit positive integer. NULL is represented by −1.

Then N lines follow, each describes a node in the format:

Address Key Next

where Address is the address of the node in memory, Key is an integer in [−105,105], and Next is the address of the next node. It is guaranteed that all the keys are distinct and there is no cycle in the linked list starting from the head node.

Output Specification:

For each test case, the output format is the same as that of the input, where N is the total number of nodes in the list and all the nodes must be sorted order.

Sample Input:

5 00001 11111 100 -1 00001 0 22222 33333 100000 11111 12345 -1 33333 22222 1000 12345

Sample Output:

5 12345 12345 -1 00001 00001 0 11111 11111 100 22222 22222 1000 33333 33333 100000 -1

生词如下:

Linked 把什么连接起来 有联系

structures 结构

adjacent 临近的

题目大意:

给你几个node让你把他们按照key的值按顺序进行排列

思路如下:

一个sort解决问题

注意点:

测试点4出错的原因

这个链表可能是空的,在空链表的情况下.

我们要输出

0 -1

代码如下:

#include<iostream> #include<algorithm> using namespace std; struct node { int key; int next; }Node[100005]; bool cmp(struct node a, struct node b) { return a.key < b.key; } int main(void) { struct node result[100005]; int N = 0, temp = 0, FirstAddress = 0,i=0,j=0; scanf("%d%d", &N, &FirstAddress); for (i = 0; i < N; ++i) { scanf("%d", &temp); scanf("%d%d", &Node[temp].key, &Node[temp].next); } i = 0; while (FirstAddress != -1) { result[i].next = FirstAddress; result[i].key = Node[FirstAddress].key; FirstAddress = Node[FirstAddress].next; i++; } sort(result, result + i, cmp); if (i != 0) { printf("%d d\n", i, result[0].next); for (j = 0; j < i - 1; ++j) { printf("d %d d\n", result[j].next, result[j].key, result[j + 1].next); } printf("d %d -1", result[j].next, result[j].key); } else printf("0 -1"); return 0; }

柳神的代码

柳神的代码比我的代码好在只用了一个结构体.

用了一个bool类型来帮助写移动代码.

#include <iostream> #include <algorithm> using namespace std; struct NODE { int address, key, next; bool flag; }node[100000]; int cmp1(NODE a, NODE b) { return !a.flag || !b.flag ? a.flag > b.flag : a.key < b.key; } int main() { int n, cnt = 0, s, a, b, c; scanf("%d%d", &n, &s); for(int i = 0; i < n; i++) { scanf("%d%d%d", &a, &b, &c); node[a] = {a, b, c, false}; } for(int i = s; i != -1; i = node[i].next) { node[i].flag = true; cnt++; } if(cnt == 0) { printf("0 -1"); } else { sort(node, node + 100000, cmp1); printf("%d d\n", cnt, node[0].address); for(int i = 0; i < cnt; i++) { printf("d %d ", node[i].address, node[i].key); if(i != cnt - 1) printf("d\n", node[i + 1].address); else printf("-1\n"); } } return 0; }

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.