假设一个多项式形式为 ,其中,ei(1≤i≤m)为整数类型的指数,并且没有相同指数的多项式;ci(1≤i≤m)为实数类型的序数。编写求两个多项式相加的程序。
一个多项式由多个(1≤i≤m)多项式组成,每个多项式采用以下节点存储:
coef |
expn |
next |
其中,coef数据域存放序数ci;expn数据域存放指数ei;next域是一个链域,指向下一个节点。由此,一个多项式可以表示成由这些节点链接起来的单链表(假设该单链表是带头节点的单链表)。这样的单链表节点的类型定义如下:
typedef struct node
{
float coef; /*序数*/
int expn; /*指数*/
struct node *next; /*指向下一个节点的指针*/
} PolyNode;
在该单链表上实现线性表基本运算的原理与2.3.1节描述的完全相同,这些运算的实现算法如下:
void InitList(PolyNode *&L) /*初始化多项式单链表*/
{
L=(PolyNode *)malloc(sizeof(PolyNode)); /*建立头节点*/
L->next=NULL;
}
int GetLength(PolyNode *L) /*求多项式单链表的长度*/
{
int i=0;
PolyNode *p=L->next;
while(p!=NULL) /*扫描单链表L,用i累计数据节点个数*/
{
i++; /*计数增加*/
p=p->next; /*指针后移*/
}
return i;
}
PolyNode *GetElem(PolyNode *L,int i) /*返回多项式单链表中第i个节点的指针*/
{
int j=1;
PolyNode *p=L->next;
if(i<1 || i>GetLength(L))
return NULL;
while(j<i) /*沿next域找第i个节点*/
{
p=p->next; /*指针后移*/
j++;
}
return p;
}
PolyNode *Locate(PolyNode *L,float c,int e)/*在多项式单链表中按值查找*/
{
PolyNode *p=L->next;
while(p!=NULL && (p->coef!=c ||p->expn!=e))
p=p->next; /*指针后移*/
return p;
}
int InsElem(PolyNode *L,float c,int e,int i) /*在多项式单链表中插入一个节点*/
{
int j=1;
PolyNode *p=L,*s;
s=(PolyNode *)malloc(sizeof(PolyNode));
s->coef=c;s->expn=e;s->next=NULL;
if(i<1 || i>GetLength(L)+1)
return 0;
while (j<i) /*查找第i-1个节点*p*/
{
p=p->next; /*指针后移*/
j++;
}
s->next=p->next;
p->next=s;
return 1;
}
int DelElem(PolyNode *L,int i) /*在多项式单链表中删除一个节点*/
{
int j=1;
PolyNode *p=L,*q;
if (i<1 || i>GetLength(L))
return 0;
while (j<i) /*在单链表中查找第i-1个节点,由p指向它*/
{
p=p->next;j++;
}
q=p->next; /*q指向被删节点*/
p->next=q->next; /*删除*q节点*/
free(q);
return 1;
}
void DispList(PolyNode *L) /*输出多项式单链表的元素值*/
{
PolyNode *p=L->next;
while (p!=NULL)
{
printf("(%g,%d) ",p->coef,p->expn);
p=p->next;
}
printf("\n");
}
以上述多项式单链表的基本运算为基础,利用多项式序数数组C和指数数组E,创建一个多项式单链表的算法如下:
void CreaPolyList(PolyNode *&L,float C[ ],int E[ ],int n)
{
int i;
InitList(L);
for (i=0;i<n;i++)
InsElem(L,C[i],E[i],i+1);
}
将一个表示任意次序的多项式的单链表按expn数据域值从小到大顺序排列的算法的基本思路是采用插入排序法;首先分离出头节点*L,将第1个节点链接到其后,这样构成一个新有序单链表,再对原单链表中第2个及以后的节点,根据expn值在新有序单链表中通过比较找到正确的位置后插入。直到原单链表的所有节点插入完毕,算法便结束了。算法程序如下:
void SortPloy(PolyNode *&L) /*对L的多项式单链表按expn域递增排序*/
{
PolyNode *p=L->next,*q,*pre;
L->next=NULL;
while(p!=NULL)
{
if(L->next==NULL) /*处理第1个节点*/
{
L->next=p;p=p->next;
L->next->next=NULL;
}
else /*处理其余节点*/
{
pre=L;q=pre->next;
while (q!=NULL && p->expn>q->expn)
/*找q->expn刚大于或等于p->expn的节点*q的前驱节点*pre*/
{
pre=q;q=q->next;
}
q=p->next; /*在*pre节点之后插入*p*/
p->next=pre->next;
pre->next=p;
p=q;
}
}
}
将两个按expn数据域值从小到大顺序排列的多项式相加的算法的基本思路如下:首先创建新单链表的头节点*pc(存储相加后的结果),让p1和p2分别作为扫描pa和pb的指针,它们先指向pa和pb单链表的第1个节点。比较*p1和*p2两个节点的expn值,复制expn值较小的节点*s,将*s链接到pc单链表的尾节点(始终由tc指向它)之后。若*p1和*p2两个节点的expn值相等,且它们的coef域值相加后不为零,则以该相加值和expn值作为数据域值创建节点*s,也将*s链接到pc的尾节点之后。如此这样直到pa和pb中有一个扫描完为止,然后将未扫描完的单链表的节点复制并链接到pc的尾节点之后。算法程序如下:
PolyNode *AddPoly(PolyNode *pa,PolyNode *pb)
{
PolyNode *pc,*p1=pa->next,*p2=pb->next,*p,*tc,*s;
pc=(PolyNode *)malloc(sizeof(PolyNode)); /*新建头节点*pc*/
pc->next=NULL; /*pc为新建单链表的头节点*/
tc=pc; /*tc始终指向新建单链表的最后节点*/
while(p1!=NULL && p2!=NULL)
{
if(p1->expn<p2->expn) /*将*p1节点复制到*s并链接到pc尾*/
{
s=(PolyNode *)malloc(sizeof(PolyNode));
s->coef=p1->coef;s->expn=p1->expn;s->next=NULL;
tc->next=s;tc=s;
p1=p1->next;
}
else if(p1->expn>p2->expn) /*将*p2节点复制到*s并链接到pc尾*/
{
s=(PolyNode *)malloc(sizeof(PolyNode));
s->coef=p2->coef;s->expn=p2->expn;s->next=NULL;
tc->next=s;tc=s;
p2=p2->next;
}
else /*p1->expn=p2->expn的情况*/
{
if (p1->coef+p2->coef!=0) /*序数相加不为0时新建节点s并链接到pc尾*/
{
s=(PolyNode *)malloc(sizeof(PolyNode));
s->coef=p1->coef+p2->coef;s->expn=p1->expn;
s->next=NULL;
tc->next=s;tc=s;
}
p1=p1->next;p2=p2->next;
}
}
if(p1!=NULL) p=p1; /*将尚未扫描完的余下节点复制并链接到pc单链表之后*/
else p=p2;
while(p!=NULL)
{
s=(PolyNode *)malloc(sizeof(PolyNode));
s->coef=p->coef;s->expn=p->expn;s->next=NULL;
tc->next=s;tc=s;
p=p->next;
}
tc->next=NULL; /*新建单链表最后节点的next域置空*/
return pc;
}
现使用上述算法,实现以下两个多项式相加:
3x+7+5x17+9x8,-9x8+8x+22x7
设计的主程序如下:
void main()
{
PolyNode *L1,*L2,*L3;
float C1[ ]={3,7,5,9},C2[ ]={-9,8,22}; /*多项式序数数组*/
int E1[ ]={1,0,17,8},E2[ ]={8,1,7}; /*多项式指数数组*/
InitList(L1); /*初始化多项式单链表L1*/
InitList(L2); /*初始化多项式单链表L2*/
InitList(L3); /*初始化多项式单链表L3*/
CreaPolyList(L1,C1,E1,4); /*创建多项式单链表L1*/
CreaPolyList(L2,C2,E2,3); /*创建多项式单链表L2*/
printf("两多项式相加运算\n");
printf("原多项式A:");DispList(L1);
printf("原多项式B:");DispList(L2);
SortPloy(L1); /*对L1的多项式单链表按expn域递增排序*/
SortPloy(L2); /*对L2的多项式单链表按expn域递增排序*/
printf("排序后的多项式A:");DispList(L1); /*输出多项式单链表L1的元素值*/
printf("排序后的多项式B:");DispList(L2); /*输出多项式单链表L2的元素值*/
L3=AddPoly(L1,L2); /*将两个按expn数据域值从小到大顺序排列的多项式L1和L2相加*/
printf("多项式相加结果:");DispList(L3); /*输出结果多项式单链表L3的元素值*/
}
本程序的执行结果如下所示,从中看到上述两个多项式相加的结果为:
7+11x+22x7+5x17
两多项式相加运算
原多项式A:(3,1) (7,0) (5,17) (9,8)
原多项式B:(-9,8) (8,1) (22,7)
排序后的多项式A:(7,0) (3,1) (9,8) (5,17)
排序后的多项式B:(8,1) (22,7) (-9,8)
多项式相加结果:(7,0) (11,1) (22,7) (5,17)