1、數(shù)據(jù)結(jié)構(gòu)鏈表應(yīng)用一元多項(xiàng)式運(yùn)算院系：信息工程學(xué)院組號(hào)：2組員：田志澤、孫偉偉、程蜜蜜張劍、賈明、王忠愿班級(jí)：10計(jì)科3班B組日期：20120322計(jì)算機(jī)科學(xué)與技術(shù)一元多項(xiàng)式運(yùn)算功能具體實(shí)現(xiàn)部分#include應(yīng)用數(shù)據(jù)結(jié)構(gòu)SimpleLinkList.h需將線性鏈表SimpleLinkList包含在內(nèi)structPolyDatadoublecoef;intexpn;PolyData()coef=0;expn=0;PolyData(doublec,inte)coef=c;expn=e;/一元多項(xiàng)式的數(shù)據(jù)部分結(jié)構(gòu)定義/系數(shù)/指數(shù)classPolynomialprotected:SimpleLinkL

2、istPoly;定義一元多項(xiàng)式類將一元多項(xiàng)式定義為線性鏈表結(jié)構(gòu)public:Polynomial();voidvoidvoidvoidvoidvoidvoidADD(Polynomial&p.Polynomial&q);SUB(Polynomial&p.Polynomial&q);MUL(Polynomial&p,Polynomial&q);operator=(Polynomial&cp)Poly=cp.Poly;Sort();Unit();Show();實(shí)現(xiàn)一元多項(xiàng)式的加法運(yùn)算實(shí)現(xiàn)一元多項(xiàng)式的減法運(yùn)算實(shí)現(xiàn)一元多項(xiàng)式的乘法運(yùn)算實(shí)現(xiàn)一元多項(xiàng)式的復(fù)制運(yùn)算將一元多項(xiàng)式按指數(shù)由小到大排列friendv

