-.z.中南大學(xué)"數(shù)據(jù)構(gòu)造與算法"課程實(shí)驗(yàn)實(shí)驗(yàn)報(bào)告題目實(shí)驗(yàn)一線性表的操作學(xué)生姓名譚淇蔚學(xué)生**3901130721專業(yè)班級(jí)軟件工程1307班完成日期2014年3月31日星期一實(shí)驗(yàn)一線性表的操作〔一元多項(xiàng)式相加〕1.需求分析我們使用計(jì)算機(jī)處理的對(duì)象之間通常存在著的是一種最簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)構(gòu)造。而數(shù)據(jù)存儲(chǔ)構(gòu)造有兩種：順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。線性表是最常用且最簡(jiǎn)單的一種數(shù)據(jù)構(gòu)造。所以我們做的是實(shí)驗(yàn)一-----------線性表的操作。實(shí)驗(yàn)的目的是掌握線性表的根本操作，插入、刪除、查找，以及線性表合并等運(yùn)算在順序存儲(chǔ)構(gòu)造和鏈接存儲(chǔ)構(gòu)造上的運(yùn)算以及熟練運(yùn)用掌握的線性表的操作，實(shí)現(xiàn)一元n次多項(xiàng)式的加法運(yùn)算。學(xué)習(xí)實(shí)現(xiàn)一元n次多項(xiàng)式的加法是符號(hào)多項(xiàng)式的操作，是表處理的典型用例，需要注意的是：順序存儲(chǔ)構(gòu)造指的是用數(shù)組方法，使用數(shù)組方法實(shí)現(xiàn)時(shí)，在插入和刪除的方面，數(shù)組不如鏈表靈活，方法復(fù)雜，刪除其中一個(gè)需要將其后的數(shù)組元素改變位置，使其數(shù)組保持原有的順序構(gòu)造，在查找方面較鏈表簡(jiǎn)單，只需要知道其下標(biāo)就可以知道。鏈接存儲(chǔ)構(gòu)造指的是用鏈表方法,值得注意的是，刪除和插入較為靈活，不需要變動(dòng)大多數(shù)元素，但是查找過程相對(duì)于數(shù)組這種順序存儲(chǔ)構(gòu)造來說較為復(fù)雜，耗時(shí)巨大。我們要學(xué)習(xí)的是通過對(duì)兩種方法根本操作的掌握來做到實(shí)現(xiàn)一元n次多項(xiàng)式的相加減。我們程序的任務(wù)是：能進(jìn)展簡(jiǎn)單的線性表操作〔插入、刪除、查找〕以及線性表合并等運(yùn)算。能通過這些根本操作實(shí)現(xiàn)一元多項(xiàng)式相加。明確規(guī)定：輸入的形式：按照提示〔比方："請(qǐng)您輸入第一個(gè)構(gòu)造體數(shù)組的項(xiàng)數(shù)〔不超過50項(xiàng)〕：〞、"請(qǐng)您輸入第二個(gè)構(gòu)造體數(shù)組的項(xiàng)數(shù)〔不超過50項(xiàng)〕：〞、"請(qǐng)輸入第n項(xiàng)的系數(shù)〞、"請(qǐng)輸入第n項(xiàng)的指數(shù)〞等等〕，先輸入多項(xiàng)式的項(xiàng)數(shù)，之后順次輸入每一項(xiàng)的系數(shù)與指數(shù)。輸入值的范圍：項(xiàng)數(shù)沒有要求，但不能過于巨大；系數(shù)取為float型數(shù)據(jù)，指數(shù)取為int型數(shù)據(jù)，輸出的形式：按照提示〔比方："您輸入的第一個(gè)多項(xiàng)式為：〞、"您輸入的第二個(gè)多項(xiàng)式為：〞等等〕，會(huì)輸出原輸入的多項(xiàng)式和經(jīng)過排序和合并之后的降冪型多項(xiàng)式。同時(shí)，系數(shù)會(huì)以保存小數(shù)點(diǎn)后兩位數(shù)字的形式輸出；假設(shè)指數(shù)輸入時(shí)為小數(shù)，則輸出時(shí)會(huì)自動(dòng)截取其整數(shù)局部。程序所能到達(dá)的功能：程序可以對(duì)輸入的序列紊亂的多項(xiàng)式進(jìn)展加工，使之按照降冪排列，之后對(duì)兩多項(xiàng)式進(jìn)展加法運(yùn)算〔包括系數(shù)為負(fù)的加法〕，最后輸出最終的多項(xiàng)式。測(cè)試數(shù)正確數(shù)據(jù)：輸入：2**^3+2**^6+2**^7+2**^8+2**^10和-3**^10+4**^8+2**^7+3**^5+3**^3輸出：7.00**^2+8.00**^1+2.00錯(cuò)誤數(shù)據(jù)：輸入：-8**^1.5+4**^2和3**^2+12**^1.6輸出：7.00**^2+4.00**^12．概要設(shè)計(jì)〔1〕鏈接存儲(chǔ)構(gòu)造：structnode{floatcoef;inte*po;structnode*ne*t;}chainLink;函數(shù)主體局部，利用頭指針進(jìn)展鏈表操作，利用display進(jìn)展打印出屏幕，利用order函數(shù)對(duì)其進(jìn)展降冪排序，當(dāng)兩個(gè)多項(xiàng)式已經(jīng)創(chuàng)立完畢時(shí)，利用add函數(shù)進(jìn)展兩個(gè)多項(xiàng)式相加?！?〕順序存儲(chǔ)構(gòu)造抽象數(shù)據(jù)類型為構(gòu)造體數(shù)組：structpoly{floatcoef;inte*p;};函數(shù)主體局部，會(huì)引用指針進(jìn)展參數(shù)傳遞，在函數(shù)主體局部定義了3個(gè)構(gòu)造體數(shù)組同時(shí)定義其所對(duì)應(yīng)的指針，利用用戶輸入，利用print函數(shù)將其打印出來，再用sort函數(shù)將其降序排列，做完兩個(gè)構(gòu)造體數(shù)組后，接著利用add函數(shù)將兩個(gè)多項(xiàng)式相加。3．詳細(xì)設(shè)計(jì)〔1〕鏈接存儲(chǔ)構(gòu)造：構(gòu)造體定義：structnode{ intcoef;//系數(shù) inte*p;//指數(shù) structnode*ne*t;//指針域}chainLink;//創(chuàng)立chainLink的node結(jié)點(diǎn)對(duì)象〔值得注意的是，與順序存儲(chǔ)構(gòu)造不同的是，內(nèi)部還定義了指針域〕功能函數(shù)介紹：structnode*create()//定義建立多項(xiàng)式函數(shù)，并返回鏈表頭指針{structnode*h=NULL,*q,*p;//定義構(gòu)造體頭指針h，標(biāo)記指針p和q，p是創(chuàng)造新節(jié)點(diǎn)的標(biāo)記指針，q是鏈接鏈表的指針；inti=1,N;//定義多項(xiàng)式的項(xiàng)數(shù)N及標(biāo)記數(shù)i cout<<"請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)：\n"; cin>>N; p=0;//指針初始化；q=0;//本地指針初始化；for(;i<=N;i++) { p=(structnode*)malloc(sizeof(chainLink));//為一個(gè)新節(jié)點(diǎn)分配空間cout<<"請(qǐng)輸入第"<<i<<"項(xiàng)的系數(shù)：\n"; cin>>(*p).coef; cout<<"請(qǐng)輸入第"<<i<<"項(xiàng)的指數(shù):\n"; cin>>(*p).e*p; if(i==1){h=p;q=p;}//建立頭節(jié)點(diǎn)else { q->ne*t=p; q=p; } } q->ne*t=NULL;//p,q都成為新鏈表的尾指針；p->ne*t=NULL; returnh;}PS：值得注意的是，我在里面P，q指針均使其值為0，是讓其為空指針，對(duì)其進(jìn)展初始化，在visualstudio2013版中，如果不進(jìn)展初始化，會(huì)被報(bào)錯(cuò)。打印函數(shù)display:voiddisplay(structnode*h){ structnode*p;//定義標(biāo)記指針，輸出鏈表p=h; while(p!=NULL) { if(p->coef==0) { structnode*d; d=h; while(d->ne*t!=p) { d=d->ne*t; } d->ne*t=p->ne*t; p=p->ne*t;//刪去系數(shù)為0的節(jié)點(diǎn)； }else { if(p->coef<0)//系數(shù)為負(fù)時(shí)應(yīng)加上括號(hào),讓式子容易看清； {if(p->e*p==0)cout<<(*p).coef<<"+"; elsecout<<"("<<(*p).coef<<")"<<"**^"<<(*p).e*p<<"+"; } else { if(p->e*p==0)cout<<(*p).coef<<"+"; elseif(p->e*p!=0&&p->e*p!=1) { cout<<(*p).coef<<"**^"<<(*p).e*p<<"+"; } elsecout<<(*p).coef<<"**+"; } p=p->ne*t; } } cout<<"\b\b\n";}PS:打印函數(shù)display中，值得注意的是系數(shù)為負(fù)時(shí)，應(yīng)該加括號(hào)。其次，當(dāng)指數(shù)為1時(shí)，沒必要寫成*^1這種形式。系數(shù)為0的項(xiàng)也應(yīng)該刪去，這里我定義一個(gè)d指針，用來找到系數(shù)為0的項(xiàng)前一個(gè)結(jié)點(diǎn)的指針，然后進(jìn)展刪除該系數(shù)為0的節(jié)點(diǎn)的操作，其實(shí)和教師上課中的處理差不多，都是使用一個(gè)指針保護(hù)原有指針，用while循環(huán)找到系數(shù)為0的項(xiàng)的前驅(qū)，以便進(jìn)展刪除節(jié)點(diǎn)操作。排序函數(shù)order：structnode*order(structnode*h)//定義排序函數(shù)，并返回整理后的鏈表的頭指針{structnode*p,*q,*t,*h1,*h2;//定義三個(gè)構(gòu)造體標(biāo)記指針和兩個(gè)頭指針h1=h;//建立一個(gè)新的鏈表，頭指針為h，指向原鏈表的第一個(gè)節(jié)點(diǎn)，之后將原鏈表中的節(jié)點(diǎn)一個(gè)一個(gè)的插入此鏈表，進(jìn)展排序h2=h1->ne*t;//將原來的鏈表建立成待排序鏈表h1->ne*t=NULL;//截?cái)嗟谝粋€(gè)原鏈表中的節(jié)點(diǎn)while(h2!=NULL) { q=h1; p=q->ne*t; t=h2;//從待排序鏈表中選出一個(gè)節(jié)點(diǎn)準(zhǔn)備插入到新鏈表中h2=h2->ne*t;//移動(dòng)待排序鏈表的頭指針，便于進(jìn)展下一次挑選t->ne*t=NULL; if(t->e*p>q->e*p)//應(yīng)插入頭指針之前的情況 {t->ne*t=q; h1=t; continue; } if(p==NULL&&t->e*p<=q->e*p)q->ne*t=t;//應(yīng)插入表尾的情況while(p!=NULL) { if(t->e*p>p->e*p) { q->ne*t=t; t->ne*t=p; break; } else { q=q->ne*t; p=p->ne*t; } } if(p==NULL)q->ne*t=t; } returnh1;//新鏈表即為按降冪順序排好的鏈表，返回其頭指針}Order函數(shù)其實(shí)是利用了3個(gè)頭指針，具體操作看代碼即可，其實(shí)很容易懂。相加函數(shù)add：structnode*add(structnode*h1,structnode*h2)//定義加法函數(shù)，并返回結(jié)果的鏈表的頭指針{structnode*p,*q,*head,*r;//定義構(gòu)造體頭指針head和標(biāo)記指針p,q,r p=h1; q=h2; head=(structnode*)malloc(sizeof(chainLink));//為結(jié)果多項(xiàng)式分配頭指針if(p->e*p>=q->e*p){head=h1;p=p->ne*t;} else { if(p->e*p<q->e*p){head=h2;q=q->ne*t;} else{p->coef=p->coef+q->coef;head=p;p=p->ne*t;q=q->ne*t;} } r=head; while(p!=NULL&&q!=NULL) { if(p->e*p>q->e*p){r->ne*t=p;p=p->ne*t;} else { if(p->e*p<q->e*p){r->ne*t=q;q=q->ne*t;} else{p->coef=p->coef+q->coef;r->ne*t=p;p=p->ne*t;q=q->ne*t;} } r=r->ne*t; } if(p==NULL&&q==NULL)r->ne*t=NULL; else { if(p==NULL)r->ne*t=q; if(q==NULL)r->ne*t=p; } returnhead;}add函數(shù)大局部其實(shí)和教師PPT思路差不多。比擬兩個(gè)多項(xiàng)式中指數(shù)大小，然后分別對(duì)其余兩個(gè)進(jìn)展操作。〔2〕順序存儲(chǔ)構(gòu)造構(gòu)造體定義：structpoly{ floatcoef; inte*p;};//構(gòu)造體數(shù)組定義主函數(shù)構(gòu)造體數(shù)組的創(chuàng)立以及導(dǎo)引指針的創(chuàng)立：polyp[50],*po=p;polyp1[50],*po1=p1;polyp2[100],*po2=p2;//定義三個(gè)構(gòu)造體數(shù)組，用于存放多項(xiàng)式,定義三個(gè)指針變量；print函數(shù)以及參數(shù)調(diào)用代碼：voidprint(structpoly*s[],intn){ for(inti=0;i<n;i++) { if(i==n-1)cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p; else cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p<<"+"; }}//輸出數(shù)組主函數(shù)中調(diào)用print函數(shù)的具體形式：print(&po,n1);sort函數(shù)的代碼：voidsort(structpoly*s[],intn){ inti,temp1,j;//定義數(shù)組中的循環(huán)標(biāo)記數(shù)據(jù)i與j，和整型標(biāo)記temp1 floattemp2;//定義單精度型標(biāo)記temp2 for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { if((*s)[j].e*p>(*s)[i].e*p) { temp1=(*s)[j].e*p; (*s)[j].e*p=(*s)[i].e*p; (*s)[i].e*p=temp1; temp2=(*s)[j].coef; (*s)[j].coef=(*s)[i].coef; (*s)[i].coef=temp2; } } for(i=0;i<n-1;i++) { if((*s)[i].e*p==(*s)[i+1].e*p) { (*s)[i+1].coef=(*s)[i].coef+(*s)[i+1].coef; if(i==n-2) { (*s)[i].coef=(*s)[i+1].coef; (*s)[i+1].coef=0; } else { for(j=i;j<n;j++) { (*s)[j].coef=(*s)[j+1].coef; (*s)[j].e*p=(*s)[j+1].e*p; } (*s)[j].coef=0; i--; } } }}事實(shí)上sort函數(shù)是采用逆冒泡法排序，讓指數(shù)局部大的排在前面，與選擇排序不同，選擇排序是相鄰的交換，直到最小的排在前面為止。Sort函數(shù)在主函數(shù)中的調(diào)用：sort(&po,n1);add函數(shù)的代碼：voidadd(structpoly*s[],structpoly*s1[],structpoly*s2[],intn1,intn2){ inti=0,j=0,p,m;//定義數(shù)組中的循環(huán)標(biāo)記數(shù)據(jù)i,j,p,m for(p=0;;p++) { if((*s)[i].e*p==(*s1)[j].e*p) { (*s2)[p].coef=(*s)[i].coef+(*s1)[j].coef; (*s2)[p].e*p=(*s)[i].e*p; i++; j++; } else { if((*s)[i].e*p>(*s1)[j].e*p) { (*s2)[p].coef=(*s)[i].coef; (*s2)[p].e*p=(*s)[i].e*p; i++; } else { (*s2)[p].coef=(*s1)[j].coef; (*s2)[p].e*p=(*s1)[j].e*p; j++; } } if(i==n1||j==n2) { p++; break; } } if(i==n1) for(;j<n2;j++) { (*s2)[p].coef=(*s1)[j].coef; (*s2)[p].e*p=(*s1)[j].e*p; p++; } else for(;i<n1;i++) { (*s2)[p].coef=(*s)[i].coef; (*s2)[p].e*p=(*s)[i].e*p; p++; } for(m=0;m<p;m++) { if((*s2)[m].coef<0) { if((*s2)[m].e*p==0)cout<<(*s2)[m].coef<<"+"; elsecout<<(*s2)[m].coef<<"**^"<<(*s2)[m].e*p<<"+"; } elseif((*s2)[m].coef>0) { if((*s2)[m].e*p==0)cout<<(*s2)[m].coef<<"+"; else//printf("%.2f**^%d+",d*s2[m].coef,d*s2[m].e*p); cout<<(*s2)[m].coef<<"**^"<<(*s2)[m].e*p<<"+"; } } cout<<"\b\b\n";}add函數(shù)在主函數(shù)中的調(diào)用：add(&po,&po1,&po2,n1,n2);4．調(diào)試分析〔1〕鏈接存儲(chǔ)構(gòu)造：設(shè)計(jì)過程，注意指針保護(hù)，如果一步不小心，容易造成頭指針消失，所以需要指針來保護(hù)頭指針，至于其他方面倒是沒有什么問題?？偟膩碚f，代碼長度170，算不上特別多，該有的功能也考慮到了?！?〕順序存儲(chǔ)構(gòu)造在設(shè)計(jì)過程中，發(fā)現(xiàn)如果不采用指針參數(shù)傳遞構(gòu)造體數(shù)組，而是對(duì)單個(gè)多項(xiàng)式進(jìn)展單個(gè)功能操作，即對(duì)于每一個(gè)多項(xiàng)式都會(huì)用同功能的函數(shù)，只不過不同名稱來實(shí)現(xiàn)，這樣造成代碼冗長，我試過寫出了286行的代碼，但visualstudio2013無法編譯如此冗長的代碼，所以我決定使用指針導(dǎo)向進(jìn)展優(yōu)化，優(yōu)化后的代碼行數(shù)是162行，少了100多行，實(shí)現(xiàn)功能也比之前多了一些。雖然沒法像我第一次寫那286行的代碼可以實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)立構(gòu)造體數(shù)組，但我認(rèn)為，這162行的代碼的構(gòu)造體數(shù)組50個(gè)大小，理應(yīng)足夠計(jì)算，如果要更大，建議修改代碼中創(chuàng)立構(gòu)造體數(shù)組大小的尺寸?？傮w來說，還算不錯(cuò)，知識(shí)經(jīng)過一個(gè)寒假忘得七零八落，感覺我還沒有完全掌握這類知識(shí)，等有時(shí)間重新將自己進(jìn)展優(yōu)化，也希望教師給予指導(dǎo)。5．用戶使用說明〔1〕鏈接存儲(chǔ)構(gòu)造：按照提示一步步來即可；舉例：請(qǐng)輸入第一個(gè)多項(xiàng)式：請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)：3請(qǐng)輸入第一項(xiàng)的系數(shù)：2請(qǐng)輸入第一項(xiàng)的指數(shù)：2請(qǐng)輸入第二項(xiàng)的系數(shù)：3請(qǐng)輸入第二項(xiàng)的指數(shù)：5請(qǐng)輸入第三項(xiàng)的系數(shù)：3請(qǐng)輸入第三項(xiàng)的指數(shù)：1類似如上操作，到時(shí)大局部會(huì)在屏幕顯示?！?〕順序存儲(chǔ)構(gòu)造按照提示一步步來即可；舉例：請(qǐng)您輸入第一個(gè)構(gòu)造體數(shù)組的項(xiàng)數(shù)〔不超過50項(xiàng)〕：2請(qǐng)您輸入第二個(gè)構(gòu)造體數(shù)組的項(xiàng)數(shù)〔不超過50項(xiàng)〕：2現(xiàn)在是輸入第一個(gè)多項(xiàng)式請(qǐng)輸入第1項(xiàng)系數(shù)：2請(qǐng)輸入第1項(xiàng)指數(shù)：2請(qǐng)輸入第2項(xiàng)系數(shù)：3請(qǐng)輸入第2項(xiàng)指數(shù)：3現(xiàn)在是輸入第二個(gè)多項(xiàng)式：請(qǐng)輸入第1項(xiàng)系數(shù)：3請(qǐng)輸入第1項(xiàng)指數(shù)：3請(qǐng)輸入第2項(xiàng)系數(shù)：4請(qǐng)輸入第2項(xiàng)指數(shù)：4接著屏幕便會(huì)顯示出來。6．測(cè)試結(jié)果〔1〕鏈接存儲(chǔ)構(gòu)造：〔2〕順序存儲(chǔ)構(gòu)造7．附錄〔1〕鏈接存儲(chǔ)構(gòu)造：#include<iostream>usingnamespacestd;structnode{ intcoef;//系數(shù) inte*p;//指數(shù) structnode*ne*t;//指針域}chainLink;//創(chuàng)立chainLink的node結(jié)點(diǎn)對(duì)象structnode*create()//定義建立多項(xiàng)式函數(shù)，并返回鏈表頭指針{structnode*h=NULL,*q,*p;//定義構(gòu)造體頭指針h，標(biāo)記指針p和q，p是創(chuàng)造新節(jié)點(diǎn)的標(biāo)記指針，q是鏈接鏈表的指針；inti=1,N;//定義多項(xiàng)式的項(xiàng)數(shù)N及標(biāo)記數(shù)i cout<<"請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)：\n"; cin>>N; p=0;//指針初始化；q=0;//本地指針初始化；for(;i<=N;i++) { p=(structnode*)malloc(sizeof(chainLink));//為一個(gè)新節(jié)點(diǎn)分配空間cout<<"請(qǐng)輸入第"<<i<<"項(xiàng)的系數(shù)：\n"; cin>>(*p).coef; cout<<"請(qǐng)輸入第"<<i<<"項(xiàng)的指數(shù):\n"; cin>>(*p).e*p; if(i==1){h=p;q=p;}//建立頭節(jié)點(diǎn)else { q->ne*t=p; q=p; } } q->ne*t=NULL;//p,q都成為新鏈表的尾指針；p->ne*t=NULL; returnh;}voiddisplay(structnode*h){ structnode*p;//定義標(biāo)記指針，輸出鏈表p=h; while(p!=NULL) { if(p->coef==0) { structnode*d; d=h; while(d->ne*t!=p) { d=d->ne*t; } d->ne*t=p->ne*t; p=p->ne*t;//刪去系數(shù)為0的節(jié)點(diǎn)； }else { if(p->coef<0)//系數(shù)為負(fù)時(shí)應(yīng)加上括號(hào),讓式子容易看清； {if(p->e*p==0)cout<<(*p).coef<<"+"; elsecout<<"("<<(*p).coef<<")"<<"**^"<<(*p).e*p<<"+"; } else { if(p->e*p==0)cout<<(*p).coef<<"+"; elseif(p->e*p!=0&&p->e*p!=1) { cout<<(*p).coef<<"**^"<<(*p).e*p<<"+"; } elsecout<<(*p).coef<<"**+"; } p=p->ne*t; } } cout<<"\b\b\n";}structnode*order(structnode*h)//定義排序函數(shù)，并返回整理后的鏈表的頭指針{structnode*p,*q,*t,*h1,*h2;//定義三個(gè)構(gòu)造體標(biāo)記指針和兩個(gè)頭指針h1=h;//建立一個(gè)新的鏈表，頭指針為h，指向原鏈表的第一個(gè)節(jié)點(diǎn)，之后將原鏈表中的節(jié)點(diǎn)一個(gè)一個(gè)的插入此鏈表，進(jìn)展排序h2=h1->ne*t;//將原來的鏈表建立成待排序鏈表h1->ne*t=NULL;//截?cái)嗟谝粋€(gè)原鏈表中的節(jié)點(diǎn)while(h2!=NULL) { q=h1; p=q->ne*t; t=h2;//從待排序鏈表中選出一個(gè)節(jié)點(diǎn)準(zhǔn)備插入到新鏈表中h2=h2->ne*t;//移動(dòng)待排序鏈表的頭指針，便于進(jìn)展下一次挑選t->ne*t=NULL; if(t->e*p>q->e*p)//應(yīng)插入頭指針之前的情況 {t->ne*t=q; h1=t; continue; } if(p==NULL&&t->e*p<=q->e*p)q->ne*t=t;//應(yīng)插入表尾的情況while(p!=NULL) { if(t->e*p>p->e*p) { q->ne*t=t; t->ne*t=p; break; } else { q=q->ne*t; p=p->ne*t; } } if(p==NULL)q->ne*t=t; } returnh1;//新鏈表即為按降冪順序排好的鏈表，返回其頭指針}structnode*add(structnode*h1,structnode*h2)//定義加法函數(shù)，并返回結(jié)果的鏈表的頭指針{structnode*p,*q,*head,*r;//定義構(gòu)造體頭指針head和標(biāo)記指針p,q,r p=h1; q=h2; head=(structnode*)malloc(sizeof(chainLink));//為結(jié)果多項(xiàng)式分配頭指針if(p->e*p>=q->e*p){head=h1;p=p->ne*t;} else { if(p->e*p<q->e*p){head=h2;q=q->ne*t;} else{p->coef=p->coef+q->coef;head=p;p=p->ne*t;q=q->ne*t;} } r=head; while(p!=NULL&&q!=NULL) { if(p->e*p>q->e*p){r->ne*t=p;p=p->ne*t;} else { if(p->e*p<q->e*p){r->ne*t=q;q=q->ne*t;} else{p->coef=p->coef+q->coef;r->ne*t=p;p=p->ne*t;q=q->ne*t;} } r=r->ne*t; } if(p==NULL&&q==NULL)r->ne*t=NULL; else { if(p==NULL)r->ne*t=q; if(q==NULL)r->ne*t=p; } returnhead;}intmain(){ structnode*h1,*h2,*h3;//定義3個(gè)頭指針；cout<<"\n請(qǐng)輸入第一個(gè)多項(xiàng)式：\n"; h1=create();//創(chuàng)造第一個(gè)線性鏈表；cout<<"\n您輸入的第一個(gè)多項(xiàng)式為：\n"; display(h1);//把多項(xiàng)式顯示出來；h1=order(h1); cout<<"\n降冪排列后的第一個(gè)多項(xiàng)式為：\n"; display(h1); cout<<"\n"; cout<<"\n請(qǐng)輸入第二個(gè)多項(xiàng)式：\n"; h2=create();//創(chuàng)造第二個(gè)線性鏈表；cout<<"\n您輸入的第二個(gè)多項(xiàng)式為：\n"; display(h2);//把多項(xiàng)式顯示出來；h2=order(h2); cout<<"\n降冪排列后的第二個(gè)多項(xiàng)式為：\n"; display(h2); cout<<"\n"; h3=add(h1,h2);//利用加函數(shù)將多項(xiàng)式相加；cout<<"\n第一個(gè)多項(xiàng)式和第二個(gè)多項(xiàng)式相加后：\n"; display(h3); system("pause"); return0;}〔2〕順序存儲(chǔ)構(gòu)造#include<iostream>usingnamespacestd;structpoly{ floatcoef; inte*p;};//構(gòu)造體數(shù)組定義voiddefStruct(structpoly*s[],intn){ inti=0; for(;i<n;i++) { cout<<"請(qǐng)輸入第"<<i+1<<"項(xiàng)的系數(shù)：\n"; cin>>(*s)[i].coef; cout<<"請(qǐng)輸入第"<<i+1<<"項(xiàng)的指數(shù)：\n"; cin>>(*s)[i].e*p; }//初始化順序構(gòu)造體數(shù)組}voidprint(structpoly*s[],intn){ for(inti=0;i<n;i++) { if(i==n-1)cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p; else cout<<(*s)[i].coef<<"**^"<<(*s)[i].e*p<<"+"; }}//輸出數(shù)組voidsort(structpoly*s[],intn){ inti,temp1,j;//定義數(shù)組中的循環(huán)標(biāo)記數(shù)據(jù)i與j，和整型標(biāo)記temp1 floattemp2;//定義單精度型標(biāo)記temp2 for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) { if((*s)[j].e*p>(*s)[i].e*p) { temp1=(*s)[j].e*p; (*s)[j].e*p=(*s)[i].e*p; (*s)[i].e*p=temp1; temp2=(*s)[j].coef; (*s)[j].coef=(*s)[i].coef; (*s)[i].coef=temp2; } } for(i=0;i<n-1;i++) { if((*s)[i].e*p==(*s)[i+1].e*p) { (*s)[i+1].coef=(*s)[i].coef+(*s)[i+1].coef; if(i==n-2) { (*s)[i].coef=(*s)[i+1].coef; (*s)[i+1].coef=0; } else { for(j=i;j<n;j++) { (*s)[j].coef=(*s)[j+1].coef; (*s)[j].e*p=(*s)[j+1].e*p; } (*s)[j].coef=0; i--; } } }}voidadd(structpoly*s[],structpoly*s1[],structpoly*s2[],intn1,intn2){ inti=0,j=0,p,m;//定義數(shù)組中的循環(huán)標(biāo)記數(shù)據(jù)i,j,p,m for(p=0;;p++) { if((*s)[i].e*p==(*s1)[j].e*p) { (*s2)[p].coef=(*s)[i].coef+(*s1)[j].coef; (*s2)[p].e*p=(*s)[i].e*