polynomial.c

数据结构源码合集

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

typedef struct term *link;
struct term
{
	int c;
	int e;
	link next;
};
typedef struct
{
	link head;
	link tail;
} *poly_t;

link TERM(int c, int e)
{
	link t = malloc(sizeof *t);
	t->c = c;
	t->e = e;
	t->next = NULL;
	
	return t;
}

poly_t poly_init(void)
{
	poly_t p = malloc(sizeof *p);
	p->head = p->tail = TERM(0, 0);

	return p;
}

void term_read(poly_t p)
{
	int i, n;
	int c, e;
	scanf("%d\n", &n);
	for(i = 0; i < n; i++)
	{
		scanf("%d %d\n", &c, &e);
		p->tail = p->tail->next = TERM(c, e);
	}
}

poly_t poly_destory(poly_t p)
{
	link t, x;
	for(t = p->head; t; free(t), t = x)
		x = t->next;
	free(p);

	return NULL;
}

void poly_show(poly_t p)
{
	link t = p->head->next;
	if(p->head == p->tail)
		return;
	if(t->c < 0)
		printf("-");
	for(; t != p->tail; t = t->next)
	{
		printf("%dx^%d %c", (t->c > 0) ? (t->c) : (-t->c),
			   t->e, ((t->next->c > 0) ? '+' : '-'));
	}
		printf("%dx^%d\n", (t->c > 0) ? (t->c) : (-t->c), t->e);
}

poly_t poly_add(poly_t p1, poly_t p2)
{
	int sum;

	poly_t p = poly_init();
	link t1 = p1->head->next;
	link t2 = p2->head->next;
	
	while(t1 && t2)
	{
		if(t1->e < t2->e)
		{
			p->tail = p->tail->next = TERM(t1->c, t1->e);
			t1 = t1->next;
		}
		else if(t1->e > t2->e)
		{
			p->tail = p->tail->next = TERM(t2->c, t2->e);
			t2 = t2->next;
		}
		else
		{
			sum = t1->c + t2->c;
			if(sum)
				p->tail = p->tail->next = TERM(sum, t1->e);
			t1 = t1->next;
			t2 = t2->next;
		}
	}
	for(; t1; t1 = t1->next)
		p->tail = p->tail->next = TERM(t1->c, t1->e);
	for(; t2; t2 = t2->next)
		p->tail = p->tail->next = TERM(t2->c, t2->e);

	return p;
}

void change_sign(poly_t p)
{
	link x = p->head->next;
	while(x)
	{
		x->c = -x->c;
		x = x->next;
	}
}

poly_t poly_minus(poly_t p1, poly_t p2)
{
	change_sign(p2);
	return poly_add(p1, p2);
}

int main(void)
{
	poly_t p1, p2, p3, p4;

	p1 = poly_init();
	term_read(p1);
	poly_show(p1);

	p2 = poly_init();
	term_read(p2);
	poly_show(p2);

	p3 = poly_add(p1, p2);
	p4 = poly_minus(p1, p2);
	poly_show(p2);
	poly_show(p3);
	poly_show(p4);

	poly_destory(p1);
	poly_destory(p2);
	poly_destory(p3);
	poly_destory(p4);

	return 0;
}