首页 > 代码库 > 线性表之单链表实现一元多项式相加

线性表之单链表实现一元多项式相加

一元多项式定义:
设a0,a1,a2,…,an-1,an都是数域F中的数(注:1,2,……,n-1,n均为a的下角标),n是非负整数,那么表达式
anx^n +an-1x^(n-1)+…+a2x^2 +a1x + a0(an≠0) (1)
叫做数域F上一个文字x的多项式或一元多项式。在多项式(1)中,a0叫做零次多项式或常数项,a1x叫做一次项,一般,aix叫做i次项,ai叫做i次项的系数。一元多项式用符号f(x),g(x),…来表示。
说一下思路,利用带有两个数据元素的链表实现加法运算,数据域分别保存coef(系数)和exp(指数),运算时比较两链表当前数据域指数大小,三种情况结合正确组装出和链表并存入原链表LA,(注意本问题多项式的指数按从小到大顺序排列)。,代码如下:
#include<iostream>
using namespace std;
typedef struct Polynode
{
	int coef;
	int exp;
	struct Polynode *next;
}Polynode,*Polylist;

void init_linklist(Polylist *L)/*对单链表进行初始化*/
{
	*L=(Polylist)malloc(sizeof(Polynode)); /*申请结点空间*/
	(*L)->next=NULL;                      /*置为空表*/
}

void polycreate(Polylist head)
{
	Polynode *rear, *s;
	int c,e;
	rear=head;	                            /* rear 始终指向单链表的尾,便于尾插法建表*/
	cin>>c>>e;                  /*键入多项式的系数和指数项*/
	while(c!=0)	                            /*若c=0,则代表多项式的输入结束*/
	{
		s=(Polynode*)malloc(sizeof(Polynode));	/*申请新的结点*/
		s->coef=c;
		s->exp=e;
		rear->next=s;		/*在当前表尾做插入*/
		rear=s;
		cin>>c>>e; 
	}
	rear->next=NULL;	/*将表的最后一个结点的next置NULL,以示表结束*/
}

void  polyadd(Polylist polya, Polylist polyb)
/*此函数用于将两个多项式相加,然后将和多项式存放在多项式polya中,并将多项式ployb删除*/
{
	Polynode  *p, *q, *pre, *temp;
	int sum;
	p=polya->next;   /*令 p和q分别指向polya和polyb多项式链表中的第一个结点*/
	q=polyb->next;        
	pre=polya;  /* r指向和多项式的尾结点*/
	while (p!=NULL && q!=NULL) /*当两个多项式均未扫描结束时*/
	{ 
		if  (p->exp < q->exp)
			/*如果p指向的多项式项的指数小于q的指数,将p结点加入到和多项式中*/
		{ 
			pre->next=p;  
			pre=p; 
			p=p->next;
		}
		else
			if ( p->exp == q->exp)  /*若指数相等,则相应的系数相加*/
			{  
				sum=p->coef + q->coef;
				if (sum != 0)
				{ 
					p->coef=sum;
					pre->next=p; 
					pre=p;
					p=p->next;
					temp=q; 
					q=q->next; 
					free(temp);
				}
				else
				{  
					temp=p;
					p=p->next;
					free(temp); 
					/*若系数和为零,则删除结点p与q,并将指针指向下一个结点*/
					temp=q; 
					q=q->next;
					free(temp);
				}
			}
			else
			{  
				pre->next=q;
				pre=q; /*将q结点加入到和多项式中*/
				q = q->next; 
			}
	}
	if(p!=NULL)  /*多项式A中还有剩余,则将剩余的结点加入到和多项式中*/
		pre->next=p;
	else      /*否则,将B中的结点加入到和多项式中*/
		pre->next=q;
}
void print(Polylist L)
{
	Polylist p;
	p=L->next;
	while(p!=NULL)
	{
		cout<<p->coef<<"  "<<p->exp<<"  ";
		p=p->next;
	}
	cout<<endl;
}
int main()
{
	
	Polylist LA,LB;
	init_linklist(&LA);
	init_linklist(&LB);
	polycreate(LA);
	print(LA);
	
	polycreate(LB);
	print(LA);
	
	polyadd(LA,LB);
	print(LA);
	return 0;
}
挺经典的,,,考试神马的简单问题也许用得到

线性表之单链表实现一元多项式相加