PATAdvanceLevel（甲级）1052

发表于 更新于 分类于 ， 本文字数： 6.8k 阅读时长 ≈ 6 分钟

题目链接：1052 Linked List Sorting (25分)

题目描述如下：

作者: CHEN, Yue
单位: 浙江大学
时间限制: 400 ms
内存限制: 64 MB
代码长度限制: 16 KB
1052 Linked List Sorting (25分)
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 (<10^5) 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 [−10^5 ,10^5], 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

题目大意：

链表由一系列结构组成，这些结构在内存中不一定相邻。 我们假设每个结构都包含一个整数键和一个指向下一个结构的Next指针。 现在给出一个链表，您应该按照结构的键值以升序对它们进行排序。
输入
每一个输入文件包含一个测试样例。对于每一个样例，第一行包含一个正数N小于10的5次方和头结点的地址，N是内存中结点的总数，一个结点的地址是一个5位正整数。-1代表NULL。
接下来有N行，每一行以如下格式描述一个结点：
Address Key Next
address是结点在内存中的地址，key是一个在-10的5次方到10的5次方中的整数，next是下一个结点的地址。保证所有的key都不同并且从头结点开始的链表中没有环。
输出
对每一个样例输出格式和输入格式一样。N是链表中结点的总数并且所有的结点必须有序。

解题思路：

本题就是一道链表排序题，而且链表是静态链表，不过需要注意以下几点：
1、输入所给的结点并不一定都在链表上，有多余的结点，需要先遍历链表确定结点的个数。
2、测试样例中会有结点数目很多的情况，需要用快排的思想减小排序的时间复杂度，否则会运行超时。
3、头结点为-1时即表示是一个空链表，输出为：
0 -1

本题的C/C++代码如下所示
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#pragma warning(disable:4996)；
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define N 100010

using namespace std;

int len = 0;
/*用于接收输入的结构数组*/
struct node
{
	int key;
	int next;
}list[N];
/*用于排序的结构数组*/
struct MyStruct
{
	int key;	//结点的值
	int address;	//结点的地址
}L[N];
/*比较函数，如果用C++的algorithm中的sort函数排序需要此函数*/
bool cmp(MyStruct a, MyStruct b)
{
	return a.key < b.key;
}
/*求链表中的结点个数,并把输入的结构数组转换为用于排序的结构数组，当然也可以直接用原数组进行排序*/
void theLen(int address)
{
	while (address != -1)
	{
		L[++len].address = address;
		L[len].key = list[address].key;
		address = list[address].next;
	}
}
/*快排函数*/
int partition(int low, int high)
{
    MyStruct temp;
    temp = L[low];
    L[low]=L[(low+high)/2];
    L[(low+high)/2]=temp;
	L[0] = L[low];
	int key = L[low].key;
	while (low<high)
	{
		while (low<high&&L[high].key>key)
		{
			high--;
		}
		L[low] = L[high];
		while (low<high&&L[low].key<key)
		{
			low++;
		}
		L[high] = L[low];
	}
	L[low] = L[0];
	return low;
}

void qsort(int low, int high)
{
	if (low<high)
	{
		int loc = partition(low, high);

		qsort(low, loc - 1);
		qsort(loc + 1, high);
	}
}

void QuickSort(int n)
{
	qsort(1, n);
}

int main(void)
{

	int n, address;

	cin >> n >> address;

	for (int i = 0; i < n; i++)
	{
		int add, key, next;

		cin >> add >> key >> next;

		list[add].key = key;
		list[add].next = next;
	}



	theLen(address);

	/*链表长度不为零才需要进行排序，表长为零可以直接输出*/
	if (len)
	{
		QuickSort(len);	//使用快排函数进行排序
		//sort(L + 1, L + 1 + len, cmp);也可以直接使用sort函数进行排序
		//cout << len << ' ' << L[1].address << endl;
        	printf("%d %05d\n", len, L[1].address);	//格式化输出
		for (int i = 1; i < len; i++)
		{
			printf("%05d %d %05d\n", L[i].address, L[i].key, L[i + 1].address);
		}

		printf("%05d %d -1\n", L[len].address, L[len].key);
	}
	else
	{
		cout << 0 << ' ' << -1 << endl;	//输出最后一个结点时稍作处理
	}


	system("pause");

	return 0;
}

