數(shù)據結構程序設計作業(yè)-《一元多項式的四則運算》

教學單位學生學號數(shù)據結構課程設計報告書題目一元多項式四那么運算 學生姓名專業(yè)名稱指導教師

目錄1問題描述 -2-2功能描述 -2-2.1課題要求 -2-2.2軟件格式規(guī)定 -2-3設計 -2-3.1相關函數(shù)介紹說明 -2-3.2主程序的流程基函數(shù)調用說明 -3-4程序設計 -5-4.1多項式存儲的實現(xiàn) -5-4.2加減乘除算法 -5-加法運算的實現(xiàn) -5-減法運算的實現(xiàn) -6-乘法運算的實現(xiàn) -7-除法運算的實現(xiàn) -7-4.3函數(shù)調用關系圖 -8-5運行測試 -9-6設計小結 -12-參考文獻 -12-謝辭 -13-附錄：程序清單 -14-

1問題描述1.1首先是確定結構化程序設計的流程圖，利用已學過的數(shù)據結構來構造二個存儲多項式的結構，接著把輸入，加，減，乘，除運算分成四個主要的模塊：實現(xiàn)多項式輸入模塊、實現(xiàn)加法的模塊、實現(xiàn)減法的模塊、實現(xiàn)乘法的模塊、實現(xiàn)除法的模塊，然后各個模塊里面還要分成假設干種情況來考慮并通過函數(shù)的嵌套調用來實現(xiàn)其功能。最后，編寫main主函數(shù)以實現(xiàn)對多項式輸入輸出以及加、減、乘、除，調試程序并將缺乏的地方加以修改?？偠灾?，就是先用自頂向下、逐步細化的設計方法來分析并畫出程序設計流程圖；然后用自下而上、逐步積累的設計方法來寫出程序。2功能描述2.1課題要求A.支持一元多項式的運算器B.能夠正確輸入并顯示輸入多項式的每一項C.要求將輸入的多項式F〔X〕，G(X)可進行加，減，乘，除運算，并顯示結果2.2軟件格式規(guī)定A．輸入的形式:按程序菜單的數(shù)字選擇輸入，并按提示輸入多項式。按照〔系數(shù)指數(shù)〕的格式進行輸入并以輸入〔00〕作為結束輸入的控制。B.程序所能到達的功能:能夠進行多項式的輸入，顯示，加，減，乘，除運算。C.輸出的形式:按照多項式的數(shù)學表達式的形式輸出，形如F(x)=X^2+2X^3-2X^4-3X^3-X^1+103設計3.1相關函數(shù)介紹說明〔1〕程序定義的數(shù)據結構類型為線性表的鏈式存儲結構類型變量：typedefstructlinknode〔2〕程序定義的其它函數(shù)：linnode*Sort(linnode*S);//多項式按指數(shù)從大到小排序linnode*CreateList();//創(chuàng)立多項式VoidShowList(linnode*head);//顯示多項式linnode*Copy(linnode*copy);//拷貝多項式〔因為做減法運算時會破壞原來輸入的多項式〕linnode*SearchList(linnode*head,intx);//查找函數(shù)Linnode*Mulr(linnode*s,linnode*p)//用一個節(jié)點去乘與一個多項式〔輔助除法運算〕Linnode*AddSame(linnode*head);//和并多項式的同類項linnode*Add(linnode*head1,linnode*head2);//加法linnode*Mul(linnode*head1,linnode*head2);//乘法linnode*Sub(linnode*head1,linnode*head2);//減法VoidDiv(linnode*head1,linnode*head2)//除法intmain()//主函數(shù)3.2主程序的流程基函數(shù)調用說明〔1〕主程序的簡要流程圖選擇界面菜單對應操作的數(shù)字結束執(zhí)行完選擇的功能后返回結果并回到程序主界面調用功能對應的函數(shù)main()選擇界面菜單對應操作的數(shù)字結束執(zhí)行完選擇的功能后返回結果并回到程序主界面調用功能對應的函數(shù)main()圖1主程序流程圖〔2〕各程序模塊之間的層次〔調用〕關系①輸入模塊“CreateList〔〕”，首先按提示逐項輸入多項式的每一項，當接收到“00”時終止輸入，此時調用“Sort〔〕”進行按指數(shù)降序排列后直接返回多項式的鏈表頭指針。②加法運算模塊“Add〔〕”，首先將兩個多項式連接成一個多項式，再調用“AddSame〔〕”函數(shù)進行合并連接后的多項式的同類項并返回頭指針。③減法運算程序模塊“Sub()”，首先判斷多項式1是否為空，不為空時調用“SearchList〔〕”進行查找操作，查找到的結果與多項式1作減法后刪除多項式2中查找到的對應項。多項式2中剩余的項取反后連接到多項式1的尾部，再調用“AddSame〔〕”進行合并同類項操作并返回頭指針。④乘法運算程序模塊“Mul()”，首先判斷輸入的多項式兩個不為空時進行多項式相乘運算，并將結構存儲在新創(chuàng)立的多項式中。再調用“AddSame〔〕”進行合并同類項后返回頭指針。⑥除法運算模塊“Div”，首先判斷第一個多項式的最高次數(shù)大于或等于第二多項式的最高次數(shù)，然后再用第一個多項式的第一項去除于第二個多項式的第一項，所得的商的第一項，然后調用“Mulr〔〕”用商的第一項去乘第二個多項式，用第一個多項式減去乘得的多項式，所得的差多項式再與第二個多項式的最高指數(shù)項判斷。直到第二多項式的最高次數(shù)項大于與之判斷的多項式時結束運算，并調用“ShowList〔〕”輸出相應的結果。⑥顯示函數(shù)“ShowList〔〕”，首先調用“Sort〔〕”進行排序，再按格式輸出多項式的每一項。4程序設計4.1多項式存儲的實現(xiàn)多項式是由假設干項構成的一個數(shù)學式子，其每一項包含系數(shù)與指數(shù)。然而我們可以把每一項看成是一個節(jié)點，再由這些節(jié)點連接成多項式。根據所學數(shù)據結構，采用線性表的鏈式存儲來存儲多項式的每一個項的系數(shù)與指數(shù)。其結構為：typedefstructlinknode//鏈表節(jié)點的結構體{ floatcoe;//系數(shù) intindex;//指數(shù) structlinknode*next;}linnode;4.2加減乘除算法在多項式運算的程序設計中，每一局部都會調用一些其它函數(shù)來輔助完成運算〔例如：對輸入的多項式進行排序，查找，合并等〕，在這里主要說明加減乘除運算的程序設計，其它函數(shù)的程序設計和具體調用關系請查看程序清單。開始加法計算還是比擬容易實現(xiàn)的，將兩個傳遞過來的多項式鏈表進行復制操作〔加法運算會破壞原來兩個鏈表的結構〕，再將復制出來的兩鏈表進行連接操作，即將第一個多項式鏈表的尾指針next指向第二個鏈表的第一個節(jié)點，最后進行合并同類項操作。開始復制兩個多項式復制兩個多項式連接兩個多項式連接兩個多項式合并連接好的多項式的同類項合并連接好的多項式的同類項返回合并同類項后的多項式頭指針返回合并同類項后的多項式頭指針結束結束圖2加法運算原理圖對于加法運算我們并不用考慮多項式是否為空的情況，為空時連接后合并同類項處理后仍然返回空的多項式。多項式的減法與加法類似，先將傳遞進來的兩個多項式進行判斷是否為空，假設被減數(shù)為空時，減數(shù)按逐項系數(shù)取反操作。不為空時，被減數(shù)的每一項的指數(shù)去查找減數(shù)中與之對應的項，找到后并同類項相減，把值賦給被減數(shù)與之對應的同類項，再在減數(shù)中刪除查找到的那個項〔節(jié)點〕。徹底查找后，將減數(shù)剩余的節(jié)點取反后再連接到被減數(shù)的末尾，在進行合并同類項操作并返回頭指針。開始開始被減數(shù)是否為空被減數(shù)是否為空是被減數(shù)每一項查找減數(shù)與之對應的項否被減數(shù)每一項查找減數(shù)與之對應的項找到 未找到加法操作，并將值賦給被減數(shù)加法操作，并將值賦給被減數(shù)被減數(shù)與減數(shù)取反后連接被減數(shù)與減數(shù)取反后連接合并同類項合并同類項結束結束圖3減法運算原理圖開始多項式的乘法運算，首先是判斷多項式都不為空，為空時直接輸出結過為0。否那么將其中一個多項式的每一項去乘于另外個多項式的每一項，將乘得每一項的結果連接成一個完整的多項式，然后在對其進行合并同類項操作。最后返回結果頭指針。開始判斷兩個多項式是否都為空判斷兩個多項式是否都為空多項式兩兩相乘否多項式兩兩相乘合并同類項合并同類項結束是結束圖4乘法運算原理圖首先將相除的兩個多項式降序排列，兩個多項式為非空時。判斷被除數(shù)的最高次冪大于或等于除數(shù)的最高次冪，然后用被除數(shù)的第一項去除于除數(shù)的第一項所得商的第一項，在用所得商的這一項去乘除數(shù)的所有項所得的多項式與被減數(shù)作差，在用所得差作為被減數(shù)。循環(huán)上述步驟，當被減數(shù)最高次冪小于減數(shù)最高次冪是終止循環(huán)，輸出相應的結果。開始開始判斷兩個多項式是否都為空判斷兩個多項式是否都為空判斷最高次冪被減數(shù)>=減數(shù)否判斷最高次冪被減數(shù)>=減數(shù)相除得商的第一項是相除得商的第一項乘與被除數(shù)乘與被除數(shù)被除數(shù)減去所得多項式得到的結果作為被除數(shù)被除數(shù)減去所得多項式得到的結果作為被除數(shù)輸出商和余數(shù)否輸出商和余數(shù)結束是結束圖5除法運算原理圖在程序設計時應注意:由于在輸入多項式的時候就調用了Sort〔〕函數(shù)進行降序排序，因此在除法運算時并不需要從新排序。4.3函數(shù)調用關系圖此函數(shù)調用關系圖主要描述了四那么運算的實現(xiàn)、取反及實現(xiàn)各運算所要調用的函數(shù)，詳情還請看程序清單。Sort()排序ShowList()顯示輸出SearchList()搜索SearchList()搜索SearchList()搜索SearchList()搜索節(jié)點AddSame()合并Negate()取反AddSame()合并AddSame()合并Mulr()Div除法運算Copy()備份Sub()減法運算AddSame()合并Sort()排序Copy()備份Mul()乘法運算Add()加法運算CreateList()創(chuàng)立main〔〕選擇菜單Sort()排序ShowList()顯示輸出SearchList()搜索SearchList()搜索SearchList()搜索SearchList()搜索節(jié)點AddSame()合并Negate()取反AddSame()合并AddSame()合并Mulr()Div除法運算Copy()備份Sub()減法運算AddSame()合并Sort()排序Copy()備份Mul()乘法運算Add()加法運算CreateList()創(chuàng)立main〔〕選擇菜單圖6函數(shù)調用關系圖5運行測試圖7主界面效果圖圖8按1輸入多項式圖9輸入測試數(shù)據圖10顯示輸入的測試多項式圖11多項式相加圖12多項式相減圖13多項式相乘圖14多項式相除6設計小結《數(shù)據結構課程設計》是一門實踐性的計算機課程，為了學好這門課程，必須在掌握理論知識的同時，加強上機實踐。通過本課程的學習，能熟練掌握幾種根本數(shù)據結構的根本操作。能針對給定題目，選擇相應的數(shù)據結構，分析并設計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。同時，在設計方法以及上機操作等根本技能和科學作風方面受到比擬系統(tǒng)和嚴格的訓練。參考文獻[1]嚴蔚敏

