/*一元多项式的基本操作*/
//定义一个结构体作为链表节点，以存储多项式中的第一项并建立相应的链表
typedef struct node
{
float coef;//系数
int exp;//指数
struct node *next;//指向下一个结点
} LinkNode, *Link;
/*
/*初始条件：一元多项式P已存在
/* 操作结果：将新的节点s插入到现有链表的后面，并确保是降序
*/
void insert(Link head,Link s, boolean check)
{
Link pre=NULL,p=NULL;
pre=head;
p=pre->next;
while(p!=NULL) {
if(check && (p->exp > s->exp)) break;//如果新节点的幂大于
pre=p;
p=p->next;
}
s->next=p;
pre->next=s;
}
/*
* 操作结果：创建新的多项式链表
*/
Link createPolynomial()
{
Link head=NULL, s=NULL;
float co;
int last=-1, ex,flag=0;
head=(Link)malloc(sizeof(LinkNode));
head->next=NULL;
do {
printf("\n系数a(输入0退出程序)# ");
scanf("%f",&co);
if (co==0) flag=1;
if (flag==0) {
printf("指数e(必须大于 %d)# ", last);
scanf("%d",&ex);
if(ex <= last) continue; // 如果新输入的指数小于最后输入的，则不作任何操作，进入下一轮循环
last=ex;
s=(Link)malloc(sizeof(LinkNode));
s->coef = co;
s->exp=ex;
//insert(head,s);
insert(head, s, TRUE);
}
} while(flag==0);
return(head);
}
/*
/*初始条件：一元多项式P已存在
*操作结果：从一个给定链表中删除指定节点
*主要用于辅助destroy() 函数
*/
void _del(Link *p,Link pa)
{
(*p)->next = pa->next;
free(pa);
}
/*
/*
/*初始条件：一元多项式P已存在
* 操作结果：销毁链表，以及时释放被占用的内存
*原理：将链表中的节点依次删除
*/
void destroy(Link *p)
{
while((*p)->next != NULL)
_del(p,(*p)->next);
free(*p);
}
/*
/*初始条件：一元多项式P已存在
/* 操作结果：确定一个链表是否为空
* 原理：如果头节点指向一个空值，即NULL，则表示该链表为空
* @return boolean, 如果为空则返回TRUE， 否则返回FALSE
*/
boolean isBlank(Link p) {
if(p->next == NULL) {
return OK;
}
return FALSE;
}
/*
/*初始条件：一元多项式P已存在
* 操作结果：复制一个链表，将返回该新链表的头指针，以免对在运行的时候改变原链表
* 从而影响继计算
* 原理：获取原结点中每个结点的值，并插入到新的链表中
* 返回：一个按升幂排列的多项式
*/
Link copyList(Link head) {
Link node = NULL, newHead = NULL;
newHead = (Link) malloc(sizeof(LinkNode));
newHead->next = NULL;
head = head->next;
while (head != NULL) {
node = (Link) malloc(sizeof(LinkNode));
node->coef = head->coef;
node->exp = head->exp;
//insert(newHead, node);
insert(newHead, node, TRUE);
head = head->next;
}
return newHead;
}
/*
/*初始条件：一元多项式P已存在
* 操作结果：将指定链表逆序
* 主要用于辅助乘除运算
*/
Link reverse(Link head)
{
LinkNode *p,*q,*t;
p=NULL;
q=head->next;
while( q!=NULL ) {
t=q->next;
q->next =p;
p=q;
q=t;
}
head->next =p;
return head;
}
/*
/*初始条件：一元多项式P已存在
* 操作结果：实现两个多项式想加，并将计算结果存储于pa中
*原理：将指数相同的项的系数加
* pa, 与pb的幂次序都要求是升序，否则可能得到错误的结果
*/
void addPoly(Link pa,Link pb)
{
Link pc,pre,u;
float sum;
pc=pa;
pre=pa;
pa=pa->next;
u=pb;
pb=pb->next;
free(u);
while(pa && pb) {
if (pa->exp < pb->exp) {//如果当前pa的幂小于pb则指向pa中的下一个节点
pre=pa;
pa=pa->next;
} else if (pa->exp > pb->exp) {
u=pb->next;
pb->next=pa;
pre->next=pb;
pre=pb;
pb=u;
} else {
sum = pa->coef + pb->coef;//指数相加
if(sum!=0.0) {
pa->coef = sum;
pre=pa;
} else {
pre->next = pa->next;
free(pa);
}
pa=pre->next;
u=pb;
pb=pb->next;
free(u);
}
}
if(pb) pre->next = pb;
}//End addPoly
/*
/*初始条件：一元多项式P已存在
*操作结果：实现两个多项式相减
* 原理：与加法类似，将指数相同的指数相减
*/
Link subtractPoly(Link pa,Link pb)
{
Link pc,pre,u, newNode = NULL, newHead = NULL;
float minus;
pc = pa;
pre = pa;
pa = pa->next;
u = pb;
pb = pb->next;
free(u);
//创建一个新的链表以存储新相减的结果
newHead = (Link) malloc(sizeof(LinkNode));
newHead->next = NULL;
while(pa && pb) {
if (pa->exp < pb->exp) {//如果当前pa的指数小于pb的指数，则将该pa节点存储于将的链表中
newNode = (Link) malloc (sizeof(LinkNode));
newNode->coef = pa->coef;
newNode->exp = pa->exp;
//insert(newHead, newNode);
insert(newHead, newNode, TRUE);
pre = pa;
pa = pa->next;
} else if (pa->exp > pb->exp) {//如果当前pa的指数大于pb的指数，则将该pb节点存储于将的链表中
minus = -pb->coef;
newNode = (Link) malloc (sizeof(LinkNode));
newNode->coef = minus;
newNode->exp = pb->exp;
//insert(newHead, newNode);
insert(newHead, newNode, TRUE);
u = pb->next;
pb->next = pa;
pre->next = pb;
pre = pb;
pb = u;
} else {//如果相等，则将系数相减
minus = pa->coef - pb->coef;
if(minus!=0.0) {//判断相减的结果是否为0
newNode = (Link) malloc (sizeof(LinkNode));
newNode->coef = minus;
newNode->exp = pa->exp;
//insert(newHead, newNode);
insert(newHead, newNode, TRUE);
pre=pa;
} else {//如果为0则不作任何操作
pre->next = pa->next;
free(pa);
}
pa = pre->next;
u = pb;
pb = pb->next;
free(u);
}
}
pre = pb ? pb : (pa ? pa : NULL);//判断pa或pb是否完成
if(pre) {
while(pre) {
newNode = (Link) malloc (sizeof(LinkNode));
newNode->coef = pb ? -pre->coef : pre->coef;
newNode->exp = pre->exp;
//insert(newHead, newNode);
insert(newHead, newNode, TRUE);
pre = pre->next;
}
}
return newHead;
}
/*
/*初始条件：一元多项式P已存在
* 操作结果：实现两个多项式相乘，A(X) * B(x)
*/
Link multiplyPolynomial(Link A,Link B)
{
LinkNode *pa, *pb, *pc, *u, *head;
int k , maxExp;
float coef;
//The head node of the multiply
head = (Link) malloc( sizeof (LinkNode) );
if(head==NULL) {
printf("Allocable memory fail!\n");
return NULL;
}
head->coef=0.0;
head->exp =0;
head->next =NULL;
//将多项式链表按降序排列，如4X^3 + 3X^2 + 2X^1 + 19
reverse(A);
reverse(B);
if(A && B) { //获得两个多项式相乘后的度
maxExp=(A->next)->exp + (B->next)->exp;
} else {
return head;
}
pc=head;
B=reverse (B);
for(k=maxExp; k>=0; k--) {
pa = A->next ;
while(pa != NULL && pa->exp > k) {
pa=pa->next ;
}
pb = B->next ;
while( pb != NULL && pa != NULL && (pa->exp + pb->exp) < k ) {
pb=pb->next;
}
coef=0.0;
while(pa != NULL && pb != NULL ) {
if( (pa->exp +pb->exp )==k ) {
coef+=pa->coef * pb->coef;
pa=pa->next;
pb=pb->next;
} else {
if(( pa->exp + pb->exp ) > k ) {
pa=pa->next;
} else {
