学步园

本想会很快写出来的程序，最后总是用了很长时间。

这题开始时用链表，大数据却是段错误和内存超限。毕竟struct貌似要额外的48字节记录信息。

#include <stdio.h>
#include <malloc.h>

typedef struct node{
	int v;
	struct node *nx;
}ND;

int main()
{
	freopen("in.txt", "r", stdin);
	int k;
	int x;
	int c=0;
	scanf("%d", &k);
	ND *p=NULL, *q=NULL, *r=NULL;
	r = (ND*)malloc(sizeof(ND));
	r->v = -1;
	r->nx = NULL;
	p = r;
	while(1){
		scanf("%d", &x);
		if(x < 0) break;
		if(c < k){
			q = (ND*)malloc(sizeof(ND));
		}
		else{
			q = p->nx;
			p->nx = q->nx;
//			free(q);
		}
		q->v = x;
		q->nx = NULL;
		r->nx = q;
		r = q;
		c++;
	}
	if(c < k)
		printf("NULL");
	else
		printf("%d", p->nx->v);
	return 0;
}

上面能保证链表长度不超过k，也不用free了。

考虑错误的原因一个是struct问题，另一个可能是OJ问题，因为自己做的10^8都没有段错误。不过之前用free不会有3号测试点的段错误。为什么呢?

补充1：

终于找到原因了，没放弃。

	while(1){
		scanf("%d", &x);
		if(x < 0) break;
		q = (ND*)malloc(sizeof(ND));
		q->v = x;
		q->nx = NULL;
		r->nx = q;
		r = q;
		c++;
		if(c > k){
			q = p->nx;
			p->nx = q->nx;
			free(q);
		}
	}

之前版本的用free，没想到这几次内存都在31300+，恰好全过了。突然发现测试点3的内存只用了256，和点1，点2一样。但3出现段错误，想到可能是k=1出错的。测试了一下，果然！

还是想了好久，最后gdb才知道是一个元素删除时引发的尾指针丢失问题：

		else{
			q = p->nx;
			if(q->nx == NULL)
				r = p;
			p->nx = q->nx;
//			free(q);
		}

修改了else果然全过了！！

//

由于之前说的产生错误，不得不用简单的循环队列做。这种方法就简单明了。

#include <stdio.h>

int main()
{
	freopen("in.txt", "r", stdin);
	int k;
	int x;
	int c=0;
	int *m;
	int p=0;
	scanf("%d", &k);
	m = (int*)malloc(sizeof(int)*k);
	while(1){
		scanf("%d", &x);
		if(x < 0) break;
		m[p] = x;
		p = (p+1)%k;
		c++;
	}
	if(c < k)
		printf("NULL");
	else
		printf("%d", m[p]);
	return 0;
}

补充2：

链表算法出现的消耗超出预期的内存的原因，我的博客《malloc申请空间到底有多少 》分析了