输入格式：
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N?(≤105)。结点的地址是5位非负整数，NULL地址用?1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。
输出格式：
对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1
思路：?
? ?题目为重排链表，但是仔细分析题意可发现，没必要真创建一条链表，用一个自定义的结构体数组代替即可。在代表链表节点的结构体中，应该包含的属性有1.节点当前地址（可用int类型的变量代表，例：输入00100会存入100）2.节点内保存的数据 3.当前节点下一个节点的地址 4.一个变量用来代表节点的顺序（我用的是order）
? ?因为题目中节点的地址是五位数，所以创建一个容量至少为100000的结构体数组（可创建一个全局的数组，因为100000比较大），遍历一遍数组，将数组中表示节点顺序的属性都初始化为100000以上。
? ?输入每个节点的地址时，应该设置一个int类型的变量进行输入，然后再找到这个int类型的变量在数组中的相应位置，然后让数组中下标为这个int类型变量的元素的当前地址等于这个int类型变量（有点绕哈），再输入数据，下一个节点的地址等，order（节点顺序属性）先不做处理。
? 设置一个count变量初始化为1，再将一开始就输入的第一个节点的地址赋值给一个新创建的temp变量，while循环，条件是temp！=1，循环体内遍历一遍相互有关联的节点（可能存在一个节点与其他节点都无联系，要将这个节点排除出去，相关实现看代码，很容易理解），遍历时count++来进行相关联的order赋值。循环完成后count--，此时count即是有效节点的数量
? 运用排序函数，按照元素的order进行重小到大排序。题目中的输出格式可通过一个循环以及两个变量，一个初始化为0，一个初始化为count-1完成，注意：输出地址时要用0补齐。
代码如下：
#include <iostream>
using namespace std;
#include <algorithm>
typedef struct
{
int address;
int data;
int next;
int order;
}Node;
bool cmp(Node a, Node b)
{
return a.order < b.order;
}
Node arr[100001];
int main()
{
int begin, n;//begin代表第一个节点的位置，n代表输入节点个数
cin >> begin >> n;
int i = 0;
for (i = 0; i < 100001; i++)
{
arr[i].order = 100001;
}
for (i = 0; i < n; i++)
{
int addr;
cin >> addr;
arr[addr].address = addr;//通过输入的地址找到数组中对应下标的地址
cin >> arr[addr].data;
cin >> arr[addr].next;
}
int count = 1;
int temp = begin;
while (temp != -1)//用于对有效节点之间的顺序进行赋值，第一个节点order为1
{
arr[temp].order = count++;
temp = arr[temp].next;
}
count--;
sort(arr, arr + 100001, cmp);//进行排序，执行完此语句后，有效的节点会按照前后顺序从下标为0的位置开始排列
int j = 0;
int k = count - 1;
for (i = 0; i < count; i++)
{
if (i % 2 != 0)
{
printf("%05d %d", arr[j].address, arr[j].data);//%05d 输出5位，不足的位数用0补齐
if (i != count - 1)
{
printf(" %05d\n", arr[k].address);
}
else
{
printf(" -1\n");//最后一个节点的下一个节点的地址按题目要求记为-1
}
j++;//考虑到下一次循环的情况
}
else
{
printf("%05d %d", arr[k].address, arr[k].data);
if (i != count - 1)
{
printf(" %05d\n", arr[j].address);
}
else
{
printf(" -1\n");
}
k--;//考虑到下一次循环的情况
}
}
return 0;
}
?
|