f(X)=1+x+x2+x5

g(X)=x3+x6+x8+x100

f(X)+g(X)=1+x+x2+x3+x5+x6+x8+x100

兩個(gè)有序多項(xiàng)式相加合并問(wèn)題：?

顯然第一個(gè)想到的是用數(shù)組解決，可仔細(xì)想一想，數(shù)組有諸多弊端，比如大量空間浪費(fèi)，無(wú)法同時(shí)存儲(chǔ)系數(shù)和指數(shù)（當(dāng)然可以用結(jié)構(gòu)體數(shù)組，但那不還是鏈表嗎），插入刪除都需移動(dòng)大量數(shù)據(jù)，索性，就用單鏈表解決吧

思路如下：

1）將f(X)和g(X)分別存儲(chǔ)在兩個(gè)單向鏈表內(nèi)，每個(gè)節(jié)點(diǎn)存儲(chǔ)多項(xiàng)式的一項(xiàng)，內(nèi)含系數(shù)和指數(shù)，并指向下一項(xiàng)節(jié)點(diǎn)，連貫成一個(gè)多項(xiàng)式，頭結(jié)點(diǎn)分別是head1,和head2；

2)接下來(lái)就是兩個(gè)多項(xiàng)式合并同類項(xiàng)了（初中貌似最喜歡做這玩意了，可計(jì)算機(jī)可不如你啊），用Node?*p1=head->next;?指向f(X)的第一個(gè)項(xiàng)節(jié)點(diǎn)（head節(jié)點(diǎn)均為無(wú)數(shù)據(jù)的表頭），

Node?*p2=head->next;指向g(X)的的一項(xiàng)；?在定義兩個(gè)指針pre1=head1、pre2=head2（一會(huì)兒有用），準(zhǔn)備工作基本做完了。

3）此算法的關(guān)鍵在于將兩個(gè)有序鏈表合并成一個(gè)，并依然有序；只需將f(X)看成主串，g(X)看成插入串即可，遍歷g(X)的各節(jié)點(diǎn)，比較其與f(X)各節(jié)點(diǎn)指數(shù)的大小，小的就插在前面，大的話指針p1就往后移，相等就合并，如果f(X)先遍歷到結(jié)尾，說(shuō)明g(X)的其余項(xiàng)都比f(wàn)(X)的最后一項(xiàng)的指數(shù)大，只需將f(X)的最后一個(gè)節(jié)點(diǎn)指向g(x)的剩余節(jié)點(diǎn)即可，最后別忘了把head2刪了，因?yàn)樗莻€(gè)沒(méi)有數(shù)據(jù)的節(jié)點(diǎn)。

好了還是上代碼吧：

#include<iostream>
using?namespace?std;

typedef?struct?node
{
????int?coe;?????//系數(shù)
????int?exp;?????//指數(shù)
????struct?node?*next;
}Node;
/生成鏈表
Node?*Create()
{
????Node?*head=new?Node;
????head->next=NULL;
????Node?*p=head;
????int?n;???????????//項(xiàng)數(shù)
????cout<<"N:";
????cin>>n;
????for(int?i=0;i<n;i++)
????{
??????p->next=new?Node?;
??????p=p->next;
??????cin>>p->coe>>p->exp;
??????p->next=NULL;

????}
????return?head;
}

int?main()
{
????Node?*head1=Create();
????Node?*head2=Create();
????Node?*p1=head1->next,*p2=head2->next;
????Node?*pre1=head1,*pre2=head2;?????//pre1指針用來(lái)指向比較節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
??????????????????????????????????????//pre2指針用作temp
????while(p1?&&?p2)
????{
????????if(p1->exp?<?p2->exp)
????????{
????????????pre1=p1;
????????????p1=p1->next;
????????}
????????else?if(p1->exp?>?p2->exp)
????????{
????????????pre1->next=p2;
????????????pre2=p2->next;
????????????p2->next=p1;
????????????p2=pre2;
????????????pre1=pre1->next;
????????}
????????else?if(p1->exp?==?p2->exp)
????????{
????????????p1->coe+=p2->coe;
????????????pre2=p2;
????????????p2=p2->next;
????????????delete?pre2;
????????}

????}
????if(p1==NULL)
????{
???????pre1->next=p2;
????}
????delete?head2;
???Node?*temp=head1->next;
???while(temp)
???{
??????cout<<temp->coe<<'X'<<'('<<temp->exp<<')'<<"?";
??????temp=temp->next;
????}
????return?0;

}?

?

轉(zhuǎn)載于:https://www.cnblogs.com/gavindlutsw/archive/2011/09/24/2189784.html

總結(jié)

以上是生活随笔為你收集整理的链表应用——多项式相加的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。