多項式的設(shè)計報告數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

PAGE4目錄1.多項式的設(shè)計報告…….………2a．概要設(shè)計…….………2b．詳細(xì)設(shè)計…….………3c．調(diào)試分析…….………8數(shù)據(jù)結(jié)果…….………8時間復(fù)雜度分析……10問題和解決方法……10源程序代碼展示…………102.二叉樹的設(shè)計報告…….………18a．概要設(shè)計…….………18b．詳細(xì)設(shè)計…….………19c．調(diào)試分析…….………21數(shù)據(jù)結(jié)果…….………21時間復(fù)雜度分析………22問題和解決方法………23源程序代碼展示…………233.課程設(shè)計總結(jié)…………………26多項式的設(shè)計報告概要設(shè)計1.將該存儲結(jié)構(gòu)定義為鏈?zhǔn)浇Y(jié)構(gòu)的線性表存儲結(jié)構(gòu)的定義：structNode{floatcoef;//結(jié)點類型intexp;};typedefNodepolynomial;structLNode{polynomialdata;//鏈表類型LNode*next;};typedefLNode*Link;2．創(chuàng)建函數(shù)流程圖開始開始分配空間第i個的系數(shù)ceof第i個的指數(shù)expexp>0？否是錯誤，重新輸入JudgeIfExpSame=1？否是錯誤，重新輸入1=>i注釋：JudgeIfExpSame函數(shù)是判斷輸入的指數(shù)是否與多項式中已存在的某項的指數(shù)相同3.主程序流程圖:4.多項式加法的算法分析將鏈表pa，pb分別復(fù)制到新建鏈表p1，p2中，再新建鏈表pc，然后分別依次對p1，p2鏈表中結(jié)點中的指數(shù)進(jìn)行比較，將指數(shù)小的結(jié)點的值先賦值給pc中的結(jié)點，兩個指數(shù)相同時，將系數(shù)相加后一起賦值給pc中的結(jié)點，最后將p1或者p2中多余的結(jié)點直接賦值給pc鏈表，pc鏈表就是通過加法后的多項式5.多項式減法的算法分析新建鏈表pt，將pb中的結(jié)點值賦給pt，然后將pt中所有結(jié)點的系數(shù)乘上（-1）后，再將pt和pa相加就得到相減后的多項式。6.多項式乘法的算法分析同樣將鏈表pa，pb中的結(jié)點賦值給p1，p2，然后依次將p1中的每個結(jié)點的值分別與p2中每個結(jié)點的值相乘后賦值給pc，就得到相乘后的多項式。詳細(xì)設(shè)計創(chuàng)建多項式的源程序voidCreateLink(Link&L,intn){if(L!=NULL)//首先判斷是已經(jīng)存在多項式，如果存在則銷毀{DestroyLink(L);}Linkp,newp;L=newLNode;L->next=NULL;//分配結(jié)點空間，new相當(dāng)于malloc函數(shù)(L->data).exp=-1;//創(chuàng)建頭結(jié)點p=L;for(inti=1;i<=n;i++){newp=newLNode;cout<<"請輸入第"<<i<<"項的系數(shù)和指數(shù):"<<endl;cout<<"系數(shù):";cin>>(newp->data).coef;cout<<"指數(shù):";cin>>(newp->data).exp;if(newp->data.exp<0){cout<<"您輸入有誤，指數(shù)不允許為負(fù)值!"<<endl;deletenewp;i--;continue;//輸入不符合要求則刪除重新創(chuàng)建，delete相當(dāng)于free函數(shù)}newp->next=NULL;p=L;if(newp->data.coef==0){cout<<"系數(shù)為零，重新輸入!"<<endl;deletenewp;i--;continue;}while((p->next!=NULL)&&((p->next->data).exp<(newp->data).exp)){p=p->next;//p指向指數(shù)最小的那一個}if(!JudgeIfExpSame(L,newp)){newp->next=p->next;p->next=newp;}else{cout<<"輸入的該項指數(shù)與多項式中已存在的某項相同,請重新創(chuàng)建一個正確的多項式"<<endl;deletenewp;DestroyLink(L);CreateLink(L,n);//創(chuàng)建多項式?jīng)]有成功，遞歸調(diào)用重新創(chuàng)建break;}}}二．多項式相加模塊的源程序voidPolyAdd(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd;CopyLink(p1,pa);CopyLink(p2,pb);//將鏈表pa，pb分別復(fù)制給p1，p2pc=newLNode;pc->next=NULL;p=pc;//創(chuàng)建新鏈表pc來存儲相加后的值p1=p1->next;p2=p2->next;while(p1!=NULL&&p2!=NULL){if(p1->data.exp<p2->data.exp)//將指數(shù)小的結(jié)點的值賦給pc鏈表中的結(jié)點{p->next=p1;p=p->next;p1=p1->next;}elseif(p1->data.exp>p2->data.exp){p->next=p2;p=p->next;p2=p2->next;}else//當(dāng)指數(shù)相等時，將系數(shù)相加后再把指數(shù)和系數(shù)賦給pc{p1->data.coef=p1->data.coef+p2->data.coef;if(p1->data.coef!=0)//當(dāng)相加后的系數(shù)不等于0，直接賦給pc{p->next=p1;p=p->next;p1=p1->next;p2=p2->next;}else//當(dāng)相加后的系數(shù)等于0時不存儲在pc中，將p1，p2分別指向下一個結(jié)點進(jìn)行相加算法{pd=p1;p1=p1->next;p2=p2->next;deletepd;}}}if(p1!=NULL){p->next=p1;}if(p2!=NULL){p->next=p2;}}三．多項式相減模塊的源程序voidPolySubstract(Link&pc,Linkpa,Linkpb){Linkp,pt;CopyLink(pt,pb);p=pt;//將鏈表pb賦給鏈表ptwhile(p!=NULL){(p->data).coef=(-(p->data).coef);p=p->next;//將pt中的系數(shù)都乘以（-1）}PolyAdd(pc,pa,pt);//再將pt與pa相加，就得到相減的結(jié)果DestroyLink(pt);}四．多項式相乘模塊的源程序voidPolyMultiply(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd,newp,t;pc=newLNode;pc->next=NULL;p1=pa->next;p2=pb->next;while(p1!=NULL)//用循環(huán)的方式將p1的每個結(jié)點分別與p2中的每個結(jié)點相乘{(lán)pd=newLNode;pd->next=NULL;p=newLNode;p->next=NULL;t=p;while(p2){newp=newLNode;newp->next=NULL;newp->data.coef=p1->data.coef*p2->data.coef;newp->data.exp=p1->data.exp+p2->data.exp;t->next=newp;t=t->next;p2=p2->next;}PolyAdd(pd,pc,p);//將最新相乘算出來的多項式與已存在的多項式相加CopyLink(pc,pd);//再將相加的結(jié)果放到鏈表pc中去p1=p1->next;p2=pb->next;DestroyLink(p);DestroyLink(pd);}}五．主函數(shù)源程序voidmain()//主函數(shù){intn;LinkL,La=NULL,Lb=NULL;//La,Lb分別為創(chuàng)建的兩個多項式intchoose;Menu();//調(diào)用菜單函數(shù)while(1){cin>>choose;switch(choose){case1:cout<<"請輸入需要運算的第一個一元多項式的項數(shù):"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"輸入有誤，請重新輸入……\n\t\t\t\t請選擇:";break;}CreateLink(La,n);//創(chuàng)建鏈表Lacout<<"請輸入需要運算的第二個一元多項式的項數(shù):"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"輸入有誤，請重新輸入……\n\t\t\t\t請選擇:";break;}CreateLink(Lb,n);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;//創(chuàng)建鏈表Lbcase2:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;//如果多項式為空則重新輸入}PolyAdd(L,La,Lb);cout<<""<<endl;//將多項式相加cout<<"待相加的兩個一元多項式為："<<endl;cout<<""<<endl;cout<<"A的多項式為：";PrintList(La);cout<<""<<endl;cout<<"B的多項式為：";PrintList(Lb);cout<<""<<endl;cout<<"相加后的結(jié)果為：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case3:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}PolySubstract(L,La,Lb);//將多項式相減cout<<"相減的兩個一元多項式為："<<endl;cout<<""<<endl;cout<<"A的多項式為：";PrintList(La);cout<<""<<endl;cout<<"B的多項式為：";PrintList(Lb);cout<<""<<endl;cout<<"相減后的結(jié)果為：";PrintList(L);cout<<"\n\t\t\t\t請繼續(xù)選擇:";DestroyLink(L);break;case4:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}PolyMultiply(L,La,Lb);//將多項式相乘cout<<"相乘的兩個一元多項式為："<<endl;cout<<""<<endl;cout<<"A的多項式為：";PrintList(La);cout<<""<<endl;cout<<"B的多項式為：";PrintList(Lb);cout<<""<<endl;cout<<"相乘后的結(jié)果為：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case5:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}cout<<"一元多項式A為："<<endl;PrintList(La);cout<<""<<endl;//將多項式La輸出cout<<"一元多項式B為："<<endl;PrintList(Lb);//將多項式Lb輸出cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case6:if(La&&Lb){DestroyLink(La);DestroyLink(Lb);cout<<"多項式銷毀成功！"<<endl;cout<<"\t\t\t\t請繼續(xù)選擇:";}else{cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";}break;case7:exit(0);//exit(0)強(qiáng)制終止程序，返回狀態(tài)碼0表示正常結(jié)束default:cout<<"輸入錯誤，請重新選擇操作……\n\t\t\t\t請選擇:";break;}}}調(diào)試分析1.數(shù)據(jù)結(jié)果*************************一元多項式的運算*************************①新建多項式**②加法運算**③減法運算**④相乘運算**⑤輸出**⑥清空**⑦退出******************************************************************請選擇:9輸入錯誤，請重新選擇操作……請選擇:4多項式不存在，請重新輸入……請選擇:1請輸入需要運算的第一個一元多項式的項數(shù):46項數(shù)太大，請重新輸入……請選擇:1請輸入需要運算的第一個一元多項式的項數(shù):5請輸入第1項的系數(shù)和指數(shù):系數(shù):34指數(shù):5請輸入第2項的系數(shù)和指數(shù):系數(shù):47指數(shù):2請輸入第3項的系數(shù)和指數(shù):系數(shù):48指數(shù):1請輸入第4項的系數(shù)和指數(shù):系數(shù):49指數(shù):3請輸入第5項的系數(shù)和指數(shù):系數(shù):28指數(shù):4請輸入需要運算的第二個一元多項式的項數(shù):4請輸入第1項的系數(shù)和指數(shù):系數(shù):33指數(shù):5請輸入第2項的系數(shù)和指數(shù):系數(shù):39指數(shù):1請輸入第3項的系數(shù)和指數(shù):系數(shù):29指數(shù):3請輸入第4項的系數(shù)和指數(shù):系數(shù):88指數(shù):2請繼續(xù)選擇:2待相加的兩個一元多項式為：A的多項式為：48x+47x^2+49x^3+28x^4+34x^5B的多項式為：39x+88x^2+29x^3+33x^5相加后的結(jié)果為：87x+135x^2+78x^3+28x^4+67x^5請繼續(xù)選擇:3相減的兩個一元多項式為：A的多項式為：48x+47x^2+49x^3+28x^4+34x^5B的多項式為：39x+88x^2+29x^3+33x^5相減后的結(jié)果為：9x-41x^2+20x^3+28x^4+x^5請繼續(xù)選擇:4相乘的兩個一元多項式為：A的多項式為：48x+47x^2+49x^3+28x^4+34x^5B的多項式為：39x+88x^2+29x^3+33x^5相乘后的結(jié)果為：1872x^2+6057x^3+7439x^4+6767x^5+6795x^6+5355x^7+2603x^8+924x^9+1122x^10請繼續(xù)選擇:5一元多項式A為：48x+47x^2+49x^3+28x^4+34x^5一元多項式B為：39x+88x^2+29x^3+33x^5請繼續(xù)選擇:6多項式銷毀成功！請繼續(xù)選擇:7Pressanykeytocontinue2．時間復(fù)雜度分析創(chuàng)建函數(shù)的復(fù)雜度為o（n），復(fù)制鏈表時為o（n），設(shè)鏈表a為n1個節(jié)點，鏈表b為n2個節(jié)點，加法運算時因為有復(fù)制過程所以如果是不理想狀態(tài)復(fù)雜度為o（2（n1+n2）），減法運算時因為先將鏈表b復(fù)制然后又將其改成-pb，然后將-pb與pa相加，故復(fù)雜度為o（2（n1+2n2）），乘法時復(fù)雜度為o（n1*n2）3.問題和解決方法1.開始沒有想到將鏈表復(fù)制，而是直接在鏈表上進(jìn)行的操作，但是卻因此改變了鏈表的值而影響了后面的操作使結(jié)果不如人意。解決方法是從網(wǎng)上看了一個程序后，重新分配空間后將其鏈表復(fù)制到其上，才達(dá)到效果，不影響原來多項式的數(shù)值。2.系數(shù)的表示方法，開始運行的時候，不是很到位，比如說當(dāng)系數(shù)為1或-1時，可以省略1，還有指數(shù)1和0次方的表示比較特殊。所以解決的時候必須分別分情況討論。但是又增加了程序的空間復(fù)雜度。還有一些其他細(xì)小的問題一般都會有的，只需注意一下，也比較容易改正。3.在課設(shè)過程中有遇到這樣一個問題，就是對一個操作完成以后它不會進(jìn)行下一個操作，分析之后發(fā)現(xiàn)switch語句中用到break，而沒有循環(huán)故不進(jìn)行下個選項直接跳出switch到主函數(shù)中去了，加入一個while以后就可以正常進(jìn)行。4.改進(jìn)改進(jìn)的話就是需要盡量減少空間復(fù)雜度和時間復(fù)雜度。源程序代碼展示#include<conio.h>#include<iostream>#include<stdlib.h>usingnamespacestd;structNode{floatcoef;//結(jié)點類型intexp;};typedefNodepolynomial;structLNode{polynomialdata;//鏈表類型LNode*next;};typedefLNode*Link;voidDestroyLink(Link&L)//銷毀鏈表函數(shù){Linkp;p=L->next;while(p){L->next=p->next;deletep;p=L->next;}deleteL;L=NULL;}/*判斷指數(shù)是否與多項式中已存在的某項相同*/intJudgeIfExpSame(LinkL,Linke){Linkp;p=L->next;while(p!=NULL&&(e->data.exp!=p->data.exp))p=p->next;if(p==NULL)return0;elsereturn1;}//用頭插入法創(chuàng)建含有n個鏈表類型結(jié)點的項，即創(chuàng)建一個n項多項式的算法voidCreateLink(Link&L,intn){if(L!=NULL){DestroyLink(L);}Linkp,newp;L=newLNode;L->next=NULL;(L->data).exp=-1;//創(chuàng)建頭結(jié)點p=L;for(inti=1;i<=n;i++){newp=newLNode;cout<<"請輸入第"<<i<<"項的系數(shù)和指數(shù):"<<endl;cout<<"系數(shù):";cin>>(newp->data).coef;cout<<"指數(shù):";cin>>(newp->data).exp;if(newp->data.exp<0){cout<<"您輸入有誤，指數(shù)不允許為負(fù)值!"<<endl;deletenewp;i--;continue;}newp->next=NULL;p=L;if(newp->data.coef==0){cout<<"系數(shù)為零，重新輸入!"<<endl;deletenewp;i--;continue;}while((p->next!=NULL)&&((p->next->data).exp<(newp->data).exp)){p=p->next;//p指向指數(shù)最小的那一個}if(!JudgeIfExpSame(L,newp)){newp->next=p->next;p->next=newp;}else{cout<<"輸入的該項指數(shù)與多項式中已存在的某項相同,請重新創(chuàng)建一個正確的多項式"<<endl;deletenewp;DestroyLink(L);CreateLink(L,n);//創(chuàng)建多項式?jīng)]有成功，遞歸調(diào)用重新創(chuàng)建break;}}}/*輸出鏈表算法*/voidPrintList(LinkL){Linkp;if(L==NULL||L->next==NULL)cout<<"該一元多項式為空！"<<endl;else{p=L->next;//項的系數(shù)大于0的5種情況if((p->data).coef>0){if((p->data).exp==0)cout<<(p->data).coef;elseif((p->data).coef==1&&(p->data).exp==1)cout<<"x";elseif((p->data).coef==1&&(p->data).exp!=1)cout<<"x^"<<(p->data).exp;elseif((p->data).exp==1&&(p->data).coef!=1)cout<<(p->data).coef<<"x";elsecout<<(p->data).coef<<"x^"<<(p->data).exp;}//項的系數(shù)小于0的5種情況if((p->data).coef<0){if((p->data).exp==0)cout<<(p->data).coef;elseif(p->data.coef==-1&&p->data.exp==1)cout<<"-x";elseif(p->data.coef==-1&&p->data.exp!=1)cout<<"-x^"<<p->data.exp;elseif(p->data.exp==1)cout<<p->data.coef<<"x";elsecout<<(p->data).coef<<"x^"<<(p->data).exp;}p=p->next;while(p!=NULL){if((p->data).coef>0){if((p->data).exp==0)cout<<"+"<<(p->data).coef;elseif((p->data).exp==1&&(p->data).coef!=1)cout<<"+"<<(p->data).coef<<"x";elseif((p->data).exp==1&&(p->data).coef==1)cout<<"+"<<"x";elseif((p->data).coef==1&&(p->data).exp!=1)cout<<"+"<<"x^"<<(p->data).exp;elsecout<<"+"<<(p->data).coef<<"x^"<<(p->data).exp;}if((p->data).coef<0){if((p->data).exp==0)cout<<(p->data).coef;elseif(p->data.coef==-1&&p->data.exp==1)cout<<"-x";elseif(p->data.coef==-1&&p->data.exp!=1)cout<<"-x^"<<p->data.exp;elseif(p->data.exp==1)cout<<p->data.coef<<"x";elsecout<<(p->data).coef<<"x^"<<(p->data).exp;}p=p->next;}}cout<<endl;}/*把一個鏈表的內(nèi)容復(fù)制給另一個鏈表算法*/voidCopyLink(Link&pc,Linkpa){Linkp,q,r;pc=newLNode;pc->next=NULL;r=pc;p=pa;while(p->next!=NULL){q=newLNode;q->data.coef=p->next->data.coef;q->data.exp=p->next->data.exp;r->next=q;q->next=NULL;r=q;p=p->next;}}/*將兩個一元多項式相加算法*/voidPolyAdd(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd;CopyLink(p1,pa);CopyLink(p2,pb);pc=newLNode;pc->next=NULL;p=pc;p1=p1->next;p2=p2->next;while(p1!=NULL&&p2!=NULL){if(p1->data.exp<p2->data.exp){p->next=p1;p=p->next;p1=p1->next;}elseif(p1->data.exp>p2->data.exp){p->next=p2;p=p->next;p2=p2->next;}else{p1->data.coef=p1->data.coef+p2->data.coef;if(p1->data.coef!=0){p->next=p1;p=p->next;p1=p1->next;p2=p2->next;}else{pd=p1;p1=p1->next;p2=p2->next;deletepd;}}}if(p1!=NULL){p->next=p1;}if(p2!=NULL){p->next=p2;}}/*將兩個多項式相減算法*/voidPolySubstract(Link&pc,Linkpa,Linkpb){Linkp,pt;CopyLink(pt,pb);p=pt;while(p!=NULL){(p->data).coef=(-(p->data).coef);p=p->next;}PolyAdd(pc,pa,pt);DestroyLink(pt);}/*將兩個一元多項式相乘算法*/voidPolyMultiply(Link&pc,Linkpa,Linkpb){Linkp1,p2,p,pd,newp,t;pc=newLNode;pc->next=NULL;p1=pa->next;p2=pb->next;while(p1!=NULL){pd=newLNode;pd->next=NULL;p=newLNode;p->next=NULL;t=p;while(p2){newp=newLNode;newp->next=NULL;newp->data.coef=p1->data.coef*p2->data.coef;newp->data.exp=p1->data.exp+p2->data.exp;t->next=newp;t=t->next;p2=p2->next;}PolyAdd(pd,pc,p);CopyLink(pc,pd);p1=p1->next;p2=pb->next;DestroyLink(p);DestroyLink(pd);}}//菜單函數(shù)voidMenu(){cout<<endl<<endl;cout<<"\t*************************一元多項式的運算**********************"<<endl;cout<<"\t*\t\t\t\t\t\t\t*"<<endl;cout<<"\t*\t\t\t①新建多項式\t\t\t*"<<endl;cout<<"\t*\t\t\t②加法運算\t\t\t*"<<endl;cout<<"\t*\t\t\t③減法運算\t\t\t*"<<endl;cout<<"\t*\t\t\t④相乘運算\t\t\t*"<<endl;cout<<"\t*\t\t\t⑤輸出\t\t\t*"<<endl;cout<<"\t*\t\t\t⑥清空\t\t\t*"<<endl;cout<<"\t*\t\t\t⑦退出\t\t\t*"<<endl;cout<<"\t*\t\t\t\t\t\t\t*"<<endl;cout<<"\t***************************************************************"<<endl;cout<<"\t\t\t\t請選擇:";}//判斷輸入的整數(shù)是不是為1到20的數(shù)字算法，限定多項式的項數(shù)，使項數(shù)不要太多intCompareIfNum(inti){if(i>0&&i<20)return0;elsereturn1;}voidmain()//主函數(shù){intn;LinkL,La=NULL,Lb=NULL;//La,Lb分別為創(chuàng)建的兩個多項式intchoose;Menu();//調(diào)用菜單函數(shù)while(1){cin>>choose;switch(choose){case1:cout<<"請輸入需要運算的第一個一元多項式的項數(shù):"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"輸入有誤，請重新輸入……\n\t\t\t\t請選擇:";break;}CreateLink(La,n);cout<<"請輸入需要運算的第二個一元多項式的項數(shù):"<<endl;cin>>n;if(CompareIfNum(n)==1){cout<<"輸入有誤，請重新輸入……\n\t\t\t\t請選擇:";break;}CreateLink(Lb,n);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case2:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}PolyAdd(L,La,Lb);cout<<""<<endl;cout<<"待相加的兩個一元多項式為："<<endl;cout<<""<<endl;cout<<"A的多項式為：";PrintList(La);cout<<""<<endl;cout<<"B的多項式為：";PrintList(Lb);cout<<""<<endl;cout<<"相加后的結(jié)果為：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case3:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}PolySubstract(L,La,Lb);cout<<"相減的兩個一元多項式為："<<endl;cout<<""<<endl;cout<<"A的多項式為：";PrintList(La);cout<<""<<endl;cout<<"B的多項式為：";PrintList(Lb);cout<<""<<endl;cout<<"相減后的結(jié)果為：";PrintList(L);cout<<"\n\t\t\t\t請繼續(xù)選擇:";DestroyLink(L);break;case4:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}PolyMultiply(L,La,Lb);cout<<"相乘的兩個一元多項式為："<<endl;cout<<""<<endl;cout<<"A的多項式為：";PrintList(La);cout<<""<<endl;cout<<"B的多項式為：";PrintList(Lb);cout<<""<<endl;cout<<"相乘后的結(jié)果為：";PrintList(L);DestroyLink(L);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case5:if(La==NULL||Lb==NULL){cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";break;}cout<<"一元多項式A為："<<endl;PrintList(La);cout<<""<<endl;cout<<"一元多項式B為："<<endl;PrintList(Lb);cout<<"\n\t\t\t\t請繼續(xù)選擇:";break;case6:if(La&&Lb){DestroyLink(La);DestroyLink(Lb);cout<<"多項式銷毀成功！"<<endl;cout<<"\t\t\t\t請繼續(xù)選擇:";}else{cout<<"多項式不存在，請重新輸入……\n\t\t\t\t請選擇:";}break;case7:exit(0);//exit(0)強(qiáng)制終止程序，返回狀態(tài)碼0表示正常結(jié)束default:cout<<"輸入錯誤，請重新選擇操作……\n\t\t\t\t請選擇:";break;}}}二叉樹的設(shè)計報告概要設(shè)計主要是遞歸函數(shù)的使用比較重要，還有非遞歸遍歷時用棧來操作。主函數(shù)是基本的switch語句可以省略創(chuàng)建函數(shù)的遞歸流程圖開始遞歸函數(shù)開始遞歸函數(shù)CreatBiTree（T）Ch=Null？是否T=NullCh=>T—>dataT—>lchild=>TT—>rchild=>T輸入Ch先序遞歸遍歷流程圖4.存儲結(jié)構(gòu)主要用了鏈表二叉樹定義typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BiTree;在層序遍歷中還使用了隊列來存儲。b.詳細(xì)設(shè)計一．二叉樹的創(chuàng)建算法的源程序voidCreateBiTree(BiTree&T){//按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空節(jié)點charch;ch=getchar();//從鍵盤輸入結(jié)點的值if(ch=='')T=NULL;//如果為空格號就為空結(jié)點else{if(!(T=(BTNode*)malloc(sizeof(BTNode))))cout<<"mallocfail!";T->data=ch;CreateBiTree(T->lchild);//遞歸調(diào)用創(chuàng)建左結(jié)點CreateBiTree(T->rchild);//遞歸調(diào)用創(chuàng)建右結(jié)點}}二．二叉樹的遞歸先序遍歷算法的源程序voidPreOrderTraverse(BiTreeT){//遞歸先序遍歷if(T){cout<<""<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}三．二叉樹的遞歸中序遍歷算法的源程序voidInOrderTraverse(BiTreeT){//遞歸中序遍歷if(T){InOrderTraverse(T->lchild);cout<<""<<T->data;InOrderTraverse(T->rchild);}}四．二叉樹的遞歸后序遍歷算法的源程序voidPostOrderTraverse(BiTreeT)//遞歸后序遍歷{if(T){ PreOrderTraverse(T->lchild);//后序遍歷左子樹 PreOrderTraverse(T->rchild);//后序遍歷右子樹 cout<<""<<T->data;//訪問結(jié)點}}五．二叉樹的遞歸層序遍歷算法的源程序voidLevelOrderTraverse(BiTreeT){//層序遍歷，用隊列來存儲BiTreeQ[MaxLength];intfront=0,rear=0;BiTreep;if(T){//根結(jié)點入隊Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){p=Q[front];//隊頭元素出隊front=(front+1)%MaxLength;cout<<""<<p->data;if(p->lchild){//左孩子不為空，入隊Q[rear]=p->lchild;rear=(rear+1)%MaxLength;}if(p->rchild){//右孩子不為空，入隊Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}}}六．主函數(shù)源程序voidmain(){BiTreeT;T=NULL;cout<<endl;cout<<"\t**********************************************************";cout<<"\n\n\t********************二叉樹的遞歸操作:*********************\n";cout<<"\t********\t1.新建二叉樹\t********\n";cout<<"\t********\t2.二叉樹的層次遍歷算法\t********\n";cout<<"\t********\t3.二叉樹的遞歸先序遍歷算法\t********\n";cout<<"\t********\t4.二叉樹的遞歸中序遍歷算法\t********\n";cout<<"\t********\t5.二叉樹的遞歸后序遍歷算法\t********\n";cout<<"\t********\t0.退出\t********\n";cout<<"\t**********************************************************\n";cout<<"\n\t**********************************************************\n";cout<<"\t\t\t\t請選擇";while(1){intselect;cin>>select;switch(select){case0:return;//選0退出case1:cout<<"請按先序次序輸入各結(jié)點的值，以空格表示空節(jié)點:"<<endl;CreateBiTree(T);//以空格表示空節(jié)點創(chuàng)建二叉樹cout<<"\t\t\t\t請選擇";break;case2:if(!T)cout<<"未建立樹，請先建樹！\n\t\t\t\t請重新選擇";//如果樹不存在則重新選擇創(chuàng)建樹else{cout<<"\n層序遍歷:\n";//遞歸層序遍歷LevelOrderTraverse(T);cout<<"\n\t\t\t\t請再選擇";}break;case3:if(!T)cout<<"未建立樹，請先建樹！\n\t\t\t\t請重新選擇";else{cout<<"\n先序遍歷:\n";//遞歸先序遍歷PreOrderTraverse(T);cout<<"\n\t\t\t\t請再選擇"<<endl;}break;case4:if(!T)cout<<"未建立樹，請先建樹！\n\t\t\t\t請重新選擇"; else{cout<<"\n中序遍歷:\n";//遞歸中序遍歷InOrderTraverse(T);cout<<"\n\t\t\t\t請再選擇"<<endl;}break;case5:if(!T)cout<<"未建立樹，請先建樹！\n\t\t\t\t請重新選擇";else{cout<<"\n后序遍歷:\n";//遞歸后序遍歷PostOrderTraverse(T);cout<<"\n\t\t\t\t請再選擇"<<endl;}break;default:cout<<"請確認(rèn)選擇項:\n\t\t\t\t請重新選擇";}//endswitch}//endwhile}c.調(diào)試分析1.數(shù)據(jù)結(jié)果2．時間復(fù)雜度分析很顯然遞歸樹的每種遍歷的時間復(fù)雜度都是o（n），但是非遞歸遍歷因為有進(jìn)棧和出棧的操作，因此時間復(fù)雜度為O（2n）。3.問題和解決方法在主函數(shù)中因為調(diào)用的函數(shù)中我還是帶有參數(shù)類型，導(dǎo)致編譯過程中出錯，當(dāng)時還沒認(rèn)真的發(fā)現(xiàn)，后來經(jīng)過查閱書籍后才看到這個明顯的錯誤，將類型去掉后，錯誤消失。在運行的時候，總覺得輸出不是很貼近人的表達(dá)，比如說，我還沒有建立樹，但我選擇4來遍歷，結(jié)果會出現(xiàn)中序遍歷但是后面沒內(nèi)容，會讓初次接觸的人不明白為什么，因此在輸出語句前加了一句if語句，判斷樹是否為空，若空則輸出“未建立樹”告知。然后主要問題是在運行時多次修改使之美觀化和一目了然化。當(dāng)然還有一些其他的小問題以后會多加注意。源程序代碼展示#include"iostream.h"#include"stdlib.h"#include"stdio.h"typedefcharElemType;//定義二叉樹結(jié)點值的類型為字符型constintMaxLength=20;//結(jié)點個數(shù)不超過20個typedefstructBTNode{ElemTypedata;structBTNode*lchild,*rchild;}BTNode,*BiTree;voidCreateBiTree(BiTree&T){//按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空節(jié)點charch;ch=getchar();if(ch=='')T=NULL;else{if(!(T=(BTNode*)malloc(sizeof(BTNode))))cout<<"mallocfail!";T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}}voidPreOrderTraverse(BiTreeT){//先序遍歷if(T){cout<<""<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}}voidInOrderTraverse(BiTreeT){//中序遍歷if(T){InOrderTraverse(T->lchild);cout<<""<<T->data;InOrderTraverse(T->rchild);}}voidPostOrderTraverse(BiTreeT){if(T){ PreOrderTraverse(T->lchild);//后序遍歷左子樹 PreOrderTraverse(T->rchild);//后序遍歷右子樹 cout<<""<<T->data;//訪問結(jié)點}}voidLevelOrderTraverse(BiTreeT){//層序遍歷BiTreeQ[MaxLength];intfront=0,rear=0;BiTreep;if(T){//根結(jié)點入隊Q[rear]=T;rear=(rear+1)%MaxLength;}while(front!=rear){p=Q[front];//隊頭元素出隊front=(front+1)%MaxLength;cout<<""<<p->data;if(p->lchild){//左孩子不為空，入隊Q[rear]=p->lchild;rear=(rear+1)%MaxLength;}if(p->rchild){//右孩子不為空，入隊Q[rear]=p->rchild;rear=(rear+1)%MaxLength;}}}voidmain(){BiTr