3、oidCinhelp();/以Sort()為基礎(chǔ)合并多項(xiàng)式中指數(shù)相同的項(xiàng)并清除系數(shù)為0的項(xiàng)實(shí)現(xiàn)多項(xiàng)式的輸出顯示輔助輸入;將當(dāng)前多項(xiàng)式的鏈表請(qǐng)空將得鏈表直接添加到當(dāng)前鏈表中對(duì)當(dāng)前鏈表進(jìn)行并項(xiàng)去零操作將當(dāng)前多項(xiàng)式的鏈表請(qǐng)空將得鏈表直接添加到當(dāng)前鏈表中對(duì)當(dāng)前鏈表進(jìn)行并項(xiàng)去零操作voidPolynomial:ADD(Polynomial&p,Polynomial&q)Poly.Clear();Poly.ADD(p.Poly,q.Poly);Sort();voidPolynomial:SUB(Polynomial&p.Polynomial&q)PolyDatae;Polynomialtmp;while(

4、tmp.Poly.length()q.Poly.length()q.Poly.GetElem(tmp.Poly.length()+1,e);e.coef=-e.coef;tmp.Poly.SetElem(e);ADD(p,tmp);依次取岀q中的每一個(gè)元素對(duì)取得的元素取相反數(shù)依次寫入到tmp中，完成后得-q調(diào)用ADD實(shí)現(xiàn)p-q功能voidPolynomial:MUL(Polynomial&p.Polynomial&q)Poly.Clear();inti=1,j;PolyDatae,ei,ej;while(i=p.Poly.length()p.Poly.GetElem(i,ei);j=1;i+;

5、while(j=q.Poly.length()q.Poly.GetElem(j,ej);e.coef=ei.coef*ej.coef;e.expn=ei.expn+ej.expn;Poly.SetElem(e);j+;voidPolynomial:Sort()inti=1,j;PolyDataei,ej;while(i=Poly.length()-1)Poly.GetElem(i,ei);j=i+1;while(jej.expn)將當(dāng)前多項(xiàng)式的鏈表請(qǐng)空取岀p中的每一個(gè)元素取岀q中的每一個(gè)元素產(chǎn)生的新項(xiàng)的系數(shù)為pq兩項(xiàng)系數(shù)相乘產(chǎn)生的新項(xiàng)的指數(shù)為pq兩項(xiàng)指數(shù)相加將產(chǎn)生的新項(xiàng)存入當(dāng)前多項(xiàng)式的鏈表中將

6、當(dāng)前多項(xiàng)式的鏈表請(qǐng)空取岀p中的每一個(gè)元素取岀q中的每一個(gè)元素產(chǎn)生的新項(xiàng)的系數(shù)為pq兩項(xiàng)系數(shù)相乘產(chǎn)生的新項(xiàng)的指數(shù)為pq兩項(xiàng)指數(shù)相加將產(chǎn)生的新項(xiàng)存入當(dāng)前多項(xiàng)式的鏈表中取出當(dāng)前多項(xiàng)式鏈表中的每一個(gè)元素/與當(dāng)前元素之后的每一個(gè)元素今次那個(gè)比較若當(dāng)前元素的指數(shù)大于其后的某一個(gè)元素時(shí)/交換兩個(gè)元素Poly.ReSetElem(i,ej);Poly.ReSetElem(j,ei);ei=ej;/對(duì)應(yīng)的兩項(xiàng)交換后，將i項(xiàng)當(dāng)前值更新j+;i+;voidPolynomial:Unit()inti=1;/獲取第一項(xiàng)的數(shù)據(jù)部分PolyDataei,ej;Poly.GetElem(i,ei);while(i=Poly.

7、length()-1)Poly.GetElem(i+1,ej);if(ei.coef=0)Poly.DelElem(i);ei=ej;/獲取后一項(xiàng)的數(shù)據(jù)部分當(dāng)?shù)趇個(gè)元素的系數(shù)為0時(shí)將該項(xiàng)清除當(dāng)?shù)趇+1個(gè)元素的系數(shù)為0時(shí)將該項(xiàng)清除/判斷相鄰兩項(xiàng)的指數(shù)部分是否相同兩部分系數(shù)之和為0,則將這兩項(xiàng)刪除elseif(ej.coef=0)Poly.DelElem(i+1);elseif(ei.expn=ej.expn)if(ei.coef+ej.coef=0)Poly.DelElem(i+1);Poly.DelElem(i);Poly.GetElem(i,ei);else/系數(shù)之和不是ei.coef+=e

8、j.coef;Poly.ReSetElem(i,ei);Poly.DelElem(i+1);elsei+;ei=ej;/兩個(gè)元素都刪除后對(duì)ei賦新值0,兩項(xiàng)合并到i將第i+1項(xiàng)刪除將指數(shù)相同的兩項(xiàng)合并到第i項(xiàng)中重置第i項(xiàng)刪除第i+1項(xiàng)/當(dāng)指數(shù)不相同時(shí)轉(zhuǎn)至下一個(gè)元素/比較下一項(xiàng)為ei依次裝入后繼元素voidPolynomial:Show()inti=1;PolyDataelem;Poly.GetElem(i,elem);if(elem.coef=0);elseif(elem.expn=0)while(i0)coutelem.coef;elsecout-0)if(elem.coef!=1)cout

9、elem.coef;couta;elsecout-;if(elem.coef!=-1)cout-elem.coef;cout0)if(elem.coef=1)coutaA;elsecoutvelem.coefvvavvA;if(elem.expnO)coutv(velem.expn);當(dāng)指數(shù)小于0時(shí)加一個(gè)括號(hào)elsecoutelem.expn;else系數(shù)小于0且指數(shù)不為0時(shí)if(elem.coef=-1)cout-aA;elsecout-elem.coefaA；if(elem.expn0)coutv(velem.expn);elsecoutelem.expn;if(i+10)cout+;i+

