PAT A1052 --静态链表

1. 先来一波温习：
   sort函数排序

• sort(first_pointer,first_pointer+n,cmp)，该函数可以给数组，或者链表list、向量排序。
  参数1：第一个参数是数组的首地址，一般写上数组名就可以，因为数组名是一个指针常量。
  参数2：第二个参数相对较好理解，即首地址加上数组的长度n（代表尾地址的下一地址）。
  参数3：默认可以不填，如果不填sort会默认按数组升序排序。
• 使用此函数需先包含：#include
• 可以自己编写排序规则函数
  例如：

bool compare(int a,int b)
    return a<b; //升序排列，如果改为return a>b，则为降序

2. 一开始的思路是这样的：

• 节点存放自己的地址，全部信息封装起来
• 因为原始输入的链表的地址顺序其实没有作用，最后的输出是会重新排序的，因为存放节点信息从0号下标处开始存即可
• 输入n个节点信息，按输入顺序放入数组中，然后用sort进行排序，排序的基准是按data的值升序排序，因此要写个cmp
• 最后输出前要连成链表，就直接当前元素的next是下一个元素的addr，最后一个元素的next为-1即可
• 可以特判一下输入节点数为0和1的时候
• 地址要求%05d，还是用scanf-printf组合好，注意next为-1时不能格式化，所以要特判

下面是思路实现出来的代码（感觉用了不少循环，提交后发现确实用时有点多，51ms，可以注意代码优化了）

#include<algorithm>
using namespace std;
const int maxn = 100010;
struct NODE {
	int addr;//节点存放自己地址
	int data;
	int next;
}list[maxn];
bool cmp(NODE a, NODE b) {
	return a.data < b.data;
}
int main() {
	int n, start;
	scanf("%d %d", &n, &start);
	if (n == 0) return 0;
	int addr, data, next;
	for (int i = 0; i < n; i++) {
		scanf("%d %d %d", &addr, &data, &next);
		list[i].addr = addr;
		list[i].data = data;
		list[i].next = next;
	}
	if (n == 1) {
		printf("%d %05d\n", n, list[0].addr);
		if (list[0].next == -1)
			printf("%05d %d %d\n", list[0].addr, list[0].data, list[0].next);
		else
			printf("%05d %d %05d\n", list[0].addr, list[0].data, list[0].next);
		return 0;
	}
	sort(list, list + n, cmp);
	for (int j = 0; j < n; j++) {
		if (j == n - 1)list[j].next = -1;
		else list[j].next = list[j + 1].addr;
		
	}
	printf("%d %05d\n", n, list[0].addr);
	for (int k = 0; k < n; k++) {
		if (list[k].next == -1)
			printf("%05d %d %d\n", list[k].addr, list[k].data, -1);
		else
			printf("%05d %d %05d\n", list[k].addr, list[k].data, list[k].next);
	}
	return 0;
}

提交结果是21分，部分正确，因此去看算法笔记里面的题解和网上的题解，看4分错在哪里。
3. 改进

• 有可能出现输入的节点里面，存在不是在以start开始的链表上的节点，所以节点结构要加个bool来判断，因此一开始整个数组要将in初始化为flase，并且要从start开始遍历一遍链表，将存在链表上的节点的in设为true，还有记录新链表的节点数count，方便最后遍历数组前count个节点
• cmp也要加上一步：不在链表上的节点都往后排，这样数组前count个数一定是在链表上且升序排序的

最终AC代码

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100005;
struct NODE {
	int addr;
	int data;
	int next;
	bool in;
}list[maxn];
bool cmp(NODE a, NODE b) {
//把不在链表上的都放到后面去，这样没有用到的位置也会被排到后面去，因此数组前面的元素都是链表上的节点
	if (a.in == false || b.in == false)
		return a.in > b.in;
	else return a.data < b.data;//data大的排到后面去
}
int main() {
	for (int i = 0; i < maxn; i++) {
		list[i].in = false;
	}
	int n, start;
	scanf("%d%d", &n, &start);
	int addr, data, next;
	for (int j = 0; j < n; j++) {
		scanf("%d%d%d", &addr, &data, &next);
		list[addr].addr = addr;
		list[addr].data = data;
		list[addr].next = next;
	}
	int tmp = start;//临时链表“指针”
	int count = 0;//在链表上的节点数
	while (tmp != -1) {
		list[tmp].in = true;
		count++;
		tmp = list[tmp].next;
	}
	if (count == 0) printf("0 -1");//新链表没有节点就输出0 -1
	else {
		sort(list, list + maxn, cmp);//将链表上的节点按data从小到大排在数组前面的位置
		/* 可以省去这一步，在print的时候写就好
		for (int j = 0; j < n; j++) {
			if (j == n - 1)list[j].next = -1;
			else list[j].next = list[j + 1].addr;

		}
		*/
		printf("%d %05d\n", count, list[0].addr);
		for (int k = 0; k < count; k++) {
			//if (list[k].next == -1) 因为没有前面的循环，要改个判断条件
			if (k == count - 1)
				printf("%05d %d %d\n", list[k].addr, list[k].data, -1);
			else
				printf("%05d %d %05d\n", list[k].addr, list[k].data, list[k + 1].addr);
		}
	}
	return 0;
}

发现其实时间是61ms，而且初始化和排序都是整个数组，所以这道题时间本身就会长一点吧。

PAT A1052 --静态链表

原文：https://www.cnblogs.com/3-louise-wang/p/14371882.html