pta_线性结构3_Reversing_Linked_List
题目描述：
Given a constant
K
and a singly linked list
L
, you are supposed to reverse the links of every
K
elements on
L
. For example, given
L
being 1→2→3→4→5→6, if
K
=3, then you must output 3→2→1→6→5→4; if
K
=4, you must output 4→3→2→1→5→6.
单链表翻转，给定链表长度N和常数K，在链表中每K个元素进行链表翻转，最后不足K个的保持原来顺序
输入样式
Each input file contains one test case. For each case, the first line contains the address of the first node, a positive
N
(≤105) which is the total number of nodes, and a positive
K
(≤
N
) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then
N
lines follow, each describes a node in the format:address Data Next
where
Address
is the position of the node,
Data
is an integer, and
Next
is the position of the next node.
第一行三个数分别表示链表头的地址，链表长度N以及每多少个元素进行翻转的K值
之后紧接N行，每一行都表示一个链表结点信息，注意此处给出的链表结点顺序是乱序的。每一行的结点信息有三个数，依次是该结点地址、结点值以及连接的下一个元素地址（如果是最后一个元素则为-1）
输出格式
For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.
将链表按照翻转后的顺序输出，每一个结点占一行，输出格式和输入的结点格式相同
输入示例
00100 6 4//address line k
00000 4 99999//address value next_address
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样式
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
//output with order
解题思路
本文的目标，存在地址与下一地址，因此采用结构指针处理。
同时，由于本题给定了输入的地址与输出的地址，为此在输出时候，需保证输出结果的顺序性
主要函数的设计分为以下几个模块
- 主函数，int main();
- 输入函数，ptr read_line(int add, int *l);
- 调序函数，ptr reverse(ptr p, int k);与ptr reverselist(ptr arr, int length, int k);
- 输出函数，void PrintList(ptr L);
代码分析
结构与宏
//定义node结构，里面包含结点当前地址，结点值，结点所指向的下一位置，结点指针
struct node {
int address;
int value;
int next_address;
struct node *next;
};
#define MAXSIZE 100002
typedef struct node* ptr;
//将结构指针重命名为ptr其类型为struct node*
struct node addr[MAXSIZE];
//定义结构数组在接下来的对输入排序起到重要作用
主函数
int main()
{
ptr arr,temp;
int add,l,k;
cin >> add >> l >> k;//读取第一列输入，第一列输入包含了首地址，输入个数，翻转的个数
arr=read_line(add, &l);
temp = reverselist(arr,l,k);
PrintList(temp);
}
输入函数
ptr read_line(int add, int l)
//输入函数，主要读取，输入的首地址和输入元素的个数
//并根据输入的首地址进行查找与排序
{
int temp_add, temp_next,add_num,pos;
ptr temp_link,temp, p;
temp=(ptr)malloc(sizeof(struct node));
temp->next= NULL;
//利用malloc函数申请空的指针存储空间
p = temp;
//p指向temp
for (int i = 0; i < l; i++)
{
//根据输入的地址在对应的结构指针中存储当前的地址，当前的值，和下一地址的值
cin >> add_num;
addr[add_num].address = add_num;
cin >> addr[add_num].value >> addr[add_num].next_address;
}
pos = add;
while (addr[pos].address != -1)
{
//从结构指针中读取相应首地址数组的地址，移动指针，并将pos值重置为下一位置的地址值，直到遇到-1
//此时，结构指针p已经将所有值都按顺序添加进去了
//当遇到-1，循环结束，跳出
p->next = &addr[pos];
p = p->next;
if (addr[pos].next_address == -1)
break;
pos = p->next_address;
}
//将结点释放出来
temp_link = temp;
temp = temp->next;
free(temp_link);
return temp;
}
输出函数
void PrintList(ptr L)
{
ptr p;
p = L;
while (p) {
//当结果保存，同时根据最后的位序进行划分输出
//由于当p-next不存在时，就代表已经到达了链表的尾部，所以输出-1
if (!p->next)
printf("%.5d %d %d\n", p->address, p->value, -1);
else
printf("%.5d %d %.5d\n", p->address, p->value, p->next->address);
p = p->next;
}
}
翻转函数
ptr reverse(ptr p, int k)
{
ptr p1, p2, p3, rear;
p1 = p;
p2 = p->next;
p3 = p->next->next;
while (k--)
{
//将p1，p2进行翻转，p1与p2的值进行调换，同时再将p3的值重新付给p2,并移动p3
//最后的结果保存在p2中
p2->next = p1;
p1 = p2;
p2 = p3;
if (p3)
{
p3 = p3->next;
}
}
rear = p->next;
rear->next = p2;
p->next = p1;
return rear;
}
//当长度等于1的时候直接相当于不用翻转，直接原样输出即可
ptr reverselist(ptr arr, int length, int k)
{
if (length == 1)
{
return arr;
}
ptr head, p,temp;
head = (ptr)malloc(sizeof(struct node));
head->next = arr;
//将arr与head连接起来
p = head;
p = reverse(p, k);
//释放结点
temp = head;
head = head->next;
free(temp);
return head;
}