2.4一元多项式的表示及相加
下面來(lái)講解下一元多項(xiàng)式，第一個(gè)問(wèn)題，我們?yōu)槭裁床挥镁€性表，我們知道棧區(qū)是很小的，很多編譯器都默認(rèn)1MB左右，如下面的代碼：
#include <stdio.h>int main() {char arr[1024*1024];return 0; }這時(shí)的運(yùn)行結(jié)果為：
上面提示 Stack Overflow，也就是棧溢出，所以當(dāng)我們要存S(x)=1+3*x^9999999+2*x^999999999999
這類很大指數(shù)的數(shù)據(jù)時(shí)，第一是浪費(fèi)很多空間，第二是很有可能會(huì)棧溢出。
所以一般用線性鏈表來(lái)表示。
比如表示A(x)=7+3*x+9*x^8+5*x^17和B(x)=8*x+22*x^7-9*x^8，這時(shí)用鏈表可以節(jié)省很多空間（堆區(qū)很大的）
如下圖所示：
我們還是先來(lái)說(shuō)明下一元多項(xiàng)式相加的運(yùn)算規(guī)則：對(duì)于兩個(gè)一元多項(xiàng)式中所有指數(shù)相同的項(xiàng)，對(duì)應(yīng)系數(shù)相加，若其和不為0，則構(gòu)成“和多項(xiàng)式”中的一項(xiàng)；對(duì)于兩個(gè)一元多項(xiàng)式中的所有指數(shù)不相同的項(xiàng)，則分別復(fù)抄到“和多項(xiàng)式”中去。
這里我們對(duì)上面那個(gè)A(x)=7+3*x+9*x^8+5*x^17和B(x)=8*x+22*x^7-9*x^8做和運(yùn)算說(shuō)明下：
看那個(gè)節(jié)點(diǎn)多，節(jié)點(diǎn)少的插入節(jié)點(diǎn)多的那個(gè)鏈，相同的話，隨便。
A(x)=7+3*x+9*x^8+5*x^17和B(x)=8*x+22*x^7-9*x^8這個(gè)相加如下圖所示：
下面來(lái)看指數(shù)的比較：
代碼如下：
int Compare(PElemType a, PElemType b) {if (a.expn<b.expn) return -1;if (a.expn>b.expn) return 1;return 0; } 分析如下：這里的expn為指數(shù)(接下來(lái)的代碼有coef這個(gè)是系數(shù))。但a>b則返回-1，a<b返回1,相等時(shí)返回0
代碼如下：
void CreatPolyn(PLinkList &P, int m) { // 輸入m項(xiàng)的系數(shù)和指數(shù)，建立表示一元多項(xiàng)式的有序鏈表PPLink h, q, s;PElemType e;int i;InitList(P); h = GetHead(P);e.coef = 0.0; e.expn = -1;SetCurElem(h,3); //設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素for(i=1;i<=m;++i){scanf(e.coef,e.expn);if(!LocateElem(P,e,q,(*cmp)()))//是否存在該指數(shù)項(xiàng){if(MakeNode(s,e))//生成節(jié)點(diǎn)InsFirst(q,s); //插入}} } // CreatPolyn我們來(lái)分析下：
1.m為要輸入的相數(shù)。
2.InitList為初始化鏈表，SetCurElem如注釋所示。
3.這個(gè)代碼的思路是從鍵盤輸入項(xiàng)，但如果輸入兩次相同指數(shù)的話，就有第一次輸入有效。
多項(xiàng)式加法：Pa=Pa+Pb，利用兩個(gè)多項(xiàng)式的結(jié)點(diǎn)構(gòu)成“和多項(xiàng)式”。
這個(gè)代碼涉及很多函數(shù)并且書(shū)中都沒(méi)提及，下面我只說(shuō)下思路，用兩個(gè)指針指向兩個(gè)鏈表頭，又用兩個(gè)指針，分別指向兩個(gè)鏈表第一個(gè)節(jié)點(diǎn)。這個(gè)功能是保留Pa的鏈，在case -1 里面，當(dāng)發(fā)現(xiàn)Pa和Pb的指數(shù)不一樣時(shí)（這里是Pa的指數(shù)小，所以Pa后移，移到Pa和Pb指數(shù)一樣為止），case 0，就是合并，case 1，就是把Pb當(dāng)前節(jié)點(diǎn)給Pa，最后當(dāng)qa也就是Pa鏈到結(jié)尾，但Pb還沒(méi)到鏈尾時(shí)，把Pb直接附加到Pa上。這就是整體思路。
總結(jié)
以上是生活随笔為你收集整理的2.4一元多项式的表示及相加的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： C/C++信息隐写术（一）之认识文件结构
- 下一篇： linux模块创建proc,[Linux