|
用单链表ha 存储多项式A（x ）=a0+a1x1+a2x2+…+anxn(其中aI为非零系数)，用单链表hb 存储多项式B（x ）=b0+b1x1+b2x2+…+bmxm(其中bj为非零系数)，要求计算C（x ）= A（x ）+B（x ），结果存到单链表hc中。?
算法思想：首先传入两个多项式链表，申请一个链表存放相加的结果，依次取出两个多项式的节点。如果指数相等则相加，结果为零，释放该节点，不为零申请节点将加和结果存入节点，并将节点插入和多项式；如果不相等，则把指数大的节点插入和多项式。在一个链表计算完成之后若另一个链表还有节点，则将剩余节点全部插入和多项式。
#include?<stdio.h>??
#include?<stdlib.h>??
#include?<windows.h>??
/*?
????1.首先要进行多项式的读入，ReadPoly（）??
????2.进行多项式加法，AddPoly（）?
????3.进行多项式的输出，PrintPoly（）??
*/??
typedef?struct?PolyNode?*?Polynomial;??
struct?PolyNode{??
????int?coef;//系数???
????int?expon;//指数???
????Polynomial?link;??
};??
void?Attach(int?c,?int?e,?Polynomial?*?rear);//将新读入的系数和指数加到多项式的末尾???
Polynomial?ReadPoly();//读入多项式???
Polynomial?AddPoly(Polynomial?P1,?Polynomial?P2);//计算两个多项式之和???
void?PrintPoly(Polynomial?P);//输出多项式运算结果???
int?main()??
{??
????Polynomial?P1?=?ReadPoly();??
????Polynomial?P2?=?ReadPoly();??
????Polynomial?PA?=?AddPoly(P1,?P2);??
????PrintPoly(PA);??
????system("pause");??
????return?0;??
}??
void?Attach(int?c,?int?e,?Polynomial?*?rear)??
{??
????Polynomial?input?=?(Polynomial)malloc(sizeof(struct?PolyNode));??
????//申请新节点并赋初值???
????input->coef?=?c;??
????input->expon?=?e;??
????input->link?=?NULL;??
????(*rear)->link?=?input;??
????*rear?=?input;?//修改末尾指针，因为是修改指针，故此处使用指针的指针???
}??
Polynomial?ReadPoly()??
{??
????Polynomial?P1,?rear,?t;??
????int?N;//多项式项数???
????int?c,e;//用来暂存系数和指数???
????P1?=?(Polynomial)malloc(sizeof(struct?PolyNode));//申请头节点???
????//申请头节点是为了方便使用Attach函数时，不用区分rear是空还是非空，有了头节点都是非空，插入方便???
????P1->link?=?NULL;??
??????
????rear?=?P1;//尾指针指向头节点???
????printf("请输入多项式项数：\n");??
????scanf("%d",&N);??
????printf("请输入多项式(格式为a**b?c**d,指数递减)：\n");??
????while(N--)???
????{??
????????scanf("%d**%d",&c,?&e);??
????????Attach(c,?e,?&rear);??
????}??
????t?=?P1;???
????P1?=?P1->link;??
????free(t);//释放头节点??
????return?P1;???
}??
Polynomial?AddPoly(Polynomial?P1,?Polynomial?P2)??
{??
????Polynomial?t1,t2,rear,t;??
????t1?=?P1;??
????t2?=?P2;??
????Polynomial?P?=?(Polynomial)malloc(sizeof(struct?PolyNode));??
????P->link?=?NULL;??
????rear?=?P;??
????while(t1?&&?t2)??
????{??
????????if(t1->expon?==?t2->expon)//如果指数相同则进行相加???
????????{??
????????????if(t1->coef?+?t2->coef)//如果系数相加不为零，则将计算结果加入P中???
????????????{??
????????????????Attach(t1->coef?+?t2->coef,?t1->expon,?&rear);??
????????????}??
????????????t1?=?t1->link;??
????????????t2?=?t2->link;??
????????}??
????????else?if(t1->expon?>?t2->expon)//找到指数大的加入到P中???
????????{??
???
????????????Attach(t1->coef,?t1->expon,?&rear);??
????????????t1?=?t1->link;??
????????}??
????????else??
????????{??
????????????Attach(t2->coef,?t2->expon,?&rear);??
????????????t2?=?t2->link;??
????????}??
????}??
????while(t1)//如果t1还有多余节点，则继续加入???
????{??
????????Attach(t1->coef,?t1->expon,?&rear);??
????????t1?=?t1->link;??
????}??
????while(t2)//如果t2还有多余节点，则继续加入???
????{??
????????Attach(t2->coef,?t2->expon,?&rear);??
????????t2?=?t2->link;??
????}??
????t?=?P;??
????P?=?P->link;??
????free(t);//释放头节点???
????return?P;??
}??
??
void?PrintPoly(Polynomial?P)??
{??
????printf("多项式运算结果为:\n");???
????int?flag?=?0;??
????if(!P)??
????{??
????????printf("0?0\n");??
????????return;??
????}??
????while(P)??
????{??
????????if(!flag)??
????????????flag?=?1;??
????????else??
????????????printf("?");??
????????printf("%d**%d",P->coef,?P->expon);??
????????P?=?P->link;???????
????}??
????printf("\n");??
}??
|