[题解](续II)Let’s Celebrate the 100th Contest on ZOJ! » ZOJ3441c

ZOJ3441c
ZOJ3441c.c


#include <stdio.h>
#include <stdlib.h>

struct Node {
	int value;
	struct Node* next;
};

/* (:) */
struct Node* cons(int value, struct Node* next) {
	struct Node* ret = (struct Node*)malloc(sizeof(struct Node));
	ret->value = value;
	ret->next = next;
	return ret;
}

/* filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate */
struct Node* filter(int f(int), struct Node* p) {
	if (p == NULL) return NULL;
	if (f(p->value)) {
		return cons(p->value, filter(f, p->next));
	} else {
		return filter(f, p->next);
	}
}

/* map f xs is the list obtained by applying f to each element of xs */
struct Node* map(int f(int), struct Node* p) {
	if (p == NULL) return NULL;
	return cons(f(p->value), map(f, p->next));
}

/* delete x removes the first occurrence of x from its list argument. */
struct Node* delete(int i, struct Node* p) {
	if (p == NULL) return NULL;
	if (i == p->value) {
		return p->next;
	} else {
		return cons(p->value, delete(i, p->next));
	}
}

/* The \\ function is list difference ((non-associative). In the result of xs \\ ys, the first occurrence of each element of ys in turn (if any) has been removed from xs. */
struct Node* deleteFirsts(struct Node* q, struct Node* p) {
	if (p == NULL) return q;
	return deleteFirsts(delete(p->value, q), p->next);
}

struct Node* read() {
	int c = getchar();
	if (c == '\n') {
		return NULL;
	} else {
		ungetc(c, stdin);
		scanf("%d", &c);
		return cons(c, read());
	}
}

struct Node* write(struct Node* p) {
	if (p == NULL) return NULL;
	printf("%d%c", p->value, p->next == NULL ? '\n' : ' ');
	return write(p->next);
}

int pos(int i) { return i > 0; }

int main(void) {
	struct Node *q = read();
	struct Node *p = read();
	write(deleteFirsts(filter(pos, q), map(abs, p)));
	return 0;
}
Leave a Reply