【数据结构-C语言实现】一元多项式的合并（有序链表）

【数据结构-C语言实现】一元多项式的合并（有序链表）

#include
#include
#define Status int

typedef struct
{
	int number; //多项式系数
	int power; //多项式幂数
}

typedef struct LNode
{
	LNode *next;
	ElemType data;
}LNode, *linkList;

//初始化链表
Status InitList(linkList &L)
{
	if(!L)
	{
		L = (LNode *)malloc(sizeof(LNode));
		L->next = NULL;
	}
	return 1;
}

//插入结点
Status InsertElem(linkList &L, int i, ElemType e)
{
	if(!L)
		return 0;
	LNode *p;
	p = L;
	int j = 0;
	while(p && jnext;
		j++;
	}
	if(!p || i<=0)
		return 0;
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return 1;
}

//删除结点
Status DeleteElem(linkList &L, int i, ElemType &e)
{
	if(!L || !L->next)
		return 0;
	LNode *p;
	p = L;
	int j = 0;
	while(p && jnext;
		j++;
	}
	if(!p || i<=0)
		return 0;
	LNode *q;
	q = p->next;
	p->next = q->next;
	e = q->data;
	free(q)
	return 1;
}

//返回结点
Status GetElem(linkList &L,int i,ElemType &e)
{
	if(!L || !L->next)
		return 0;
	LNode *p;
	p = L;
	int j=0;
	while(p && jnext;
		j++;
	}
	if(!p || i<=0)
		return 0;
	e = p->data;
	return 1;
}

Status MergeList(linkList La, linkList Lb, linkList &Lc)
{
	int label = 0;
	LNode *p1 = La->next;
	LNode *p2 = Lb->next;
	LNode *p3 = Lc = La;
	while(p1 && p2)
	{
		if(p1->data.power < p2->data.power)
		{
			p3->next = p1;
			p3 = p1;
			p1 = p1->next;
		}
		else if(p1->data.power > p2->data.power)
		{
			p3->next = p2;
			p3 = p2;
			p2 = p2->next;
		}
		else
		{
			p1->data.number = p1->data.number + p2->data.number;
			if(p1->data.number)
			{
				p3->next = p1;
				p3 = p1;
				label++;
			}
			p1 = p1->next;
			p2 = p2->next;
		}
	}
	if(p1)
		p3->next = p1;
	else
		p3->next = p2;
	free(Lb);
	return label;
}

//主函数
void main()
{
	linkList La,Lb,Lc;
	La = Lb = Lc = NULL;
	InitList(La);
	InitList(Lb);
	InitList(Lc);
	int n1,n2;
	int num,pow;
	ElemType x,y,z;
	printf("输入第一个一元多项式的项数:n");
	scanf("%d",&n1);
	printf("输入该多项式每项的系数和幂数：");
	for(int i=1;i<=n1;i++)
	{
		printf("n系数:");
		scanf("%d",&num);
		printf("n幂数:");
		scanf("%d",&pow);
		x.number = num;
		x.power = pow;
		InsertElem(La,i,x);
	}
	printf("输入第二个一元多项式的项数:n");
	scanf("%d",&n2);
	printf("输入该多项式每项的系数和幂数：");
	for(int j=1;j<=n2;j++)
	{
		printf("n系数:");
		scanf("%d",&num);
		printf("n幂数:");
		scanf("%d",&pow);
		y.number = num;
		y.power = pow;
		InsertElem(Lb,j,y);
	}
	printf("合并两个多项式n");
	int n = MergeList(La,Lb,Lc);
	printf("合并后的多项式为n");
	printf("系数tt幂数ttn");
	for(int k=1;k<=n1+n2-n;k++)
	{
		GetElem(Lc,k,z);
		printf("%3dtt%3dttn",z.number,z.power);
	}
}