吳偉民

《數(shù)據結構〔C語言版〕》北京：清華大學出版社

2002[2]譚浩強《C語言程序設計(第三版)》

謝辭感謝李志敏老師的殷切輔導，給予我?guī)椭?。幫我答疑解惑，從未知的迷茫道路上，漸漸走向光明的成功之路。

附錄：程序清單#include"stdlib.h"#include"iostream"typedefstructlinknode//定義節(jié)點的結構體{ floatcoe; intindex; structlinknode*next;}linnode;//定義節(jié)點類型linnkodelinnode*Sort(linnode*S)//多項式按降序排列{ linnode*z,*s; s=S; z=newlinnode; z->next=NULL; while(S->next!=NULL) { for(linnode*x=S->next;x->next!=NULL;x=x->next) { if(S->next->index<x->next->index) { z->coe=x->next->coe; x->next->coe=S->next->coe; S->next->coe=z->coe; z->index=x->next->index; x->next->index=S->next->index; S->next->index=z->index; } } S=S->next; } returns;}linnode*CreateList()//創(chuàng)立線性表{ intn=0,z=1; linnode*p,*s,*head; floatcoe; intindex; head=newlinnode; head->next=NULL; p=head; while(z) {printf("\n\t\t請輸入："); scanf("%f",&coe);scanf("%d",&index); getchar(); if(coe!=0||index!=0) { s=newlinnode; s->coe=coe; s->index=index; p->next=s; s->next=NULL; p=s; } else z=0; } returnSort(head);}voidShowList(linnode*head) //顯示線性表{ linnode*P=Sort(head); if(head->next==NULL) printf("多項式為空！"); else { while(P->next!=NULL) {if((P->next->coe)!=0) {(P->next->coe)>0?printf("+%5.2f",P->next->coe):printf("%5.2f",P->next->coe); (P->next->index)!=0?printf("X^%d",P->next->index):printf(""); } P=P->next; } }}linnode*Copy(linnode*copy){linnode*d,*head3,*a; d=newlinnode; head3=d; if(copy->next!=NULL) {while(copy->next!=NULL){ a=newlinnode; a->coe=copy->next->coe; a->index=copy->next->index; d->next=a; a->next=NULL; d=a; copy=copy->next; } returnhead3; } else returncopy;}linnode*SearchList(linnode*head,intx)//查找函數(shù){ linnode*p; if(head!=NULL) {p=head->next; while(p!=NULL&&p->index!=x) { p=p->next; } if(p!=NULL) returnp; else returnNULL; } elsereturnNULL;}linnode*AddSame(linnode*head)//合并同類項{ linnode*heads,*s,*z; heads=head; while(head->next!=NULL) { linnode*x=SearchList(head->next,head->next->index);//搜索相同節(jié)點 if(x!=NULL) { head->next->coe+=x->coe; for(s=head->next;(s->next->index)!=x->index;) s=s->next; s->next=x->next; deletex; } elsehead=head->next; } returnheads;}linnode*Sub(linnode*head1,linnode*head2)//多項式做減法函數(shù),并向函數(shù)傳遞兩個鏈表〔即兩個待相加的多項式〕{ linnode*s,*p,*head3;//定義三個節(jié)點指針變量 s=head1; head3=s;//用于存儲第一個傳進來的鏈表的頭指針 p=head2; while(s->next!=NULL)//當?shù)谝粋€鏈表不為空時依次循環(huán)獲取每一個節(jié)點的index值 { linnode*z=SearchList(p,s->next->index);//用于搜索第一鏈表的每個節(jié)點的index值在第二鏈表中是否存在并返回其節(jié)點 if(z!=NULL)//條件為真是，即在第二鏈表中查找到與第一鏈表中相同index值的節(jié)點 { s->next->coe-=z->coe; while((p->next->index)!=z->index)//用于查找搜索到節(jié)點在第二鏈表中的位置 { p=p->next; } p->next=z->next; deletez;//在第二鏈表中刪除查找到的節(jié)點 } s=s->next;//頭指針向后移動 } for(s->next=head2->next;s->next!=NULL;s=s->next) s->next->coe=-(s->next->coe); returnAddSame(head3);//返回第一鏈表的頭指針}linnode*Add(linnode*head1,linnode*head2)//多項式加法函數(shù){ linnode*s,*p,*d,*a,*head3; s=head1; p=head2; d=newlinnode; head3=d; while(s->next!=NULL){ a=newlinnode; a->coe=s->next->coe; a->index=s->next->index; d->next=a; a->next=NULL; d=a; s=s->next; } while(p->next!=NULL){ a=newlinnode; a->coe=p->next->coe; a->index=p->next->index; d->next=a; a->next=NULL; d=a; p=p->next; } returnAddSame(head3);//合并同類項后返回}linnode*Mul(linnode*s,linnode*p)//多項式作乘法運算函數(shù)，兩個參數(shù)用于傳進兩個待相乘的多項式鏈表{ linnode*head1,*head2,*head3,*n,*head4;//定義鏈表指針用于存儲多項式的節(jié)點指針 head1=s;//將第一個用于存儲多項式的鏈表的頭指針賦值給head1 head2=p;//將第二個用于存儲多項式的鏈表的頭指針賦值給head2 head4=newlinnode;//創(chuàng)立一個頭節(jié)點 head4->next=NULL; head3=head4;//用于存儲新創(chuàng)立的鏈表的頭指針 if(head1->next!=NULL&&head2->next!=NULL)//兩個多項式不為空時 { for(;head1->next!=NULL;head2=p,head1=head1->next)//此循環(huán)用于實現(xiàn)多項式中的乘法運算 { for(;head2->next!=NULL;head2=head2->next)//此循環(huán)用于實現(xiàn)多項式中的乘法運算 { n=newlinnode;//新建一個節(jié)點用于存儲多項式相乘之后每一項的結果 n->coe=(head1->next->coe*head2->next->coe);//系數(shù)相乘 n->index=(head1->next->index+head2->next->index);//指數(shù)相加 head3->next=n; n->next=NULL; head3=n; } } returnAddSame(head4); } else returnhead4;}linnode*Mulr(linnode*s,linnode*p)//一個節(jié)點乘與整個多項式〔輔助除法運算〕{ linnode*head2,*n,*head1,*head; head2=newlinnode; head2->next=NULL; head=head2; head1=p; while(p->next!=NULL&&s->coe!=0) { n=newlinnode; n->coe=s->coe*p->next->coe; n->index=s->index+p->next->index; n->next=NULL; head2->next=n; head2=n; p=p->next; } p=head1; returnhead;}voidDiv(linnode*head1,linnode*head2)//除法{ linnode*temp1,*head3,*head4,*z; temp1=newlinnode; temp1->next=NULL; head3=temp1;//商 while(head1!=NULL&&head1->next!=NULL&&head1->next->index>=head2->next->index)//判斷指數(shù)大小 { z=newlinnode; z->coe=head1->next->coe/head2->next->coe; z->index=head1->next->index-head2->next->index; temp1->next=z; z->next=NULL; temp1=z; head4=Mulr(z,head2); linnode*head5=head1; while(head1->next!=NULL) { head1=head1->next; } head1->next=head4->next; head1=AddSame(head5);//合并 while(head1->next!=NULL&&head1->next->coe==0) { head1=head1->next; } }printf("\nF(X)/G(X)"); printf("\n商："); ShowList(head3); printf("\n余數(shù)："); ShowList(head1);}intmain(){ system("color0F"); intchoice,j=1; linnode*head1,*head2,*add,*sub,*mul,*copy1,*copy2; add=newlinnode; sub=newlinnode; mul=newlinnode; head1=newlinnode;head2=newlinnode; copy1=newlinnode; copy2=newlinnode; head1->next=NULL;head2->next=NULL; head1->index=NULL;head2->index=NULL; add->next=NULL; sub->next=NULL; mul->next=NULL; copy1->next=NULL; copy2->next=NULL; while(j) { system("ColorE0"); printf("\n"); printf("\n\t\t一元多項式的四那么運算"); printf("\n"); printf("\n\t\t1輸入多項式"); printf("\n\t\t2顯示多項式"); printf("\n\t\t3相加"); printf("\n\t\t4相減"); printf("\n\t\t5相乘"); printf("\n\t\t6相除"); printf("\n\t\t0退出"); printf("\n"); printf("\n\t\t請選擇菜單號〔0--6〕進行操作:"); scanf("%d",&choice); getchar(); if(choice==1) { head1->next=NULL;head2->next=NULL; printf("\n\t\t請逐個輸入第1個多項式的結點