我在解本题时遇到最多的问题就是运行超时的问题，经过多次查找发现是快排函数的问题，我所使用的快排函数是严蔚敏老师的《数据结构C语言版第2版》246页的快排函数，以下是可以通过的快排函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int partition(int low, int high)
{
    MyStruct temp;
    temp = L[low];
    L[low]=L[(low+high)/2];
    L[(low+high)/2]=temp;
	L[0] = L[low];
	int key = L[low].key;
	while (low<high)
	{
		while (low<high&&L[high].key>key)
		{
			high--;
		}
		L[low] = L[high];
		while (low<high&&L[low].key<key)
		{
			low++;
		}
		L[high] = L[low];
	}
	L[low] = L[0];
	return low;
}

void qsort(int low, int high)
{
	if (low<high)
	{
		int loc = partition(low, high);

		qsort(low, loc - 1);
		qsort(loc + 1, high);
	}
}

void QuickSort(int n)
{
	qsort(1, n);
}

以下的快排函数会运行超时：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int partition(int low, int high)
{
	L[0] = L[low];
	int key = L[low].key;
	while (low<high)
	{
		while (low<high&&L[high].key>key)
		{
			high--;
		}
		L[low] = L[high];
		while (low<high&&L[low].key<key)
		{
			low++;
		}
		L[high] = L[low];
	}
	L[low] = L[0];
	return low;
}

void qsort(int low, int high)
{
	if (low<high)
	{
		int loc = partition(low, high);

		qsort(low, loc - 1);
		qsort(loc + 1, high);
	}
}

void QuickSort(int n)
{
	qsort(1, n);
}

两个快排函数的区别是在partition函数中主元的选取，超时的快排函数（也是书中的快排函数）是以low的值为主元，能够通过的快排函数是用（low+high）/2作为主元，主元的选取对于快排函数的性能有很大的影响。
以（low+high）/2作为主元是陈越老师在中国大学慕课平台数据结构课程中讲解快排函数时选取主元的方法，陈越老师给出的快排函数如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
typedef int ElementType;


void InsertionSort(ElementType A[], int N)
{ /* 插入排序 */
	int P, i;
	ElementType Tmp;

	for (P = 1; P<N; P++) {
		Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
		for (i = P; i>0 && A[i - 1]>Tmp; i--)
			A[i] = A[i - 1]; /*依次与已排序序列中元素比较并右移*/
		A[i] = Tmp; /* 放进合适的位置 */
	}
}


void Swap(int *a, int *b)
{
	int t;
	t = *a;
	*a = *b;
	*b = t;
}


/* 快速排序 */

ElementType Median3(ElementType A[], int Left, int Right)
{
	int Center = (Left + Right) / 2;
	if (A[Left] > A[Center])
		Swap(&A[Left], &A[Center]);
	if (A[Left] > A[Right])
		Swap(&A[Left], &A[Right]);
	if (A[Center] > A[Right])
		Swap(&A[Center], &A[Right]);
	/* 此时A[Left] <= A[Center] <= A[Right] */
	Swap(&A[Center], &A[Right - 1]); /* 将基准Pivot藏到右边*/
									 /* 只需要考虑A[Left+1] … A[Right-2] */
	return  A[Right - 1];  /* 返回基准Pivot */
}

void Qsort(ElementType A[], int Left, int Right)
{ /* 核心递归函数 */
	int Pivot, Cutoff=5, Low, High;

	if (Cutoff <= Right - Left) { /* 如果序列元素充分多，进入快排 */
		Pivot = Median3(A, Left, Right); /* 选基准 */
		Low = Left; High = Right - 1;
		while (1) { /*将序列中比基准小的移到基准左边，大的移到右边*/
			while (A[++Low] < Pivot);
			while (A[--High] > Pivot);
			if (Low < High) Swap(&A[Low], &A[High]);
			else break;
		}
		Swap(&A[Low], &A[Right - 1]);   /* 将基准换到正确的位置 */
		Qsort(A, Left, Low - 1);    /* 递归解决左边 */
		Qsort(A, Low + 1, Right);   /* 递归解决右边 */
	}
	else InsertionSort(A + Left, Right - Left + 1); /* 元素太少，用简单排序 */
}

void QuickSort(ElementType A[], int N)
{ /* 统一接口 */
	Qsort(A, 0, N - 1);
}

其实本题不用自己编写快排函数，直接使用algorithm中的sort函数就可以满足运行时间的要求，函数如下：
sort(start,end,cmp);
其中start的是待排数据起始位置，end是待排数据结束的位置，cmp是一个返回值为bool类型的比较函数，需要自己编写以告诉sort函数如何进行排序

总结

排序问题需要关心的就是效率问题，达到快排的时间复杂度才不会运行超时。

谢谢阅读，希望对你有所收获。