輸入格式:
輸入在第一行給出第一個多項式POLYA的系數(shù)和指數(shù)，并以0,0 結(jié)束第一個多項式的輸入；在第二行出第一個多項式POLYB的系數(shù)和指數(shù)，并以0,0 結(jié)束第一個多項式的輸入。
輸出格式:
對每一組輸入，在一行中輸出POLYA+POLYB和多項式的系數(shù)和指數(shù)。
輸入樣例:
5,0 2,1 1,6 8,15 0,0
-2,1 3,6 4,8 0,0
輸出樣例:
5,0 4,6 4,8 8,15 本題主要思路；
1.建立兩個頭指針分別為head1和head2鏈表，鏈表每一個節(jié)點分別記錄每一個多項式的系數(shù)coef和指數(shù)exp.
2.preA遍歷鏈表head1,preB遍歷鏈表head2.
3.建立一個只有一個頭節(jié)點的鏈表head,逐步遍歷鏈表head1和head2.分別有如下三種情況
①preA->expexp,將節(jié)點preA利用尾插法插入鏈表head。
②preB->expexp,將節(jié)點preB利用尾插法插入鏈表head.
③preB->exp=preA->exp,這種情況分為兩種
當(dāng)preA->coef+preB->coef=0時：
釋放節(jié)點preA和preB.
當(dāng)preA->coef+preB->coef≠0時：
將多項式系數(shù)相同的項的指數(shù)相加，記錄在preA,并利用尾插法將preA節(jié)點插如鏈表head.
相加的代碼如下
?文章來源地址http://www.zghlxwxcb.cn/news/detail-733744.html
void Add_Poly(PNode pa,PNode pb)
{
PNode p = pa->next; //鏈表1，和多項式的結(jié)果放在鏈表1中
PNode q = pb->next;
PNode pre = pa;
PNode u;
float x; //臨時變量
while(p != NULL && q != NULL)
{
if(p->exp < q->exp)
{
//比較鏈表1和鏈表2當(dāng)前節(jié)點的指數(shù)大小，鏈表1也是存放結(jié)果的地方
pre = p;
p = p->next;
//p指向要比較的下一個節(jié)點，pre指向結(jié)果鏈表的最后一個節(jié)點
}
else if(p->exp == q->exp)
{
//假如鏈表1和鏈表2的指數(shù)相等，則要系數(shù)相加
x = p->coef + q->coef;
if(x != 0)
{
//相加后的系數(shù)不是0，保留上一個節(jié)點就好了
p->coef = x;
pre = p;
}
else
{
//相加后系數(shù)為0，不需要保留任何一個節(jié)點，刪除鏈表1的節(jié)點
pre->next = p->next;
free(p);
}
p=pre->next; //p指向下一個節(jié)點
//下面是進行鏈表2的刪除工作
u = q;
q = q->next;
free(u);
}
else
{
//如果鏈表2當(dāng)前節(jié)點指數(shù)小，把鏈表2的當(dāng)前節(jié)點加入到鏈表1中
u = q->next;
q->next = p;
pre->next = q;
pre = q;
q = u;
}
}
if(q)
{
//如果鏈表2比鏈表1長，那么需要把鏈表2多余的部分加入到結(jié)果鏈表中
//如果鏈表1比鏈表2長，則不需要任何操作
pre->next = q;
}
free(pb);
} 完整代碼如下：
#include<stdio.h>
#include<stdlib.h>
struct tagNode
{
float coef; //系數(shù)
int exp; //指數(shù)
struct tagNode *next; //指針域
};
typedef struct tagNode Node;
typedef struct tagNode *PNode;
void insertList(PNode head,PNode pnode)
{
PNode pPre = head;
while(pPre->next != NULL)
{
if(pPre->next->exp>pnode->exp)
{
pnode->next = pPre->next;
pPre->next = pnode;
break;
}
else
{
pPre = pPre->next;
}
}
if(pPre->next == NULL)
{
pPre->next = pnode;
}
}
void CreateList(PNode head)
{
int exp;
float coef;
PNode pTemp = NULL;
head->next = NULL;
scanf("%f,%d",&coef,&exp);
while(coef != 0 || exp != 0)
{
pTemp = (PNode)malloc(sizeof(struct tagNode));
pTemp->coef = coef;
pTemp->exp = exp;
pTemp->next = NULL;
insertList(head,pTemp);
scanf("%f,%d",&coef,&exp);
}
}
void printLinkedList(PNode head)
{
PNode temp = head->next;
while(temp != NULL)
{
printf("%0.0f,",temp->coef);
printf("%d ",temp->exp);
temp = temp->next;
}
printf("\n");
}
void Add_Poly(PNode pa,PNode pb)
{
PNode p = pa->next; //鏈表1，和多項式的結(jié)果放在鏈表1中
PNode q = pb->next;
PNode pre = pa;
PNode u;
float x; //臨時變量
while(p != NULL && q != NULL)
{
if(p->exp < q->exp)
{
//比較鏈表1和鏈表2當(dāng)前節(jié)點的指數(shù)大小，鏈表1也是存放結(jié)果的地方
pre = p;
p = p->next;
//p指向要比較的下一個節(jié)點，pre指向結(jié)果鏈表的最后一個節(jié)點
}
else if(p->exp == q->exp)
{
//假如鏈表1和鏈表2的指數(shù)相等，則要系數(shù)相加
x = p->coef + q->coef;
if(x != 0)
{
//相加后的系數(shù)不是0，保留上一個節(jié)點就好了
p->coef = x;
pre = p;
}
else
{
//相加后系數(shù)為0，不需要保留任何一個節(jié)點，刪除鏈表1的節(jié)點
pre->next = p->next;
free(p);
}
p=pre->next; //p指向下一個節(jié)點
//下面是進行鏈表2的刪除工作
u = q;
q = q->next;
free(u);
}
else
{
//如果鏈表2當(dāng)前節(jié)點指數(shù)小，把鏈表2的當(dāng)前節(jié)點加入到鏈表1中
u = q->next;
q->next = p;
pre->next = q;
pre = q;
q = u;
}
}
if(q)
{
//如果鏈表2比鏈表1長，那么需要把鏈表2多余的部分加入到結(jié)果鏈表中
//如果鏈表1比鏈表2長，則不需要任何操作
pre->next = q;
}
free(pb);
}
int main()
{
PNode head1 = (PNode)malloc(sizeof(struct tagNode));
PNode head2 = (PNode)malloc(sizeof(struct tagNode));
CreateList(head1);
CreateList(head2);
Add_Poly(head1,head2);
printLinkedList(head1);
return 0;
}
測試結(jié)果如下：
?
?文章來源：http://www.zghlxwxcb.cn/news/detail-733744.html
?
到了這里，關(guān)于用鏈表表示多項式，并實現(xiàn)多項式的加法運算的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
