[数据结构与算法]PAT乙级1025

PAT乙级1025

马上读研了，拿pat复习一下吸语言。

题目

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K (≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 ?1 表示。

接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

输出格式：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6 4
00000 4 99999
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

错误

测试点5超时，测试点6答案错误

经典莽夫做法，完全不使用数据结构链表，企图莽过PAT系统，惨败！

超时可能出现在二层循环中，也可能出现在sort排序中。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

/*
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

00100 4 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218

00100 5 4
00000 4 99999
00100 1 12309
33218 3 00000
99999 5 -1
12309 2 33218

00100 1 1
00100 1 -1


*/

//statement code
struct node{
	char address[9];
	int data;
	char next[9];
	int degree;
}nodes[100000],input[100000];

char first[9];
int N;
int K;
int i,j;
//function section
int robustness_check1(){//robustness function1
	return 0;
}

void set_nodes(){
	char current[9];
	strcpy(current,first);
	for(i = 0 ; i < N ; i++){
		for(j = 0 ; j < N ; j++){
			if(strcmp(current,input[j].address) == 0){
				strcpy(nodes[i].address,input[j].address);
				nodes[i].data = input[j].data;
				strcpy(nodes[i].next,input[j].next);
				strcpy(current,input[j].next);
				break;
			}
		}
	}
	for(i = 0 ; i < N ; i++){
		nodes[i].degree = i;
	}
}

bool cmp_small_to_large(struct node n1 , struct node n2){
	return n1.degree < n2.degree;
}
bool cmp_large_to_small(struct node n1 , struct node n2){
	return n1.degree > n2.degree;
}

void print_result(){
	set_nodes();
	int current_index = 0;
	struct node* p = nodes;
	while(current_index + K <=N){
		sort(p+current_index,p+current_index+K,cmp_large_to_small);
		current_index += K;
	}

	for(i = 0 ; i < N ; i++){
		if(i != N-1)
			strcpy(nodes[i].next,nodes[i+1].address);
		else{
			nodes[i].next[0] = '-';
			nodes[i].next[1] = '1';
			nodes[i].next[2] = '\0';			
		}
	}
	for(i = 0 ; i < N ; i++){
		printf("%s %d %s",nodes[i].address,nodes[i].data,nodes[i].next);
		if(i != N-1)
			printf("\n");
	}
}

int main(){
	//input code
	scanf("%s %d %d",first,&N,&K);
	for(i = 0 ; i < N ; i++){
		int dat;
		char add[9],nex[9];
		scanf("%s %d %s",add,&dat,nex);
		strcpy(input[i].address,add);
		input[i].data = dat;
		strcpy(input[i].next,nex);
	}
	//robustness code
	//function code
	print_result();
	return 0;
}

2,4运行超时，1，3，6答案错误

这回我使用了哈希数组的方法，数组下标代表节点的地址，仍然不行，而且错的更加离谱。可能目前我的能力无法做出来这道题了，应该学习一下算法了。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

/*
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

00100 4 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218

00100 5 4
00000 4 99999
00100 1 12309
33218 3 00000
99999 5 -1
12309 2 33218

00100 1 1
00100 1 -1
*/

//statement code
struct node{
	int address;
	int data;
	int next;
}nodes[100000];
int i;
int start,N,K;
int add_buffer[100000];
//function section
int robustness_check1(){//robustness function1
	return 0;
}

void reset_nodes(){
	int link_index = 0;
	int current_address = start;
	while(link_index + 4 <= N){
		add_buffer[0] = current_address;
		for(i = 1 ; i <= K ; i++){
			current_address = nodes[current_address].next;
			add_buffer[i] = current_address;
		}
		for(i = 0 ; i < K ; i++){
			nodes[add_buffer[i]].next = add_buffer[(i+4)%5];
		}
		if(link_index == 0){
			start = add_buffer[K-1];
		}
		link_index +=4;
	}
}

void print_result(){
	reset_nodes();
	int current = start;
	while(true){
		if(nodes[current].next != -1){
			printf("%05d %d %05d\n", nodes[current].address,nodes[current].data, nodes[current].next);
			current = nodes[current].next;
		}
		else{
			printf("%05d %d %d\n", nodes[current].address,nodes[current].data, nodes[current].next);
			break;
		}
	}
}

int main(){
	//input code
	scanf("%d %d %d",&start ,&N,&K);
	for(i = 0 ; i < N ; i++){
		int add,dat,nex;
		scanf("%d %d %d",&add,&dat,&nex);
		nodes[add].address = add;
		nodes[add].data = dat;
		nodes[add].next = nex;
	}
	//robustness code
	//function code
	print_result();
	return 0;
}

博客

• 也使用了哈希数组来存放节点
• 还使用了一个权重值对节点进行了排序
• 以上两条相当于我的两次尝试相结合
• 但是博客中并没有真正地将链表反转，而是只是反转地将其输出而已。这是一个思路，真正地需求只是输出，那么我们就不必真的将其反转。

仍有错误

1，5答案错误

目前已经没有超时问题了，但是仍然有答案错误。显然经过分析，目前代码有严重的逻辑错误。

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

/*
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

00100 4 4
00000 4 -1
00100 1 12309
33218 3 00000
12309 2 33218

00100 5 4
00000 4 99999
00100 1 12309
33218 3 00000
99999 5 -1
12309 2 33218

*/

//statement code
struct node{
	int address;
	int data;
	int next;
	int degree;
}nodes[100010];
int i,j;
int N,K,start;

//function section
int robustness_check1(){//robustness function1
	return 0;
}

bool cmp(struct node n1 , struct node n2 ){
	return n1.degree < n2.degree;
}

void set_nodes_degree(){
	int current = start;
	int num = 0;
	for(i = 0 ; i < 100010 ; i++){
		nodes[i].degree = 100010;
	}
	while(current != -1){
		nodes[current].degree = num++;
		current = nodes[current].next;
	}
	N=num;
}

void print_result(){
	set_nodes_degree();
	
	sort(nodes,nodes+100001,cmp);
	int num = 0;
	for(i = 0 ; i < N/K ; i++){
		for(j = i*K + K - 1 ; j >= i*K ; j--){
			if(j == i*K){
				if(N%K ==0 && j == N-K){
					printf("%05d %d %d", nodes[j].address,nodes[j].data,nodes[i*K + K - 1].next);
					return;
				}else{
					printf("%05d %d %05d", nodes[j].address,nodes[j].data,nodes[i*K + K - 1].next);
					printf("\n");
				}
			}else{
				printf("%05d %d %05d\n", nodes[j].address,nodes[j].data,nodes[j-1].address);
			}
		}
	}

	for(i = (N/K)*K ;  i < N ; i++){
		if(i != N-1){
			printf("%05d %d %05d\n", nodes[i].address,nodes[i].data,nodes[i].next);
		}else{
			printf("%05d %d %d", nodes[i].address,nodes[i].data,nodes[i].next);			
		}
	}
}

int main(){
	//input code
	scanf("%d %d %d",&start,&N,&K);
	int add,dat,nex;
	for(i = 0 ; i < N ; i++){
		scanf("%d %d %d",&add,&dat,&nex);
		nodes[add].address = add;
		nodes[add].data = dat;
		nodes[add].next = nex;
	}
	//robustness code
	//function code
	print_result();
	return 0;
}

代码

#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>

using namespace std;

/*
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

00100 6 2
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

00100 5 2
00000 4 -1
00100 1 12309
33218 3 00000
68237 6 23546
12309 2 33218

00100 5 2
00000 4 99999
00100 1 12309
33218 3 00000
99999 5 -1
12309 2 33218

*/

//statement code
struct node{
	int address;
	int data;
	int next;
	int degree;
}nodes[100010];
int i,j;
int N,K,start;

//function section
int robustness_check1(){//robustness function1
	return 0;
}

bool cmp(struct node n1 , struct node n2 ){
	return n1.degree < n2.degree;
}

void set_nodes_degree(){
	int current = start;
	int num = 0;
	for(i = 0 ; i < 100010 ; i++){
		nodes[i].degree = 100010;
	}
	while(current != -1){
		nodes[current].degree = num++;
		current = nodes[current].next;
	}
	N=num;
}

void print_result(){
	set_nodes_degree();
	
	sort(nodes,nodes+100001,cmp);
	int num = 0;
	for(i = 0 ; i < N/K ; i++){
		for(j = i*K + K - 1 ; j >= i*K ; j--){
			if(j == i*K){
				if(j+K == N){//此小循环中的最后一个元素即整个链表中的最后一个元素时
					printf("%05d %d %d", nodes[j].address,nodes[j].data,nodes[i*K + K - 1].next);
					return;
				}else if(j + K-1+K > N - 1){//此小循环是整个链表的最后一个完整的小循环,但是后面还有元素时
					printf("%05d %d %05d", nodes[j].address,nodes[j].data,nodes[i*K + K - 1].next);
					printf("\n");
				}else{//此小循环不是最后一个完整的小循环时
					printf("%05d %d %05d", nodes[j].address,nodes[j].data,nodes[j+2*K - 1].address);
					printf("\n");
				}
			}else{
				printf("%05d %d %05d\n", nodes[j].address,nodes[j].data,nodes[j-1].address);
			}
		}
	}

	for(i = (N/K)*K ;  i < N ; i++){
		if(i != N-1){
			printf("%05d %d %05d\n", nodes[i].address,nodes[i].data,nodes[i].next);
		}else{
			printf("%05d %d %d", nodes[i].address,nodes[i].data,nodes[i].next);			
		}
	}
}

int main(){
	//input code
	scanf("%d %d %d",&start,&N,&K);
	int add,dat,nex;
	for(i = 0 ; i < N ; i++){
		scanf("%d %d %d",&add,&dat,&nex);
		nodes[add].address = add;
		nodes[add].data = dat;
		nodes[add].next = nex;
	}
	//robustness code
	//function code
	print_result();
	return 0;
}

总结

• 这道题是目前做的最难的一道题。

• 可能出现的情况非常多，坑也很多

• 遇到的全部坑：