X2+1可以表示为2,0,Xn+X(n-1)+...+1即n,n-1,.....0
所有的指数建议按大小排序,可以在单链表插入时进行。
加法,可以新建一个链表C做为结果,把链表A的内容复制到C,然后把另一个链表B中的每一项插入C,如果要插入的项已存在,则不插入并且删除这个结点。
乘法,新建一个链表C作为结果,要用2层循环遍历A和B中的每一项,对AB中的每个项都要算个加法,把和插入C中,如果这个和已存在,则不插入并且删除这个结点。
#include<stdio.h>#include<stdlib.h>
#include<malloc.h>
typedef int ElemType
/*单项链表声明*/
typedef struct PolynNode{
int coef // 系数
int expn // 指数
struct PolynNode *next
}PolynNode,*PolynList
/*位序(插表尾)输入n元素值建立带表结构单链线性表*/
/*指数系数输入*/
void CreatePolyn(PolynList &L,int n)
{
int i
PolynList p,q
L=(PolynList)malloc(sizeof(PolynNode)) // 结点
L->next=NULL
q=L
printf("输入%d数据\n",n)
for(i=1i<=ni++)
{
p=(PolynList)malloc(sizeof(PolynNode))
scanf("%d%d",&p->coef,&p->expn) //指数系数输入
q->next=p
q=q->next
}
p->next=NULL
}
// 初始条件:单链表L已存
// 操作结: 依L每数据元素调用函数vi()旦vi()失败,则操作失败
void PolynTraverse(PolynList L,void(*vi)(ElemType, ElemType))
{
PolynList p=L->next
while(p)
{
vi(p->coef, p->expn)
if(p->next)
{
printf(" + ") //+号输项面没+
}
p=p->next
}
printf("\n")
}
/*ListTraverse()调用函数(类型要致)*/
void visit(ElemType c, ElemType e)
{
if(c != 0)
{
printf("%dX^%d",c,e) //格式化输项式每项
}
}
/* 项式相加原理:归并 */
/* 参数:两已经存项式 */
/* 返值:归并新项式结点 */
PolynList MergeList(PolynList La, PolynList Lb)
{
PolynList pa, pb, pc, Lc
pa = La->next
pb = Lb->next
Lc = pc = La // 用La结点作Lc结点
while(pa&&pb)
{
if(pa->expn < pb->expn)
{
pc->next = pa //指数相等pc指针连指数结点
pc = pa
pa = pa->next //指向该结点指针移
}
else if (pa ->expn > pb->expn )
{
pc->next = pb //pc指针连指数结点
pc = pb
pb = pb->next //指向该结点指针移
}
else //(pa ->expn = pb->expn )
{
pa->coef = pa->coef + pb->coef //指数相等系数相加
pc->next = pa
pc = pa
pa = pa->next //两指针都往移
pb = pb->next
}
}
pc->next = pa ? pa:pb // 插入剩余段
return Lc
}
void main()
{
PolynList ha,hb,hc
printf("非递减输入项式ha ")
CreatePolyn(ha,5) // 位序输入n元素值
printf("非递减输入项式hb ")
CreatePolyn(hb,5) // 位序输入n元素值
printf("项式ha :")
PolynTraverse(ha, visit)
printf("\n")
printf("项式hb :")
PolynTraverse(hb, visit)
printf("\n")
hc = MergeList(ha,hb)
PolynTraverse(hc, visit)
}