數據結構之---C語言實現連式多項式

數據結構之---C語言實現連式多項式

//鏈式存儲實現多項式
#include 
#include 
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()
{
	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);
	for(i = 0; i < n; i++)
	{
		scanf(%d_%d
, &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;
	if(p->head == p->tail)
			return;
	for(t = p->head->next; 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
, (t->c>0) ? (t->c):(-t->c), t->e);
}


poly_t poly_add(poly_t p1, poly_t p2)
{
	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, t2->e);
			t1 = t1->next;
		}
		else if(t1->e > t2->e)
		{
			p->tail = p->tail->next = TERM(t2->c, t2->e);
			t2 = t2->next;		
		}
		else
		{
			int sum = t1->c + t2->c;
			if(sum != 0)
			{
				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;
}

int main()
{
	poly_t p1, p2, p3;
	p1 = poly_init();
	term_read(p1);
	poly_show(p1);

	p2 = poly_init();
	term_read(p2);
	poly_show(p2);
	
	p3 = poly_add(p1, p2);
	poly_show(p3);

	poly_destory(p1);
	poly_destory(p2);
	poly_destory(p3);
	return 0;
}