10、;當(dāng)后一個(gè)元素的系數(shù)為正數(shù)時(shí)輸岀一個(gè)+號(hào)coutendl;voidCinhelp()PolynomialA,B,C;intchoice=1,pos;doubleelemd;intelemi;while(choice)coutendl請(qǐng)選擇一元多項(xiàng)式相關(guān)操作:endlendl1.輸入兩個(gè)一元多項(xiàng)式2兩多項(xiàng)式相加3兩多項(xiàng)式相減4兩多項(xiàng)式相乘endlendlchoice;switch(choice)case1:coutendl當(dāng)前第一個(gè)多項(xiàng)式中有A.Poly.length()pos;choice=A.Poly.length();coutendl請(qǐng)依次輸入多項(xiàng)式的vvposvv個(gè)項(xiàng)，系數(shù)和指數(shù)交替輸入

11、空格間隔Enter確認(rèn):elemdelemi;PolyDataelem(elemd,elemi);Poly.SetElem(elem);coutendl第一個(gè)多項(xiàng)式為：endl;Show();coutendl當(dāng)前第二個(gè)多項(xiàng)式中有B.Poly.length()pos;choice=B.Poly.length();coutendl請(qǐng)依次輸入多項(xiàng)式的vvposvv個(gè)項(xiàng)，系數(shù)和指數(shù)交替輸入空格間隔Enter確認(rèn):endl;while(B.Poly.length()elemdelemi;PolyDataelem(elemd,elemi);Poly.SetElem(elem);coutendlvv第二個(gè)多

12、項(xiàng)式為：endl;Show();break;case2:case2:Sort();A.Unit();coutendl第一個(gè)多項(xiàng)式規(guī)格化后為：endl;A.Show();Sort();B.Unit();coutendl第二個(gè)多項(xiàng)式規(guī)格化后為：endl;B.Show();coutendl兩多項(xiàng)式相加endl;ADD(A,B);cout=;C.Show();coutendl;choice=C.Poly.length();Unit();if(choice!=C.Poly.length()當(dāng)有項(xiàng)消去時(shí)輸岀該部分cout=;C.Show();coutendl當(dāng)前多項(xiàng)式中有C.Poly.length()個(gè)元

13、素項(xiàng);coutendl;break;case3:case3:Sort();A.Unit();coutendl第一個(gè)多項(xiàng)式規(guī)格化后為：endl;Show();Sort();B.Unit();coutendl第二個(gè)多項(xiàng)式規(guī)格化后為：endl;Show();coutendl多項(xiàng)式一減多項(xiàng)式二endl;SUB(A,B);cout=;C.Show();coutendl;choice=C.Poly.length();Unit();if(choice!=C.Poly.length()當(dāng)有項(xiàng)消去時(shí)輸岀該部分cout=;C.Show();coutendl當(dāng)前多項(xiàng)式中有C.Poly.length()個(gè)元素項(xiàng);co

14、utendl;case4:break;Sort();A.Unit();coutendl第一個(gè)多項(xiàng)式規(guī)格化后為：endl;Show();Sort();B.Unit();coutendl第二個(gè)多項(xiàng)式規(guī)格化后為：endl;Show();coutendl兩多項(xiàng)式乘endl;MUL(A,B);cout=;C.Show();coutendl;Sort();cout=;C.Show();coutendl;choice=C.Poly.length();Unit();if(choice!=C.Poly.length()/當(dāng)有項(xiàng)消去時(shí)輸岀該部分coutvv=;C.ShowO;coutendlvv當(dāng)前多項(xiàng)式中有C.

15、Poly.length()個(gè)元素項(xiàng);coutendl;break;coutendlchoice;coutendlendlendl;voidmain()主函數(shù)調(diào)用部分Cinhelp();一元多項(xiàng)式運(yùn)算功能輸入截圖：請(qǐng)選擇一元多項(xiàng)式相關(guān)操作：二輸入兩個(gè)一元多項(xiàng)式2兩多項(xiàng)式相加勺”兩多項(xiàng)式相減4兩多項(xiàng)式相乘請(qǐng)依次輸入多項(xiàng)式的4個(gè)項(xiàng)，系數(shù)和指數(shù)交替輸入空格間隔Entor確認(rèn)：12453220第一個(gè)多項(xiàng)式為：十2*5篤*2*2請(qǐng)依次輸入多項(xiàng)式的3個(gè)項(xiàng).系數(shù)和指數(shù)交替輸入空格間隔Enter確認(rèn)二15315264第二個(gè)多項(xiàng)式為：比廿*3歌*與盤幾2第一個(gè)多項(xiàng)式規(guī)格化后為2+4宀+4aS第二個(gè)多項(xiàng)式規(guī)格化后為

16、；3a+5aA2+戰(zhàn)5一元多項(xiàng)式運(yùn)算功能結(jié)果輸出截圖:旨多項(xiàng)式相加=2+3a+4*2+5日7+4aA5+5=2+3a+9aA2+5aA5當(dāng)前多項(xiàng)式中有4個(gè)元素項(xiàng)多項(xiàng)式一減多項(xiàng)式二=2-3a+4aA2-5aA2+4a5-2-3a-a2+3aA5兩多項(xiàng)式乘=6a+10aA2+2aA5+12aA3+20aA4+4aA7+12aA6+20a+4al0=6a*10aA2+12a3+20aA4+2aA5+12a%+4aA7+20aA?+4al0=6a*102+12a3+2Ba4+2*5+126+24aA7+4sia10當(dāng)前多項(xiàng)式中有8個(gè)元素項(xiàng)/以部分為頭文件SimpleLinkList.h部分，用該部分替

17、換頂部的SimpleLinkList.h可實(shí)現(xiàn)一元多項(xiàng)式功能#include/結(jié)點(diǎn)類模板templatevclassETstructnodeETdata;點(diǎn)的數(shù)據(jù)部分node*next;個(gè)節(jié)點(diǎn)的位置node()next=NULL;給定參數(shù)時(shí)結(jié)點(diǎn)的初始化node(ETdat,node*link)data=dat;next=link;數(shù)結(jié)點(diǎn)構(gòu)造函數(shù)，構(gòu)造給定數(shù)據(jù)和指針的結(jié)點(diǎn);/簡(jiǎn)單線性鏈表類Pag52templatevclassETclassSimpleLinkListprotected:intcount;素個(gè)數(shù)，即表長(zhǎng)node*head;置指針應(yīng)用數(shù)據(jù)結(jié)構(gòu)結(jié)點(diǎn)數(shù)據(jù)域，存儲(chǔ)該結(jié)結(jié)點(diǎn)指針域，指示下一

18、無參數(shù)結(jié)點(diǎn)構(gòu)造函數(shù)，用于未給定參用于計(jì)數(shù)表元順序表起始位public:SimpleLinkList()count=O;head=newnode;/簡(jiǎn)單線性鏈表構(gòu)造函數(shù)SimpleLinkList()Clear();deletehead;簡(jiǎn)單線性鏈表析構(gòu)函數(shù)簡(jiǎn)單線性鏈表相關(guān)操作0有元素boolEmpty()returncount=0;/voidClear();voidShow();表是否為空表清空，置元素個(gè)數(shù)為輸出現(xiàn)實(shí)表中現(xiàn)有的所node*GetPtr(intpostion);獲取指向第pos個(gè)位置節(jié)點(diǎn)的指針數(shù)加一voidSetElem(ET&e);/向表中末位寫入元素e，元素總voidReSe

19、tElem(intpos,ET&e);重置表中第pos個(gè)位置元素的數(shù)據(jù)部分為e,元素總數(shù)不變voidInsert(intpos,ET&e);素，元素總數(shù)加一向表中第pos個(gè)位置插入新的結(jié)點(diǎn)元voidGetElem(intpos,ET&e);從表中獲取第pos元素，寫入e中，由e輸岀voidDelElem(intpos);刪除表中第pos個(gè)位置的元素.元素減一voidoperator=(SimpleLinkList&cop);/賦值符重載函數(shù)，實(shí)現(xiàn)簡(jiǎn)單線性鏈表的復(fù)制功能voidSUB(SimpleLinkList&A,SimpleLinkList&B);/實(shí)現(xiàn)表相減，將僅存在于A中的元素寫入當(dāng)前

20、鏈表voidADD(SimpleLinkList&A,SimpleLinkList&B);/實(shí)現(xiàn)鏈表相加，將表A表B中的元素依次寫入當(dāng)前鏈表voidSeprate();奇偶分離函數(shù)，使得所有奇數(shù)均排列在偶數(shù)前voidSort();對(duì)鏈表中的元素進(jìn)行排序voidReserve();對(duì)線性鏈表逆序voidResHelp(int&tmp);線性鏈表逆序輔助函數(shù)voidCinHelp();提示輸入函數(shù)，用于實(shí)現(xiàn)鍵盤輸入交互式操作;templatevclassETvoidSimpleLinkList:Clear()while(count)DelElem(1);當(dāng)表中有元素時(shí)templatevclassE

21、TvoidSimpleLinkList:Show()intcot=count;ETtmp;node*shw=head;指向頭指針的第一個(gè)后繼coutendl當(dāng)前表中共有count個(gè)元素,endl0)shw=shw-next;tmp=shw-data;coutvvtmpvv;輸岀cot-;減一coutendl;當(dāng)表中有元素時(shí)每輸岀一位向后移動(dòng)一位將后繼的數(shù)據(jù)部分逐一計(jì)數(shù)元素總數(shù)templatevclassETnode*SimpleLinkList:GetPtr(intpostion)intpos=postion;node*ElemPtr;if(pos=0)returnhead;elseif(po

22、scount+1)coutendl操作無效！請(qǐng)確保輸入元素位置小于count+2大于等于0next;while(pos1)ElemPtr=ElemPtr-next;pos-;/不斷指向下一個(gè)結(jié)點(diǎn)，頭指針?biāo)谖恢脼榱鉹eturnElemPtr;templatevclassETvoidSimpleLinkList:SetElem(ET&e)node*prt=GetPtr(count);prt-next=newnode;的結(jié)點(diǎn)count+;在的元素，元素總數(shù)加一prt-next-data=e;獲取指向最后一個(gè)結(jié)點(diǎn)的指針將最后一個(gè)節(jié)點(diǎn)的后繼指向新置入表中不存將e寫入后繼結(jié)點(diǎn)的數(shù)據(jù)部分templatev

23、classETvoidSimpleLinkList:ReSetElem(intpos,ET&e)if(poscount)coutendl操作無效！請(qǐng)確保輸入元素位置小于count+1大于0data=e;重置表中元素，元素總數(shù)不變templatevoidSimpleLinkList:lnsert(intpos,ET&e)在第pos個(gè)位置插入一個(gè)新結(jié)點(diǎn)if(poscount+1)coutendl操作無效！請(qǐng)確保輸入元素位置小于count+2大于0endl;elsenode*prt=GetPtr(pos-1);node*pNext=prt-next;prt-next=newnode;的結(jié)點(diǎn)count

24、+;在的元素，元素總數(shù)加一prt-next-data=e;prt-next-next=pNext;的結(jié)點(diǎn)大于0endl;elsenode*prt=GetPtr(pos-1);node*pNext=prt-next;prt-next=newnode;的結(jié)點(diǎn)count+;在的元素，元素總數(shù)加一prt-next-data=e;prt-next-next=pNext;的結(jié)點(diǎn)獲取指向第pos-1個(gè)結(jié)點(diǎn)的指針獲取指向第pos個(gè)結(jié)點(diǎn)的指針將第pos-1個(gè)結(jié)點(diǎn)的后繼指向新置入表中不存將e寫入新結(jié)點(diǎn)的數(shù)據(jù)部分將新結(jié)點(diǎn)的后繼指向原來第pos個(gè)位置templatevoidSimpleLinkList:GetElem

25、(intpos,ET&e)if(poscount)coutendl操作無效！請(qǐng)確保輸入元素位置小于count+1大于0data;獲取指向第pos個(gè)結(jié)點(diǎn)的數(shù)據(jù)部分templatevoidSimpleLinkList:DelElem(intpos)刪除在第pos個(gè)位置的結(jié)點(diǎn)if(poscount)coutendl操作無效！請(qǐng)確保輸入元素位置小于count+1大于0endl;elsenode*prt=GetPtr(pos-1);node*pNext=prt-next;prt-next=pNext-next;結(jié)點(diǎn)的后繼deletepNext;count-;template獲取指向第pos-1個(gè)結(jié)點(diǎn)的指

26、針獲取指向第pos個(gè)結(jié)點(diǎn)的指針將第pos-1個(gè)結(jié)點(diǎn)的后繼指向第pos個(gè)將第pos個(gè)結(jié)點(diǎn)刪除表元素元素總數(shù)減一voidSimpleLinkList:operator=(SimpleLinkListvET&cop)/賦值符“=”重載Clear();/對(duì)當(dāng)前鏈表先清空if(cop.count0)intcot=cop.count;ETelem;復(fù)制cop的頭指針復(fù)制cop的頭指針node*opr=cop.head;while(cot0)opr=opr-next;elem=opr-data;SetElem(elem);cot-;減一當(dāng)表中還有元素時(shí)/向后繼結(jié)點(diǎn)移動(dòng)一位取出后繼結(jié)點(diǎn)中的數(shù)據(jù)生成新結(jié)點(diǎn)計(jì)數(shù)元

27、素總數(shù)對(duì)當(dāng)前鏈表先清空當(dāng)表A中還有元素時(shí)從B表表頭開始比對(duì)依次獲取A表中元素的當(dāng)表B中還有元素時(shí)將A中的每一個(gè)元素分別與B若與B中所有元素均不相同時(shí)將該元素templatevoidSimpleLinkList:SUB(SimpleLinkList&A,SimpleLinkList&B)Clear();intcountA=1,countB;ETelemA,elemB;node*posA=A.head,*posB;while(countAnext;elemA=posA-data;數(shù)據(jù)部分countA+;while(countBnext;elemB=posB-data;if(elemA=elemB)

28、break;中的每一個(gè)元素進(jìn)行比較，若相同則中斷本次循環(huán)countB+;if(countBB.count)SetElem(elemA);寫入當(dāng)前表中templatevoidSimpleLinkList:ADD(SimpleLinkList&A,SimpleLinkList&B)Clear();對(duì)當(dāng)前鏈表先清空intcountA=1,countB=1;node*posA=A.head,*posB=B.head;while(countAnext;SetElem(posA-data);分,寫入當(dāng)前鏈表countA+;while(countBnext;SetElem(posB-data);分count

29、B+;templatevoidSimpleLinkList:Seprate()偶數(shù)前為鏈表中元素的總個(gè)數(shù)inti=0,jb=O,jc=0;int*B=newintcount,*C=newintcount;中的元素按奇數(shù)、偶數(shù)分別存放到數(shù)組B、C中node*pos=head;ETtmp;while(inext;tmp=pos-data;if(tmp%2=1)Bjb=tmp;jb+;elseCjc=tmp;jc+;i+;當(dāng)表A中還有元素時(shí)依次獲取A表中元素的數(shù)據(jù)部當(dāng)表B中還有元素時(shí)依次獲取B表中元素的數(shù)據(jù)部奇偶分離函數(shù)，使得所有奇數(shù)均排列在/count/將鏈表jb用于計(jì)數(shù)奇數(shù)的個(gè)數(shù)/jc用于計(jì)數(shù)偶數(shù)的個(gè)數(shù)當(dāng)表A中還有元素時(shí)依次獲取A表中元素的數(shù)據(jù)部當(dāng)表B中還有元素時(shí)依次獲取B表中元素的數(shù)據(jù)部奇偶分離函數(shù)，使得所有奇數(shù)均排列在/count/將鏈表jb用于計(jì)數(shù)奇數(shù)的個(gè)數(shù)/jc用于計(jì)數(shù)偶數(shù)的個(gè)數(shù)i=0;pos=head;while(inext;pos-data=Bi;i+;i=0;while(inext;pos-data=Ci;i+;templatevclassETvoidSimpleL