元稀疏多項式的計算

1、實驗二一元稀疏多項式的計算一、實驗?zāi)康膸椭鷮W(xué)生熟練掌握線性表的基本操作，以及用線性鏈表表示線性表的存儲結(jié)構(gòu)和操作的實現(xiàn).二、實驗內(nèi)容實現(xiàn)一元稀疏多項式的如下運算：(1)兩個一元稀疏多項式相加運算(2)兩個一元稀疏多項式相減運算(3)兩個一元稀疏多項式相乘運算三、實驗儀器微型計算機實驗用編程語言：TurboC2.0,BorlandC3.0等以上版本四、實驗原理1、一元多項式的邏輯表示一兀多項式Pn(X)可表不成：Pn(X)=P0+piX+p2X2+,+pnXnn+1個系數(shù)可用線性表來表示：(p。，p1,p2,pn)每一項的指數(shù)i隱含在其系數(shù)pi的序號中.一個一元多項式，如果其系數(shù)不為0的項相對于

2、其多項式的次數(shù)(最大指數(shù))而言要少得多，則稱該一元多項式為一元稀疏多項式.對一元稀疏多項式，若采用順序存儲結(jié)構(gòu)，需n+1個元素單元存放系數(shù).當(dāng)n很大且為零的系數(shù)較多時，既浪費存儲空間，又浪費運算時間如：s(x)=1+3x10000+2x20000采用順序存儲分配需20001個元素空間，但只有3個元素有意義.若參與同數(shù)量級的加法運算，要運行2000次以上.因此，對一元多項式采用鏈?zhǔn)酱鎯Y(jié)構(gòu)是必然的選擇.上例的鏈表表示形式如圖1所示.圖1:一元稀疏多項式的鏈表表示示意圖2、一元稀疏多項式的鏈?zhǔn)揭氯姑鲜窘Y(jié)點結(jié)構(gòu)定義如下：typedefstructItemdoublecoef;1/15intexpn;

3、structItem*next;Item,*Polyn;3、一元稀疏多項式運算原理設(shè)有兩個稀疏多項式A和B,其運算原理如下：(1)兩個多項式相加(C=A+B)的運算原則：指數(shù)相同，系數(shù)相加，若不為0,則在結(jié)果多項式中構(gòu)成一新項.指數(shù)不同，則兩項分別抄入結(jié)果多項式中.(2)兩個多項式相減(C=AB)的運算原則：指數(shù)相同，系數(shù)相減，若不為0,則構(gòu)成一新項.指數(shù)不同，對A多項式的項，直接抄入結(jié)果多項式中對B多項式的項，系數(shù)符號變換后，再將放入結(jié)果多項式中(3)兩個多項式相乘(C=AXB)的運算原則用B多項式的每一項分別去乘A多項式的每一項，并將乘得得結(jié)果放入結(jié)果多項式中.若結(jié)果多項式中有指數(shù)相同的項

4、，則應(yīng)把它們合并為一項五、實現(xiàn)1、約定使用帶頭結(jié)點的鏈表表示一元稀疏多項式.(2)用線性鏈表表示的一元稀疏多項式中，各結(jié)點按指數(shù)的升序排列(3)每個多項式都獨立存在，即參與運算的兩個多項式的數(shù)據(jù)不能應(yīng)運算而受到破壞，加、減、乘運算的結(jié)果應(yīng)相互不受影響.因此，對于每種情況都必須單獨建立一個鏈表進(jìn)行表本.(4)每一種重復(fù)性的操作都要進(jìn)行確認(rèn)，以免破壞原有操作的結(jié)果.如需要輸入A多項式，而A多項式已經(jīng)存在，這時通過“確認(rèn)”后再確定是否真正需要輸入2、基本功能(1)多項式的輸入(2)兩個一元稀疏多項式相加運算：P(x)+Q(x(3)兩個一元稀疏多項式相減運算：P(x)Q(x)(4)兩個一元稀疏多項式相

5、乘運算：P(x)XQ(x)(5)多項式打印3、輔助功能(1)菜單選擇：將上述功能通過“菜單”形式羅列出來，通過菜單選擇進(jìn)行交互式控制程序運行.(2)插入結(jié)點位置查找：確定將一個新結(jié)點插入到多項式鏈表結(jié)構(gòu)中的位置，以保2/15證鏈表中結(jié)點按指數(shù)升序排列(3)交互選擇：當(dāng)出現(xiàn)重復(fù)性操作時，提供交互式選擇方式，以確定其重復(fù)操作是否進(jìn)行.(4)撤消多項式：釋放表示多項式鏈表中所有結(jié)點的存儲空間(5)多項式項插入：將表示多項式中一項的結(jié)點插入到鏈表中給定的位置.(6)判多項式非空：判斷某個多項式是否存在(7)判斷兩個多項式的當(dāng)前運算項的關(guān)系(指數(shù)大于，等于，小于)4、程序結(jié)構(gòu)1個，基本功能函數(shù)5個，輔助

6、功能函數(shù)本程序可以由13個函數(shù)組成，其中主函數(shù)7個.函數(shù)間的調(diào)用關(guān)系圖2所示.步要操作的功能表不生成P多項式表示生成Q多項式表小兩多項式相加表示兩多項式相減表小兩多項式相乘表示打印P多項式表示打印Q多項式表示打印兩多項式相加的結(jié)果表示打印兩多項式相減的結(jié)果(2)菜單選擇函數(shù)：menu函數(shù)格式：intmenu(void)函數(shù)功能：構(gòu)造功能菜單，并選擇下函數(shù)參數(shù)：無參數(shù).函數(shù)返回值：111中的一個序號可供選擇的功能如下：1-createP(x)2-createQ(x)3-p(x)+Q(x)4-P(x)-Q(x)5-p(x)*Q(x)6-printP(x)7-printQ(x)8-printP(x)

7、+Q(x)9-printP(x)-Q(x)3/1510-printP(x)*Q(x)表示打印兩多項式相乘的結(jié)果11Quit表示退出系統(tǒng)，結(jié)束程序的運行在運行過程中，輸入其中一個序號，即表示下一步執(zhí)行后面的功能.如輸入3,表示執(zhí)行P(x)+(x)額運算.輸入多項式函數(shù)：input函數(shù)格式：PolynInput(void)函數(shù)參數(shù)：無參數(shù)函數(shù)功能：輸入多項式各項的系數(shù)和指數(shù)，生成一個多項式鏈表函數(shù)返回值：指向一個多項式鏈表的頭指針(4)兩多項式相加函數(shù)：AddPolyn函數(shù)格式PolynAddPolyn(Polynh1,Polynh2)函數(shù)功能：實現(xiàn)兩個多項式h1和h2相加.函數(shù)參數(shù)：Polynh

8、1一指向第一個多項式鏈表的頭指針Polynh2一指向第二個多項式鏈表的頭指針函數(shù)返回值：指向相加后的結(jié)果鏈表的頭指針(5)兩多項式相減函數(shù)：SubtractPolyn函數(shù)格式PolynSubtractPolyn(Polynh1,Polynh2)函數(shù)功能：實現(xiàn)兩個多項式h1和h2相減.函數(shù)參數(shù)：Polynh1一指向第一個多項式鏈表的頭指針Polynh2一指向第二個多項式鏈表的頭指針函數(shù)返回值：指向相減后的結(jié)果鏈表的頭指針(6)兩多項式相乘函數(shù)：MultPolyn函數(shù)格式PolynMultPolyn(Polynh1,Polynh2)函數(shù)功能：實現(xiàn)兩個多項式h1和h2相乘.函數(shù)參數(shù)：Polynh1一

9、指向第一個多項式鏈表的頭指針Polynh2一指向第二個多項式鏈表的頭指針函數(shù)返回值：指向相乘后的結(jié)果鏈表的頭指針(7)顯示多項式函數(shù)：Output函數(shù)格式：voidOutput(Polynh,char*title)函數(shù)功能：輸出多項式的完整表示.如：P(x)=1.00+2.50xA3-3.5xA9函數(shù)參數(shù)：Polynh要輸出的多項式鏈表的頭指針char*title字符串，提示要輸出一個什么樣的多項式，如“P(x)”.函數(shù)返回值：無返回值.(8)判斷選擇函數(shù)：Select4/15函數(shù)格式：intSelect(char*str)函數(shù)功能：根據(jù)str提示的內(nèi)容判斷是執(zhí)行指定的操作，還是不執(zhí)行.輸入“

10、Y”則表示執(zhí)行，若輸入“N”表示不執(zhí)行.如當(dāng)P(x)多項式已經(jīng)產(chǎn)生后，若再選擇產(chǎn)生P(x),這是提示：P(x)isnotEmpty,CreateP(x)again?InputYorN:若輸入“Y”則表示重新產(chǎn)生多項式P(x),若輸入“N”表示維持原多項式不變.函數(shù)參數(shù)：char*str將要確定的內(nèi)容.函數(shù)返回值：1表示執(zhí)行指定的操作0-表示不執(zhí)行指定的操作(9)插入位置定位函數(shù)：InsertLocate函數(shù)格式：intInsertLocate(Polynh,intexpn,Item*p)函數(shù)功能：確定新結(jié)點的插入位置.其插入位置的確定是保證多項式鏈表按指數(shù)遞增排列的關(guān)鍵.函數(shù)參數(shù)：Polynh

11、要查找的多項式鏈表的頭指針intexpn一新插入項的指數(shù)值.Item*p插入位置的前驅(qū)結(jié)點指針，由該函數(shù)的調(diào)用而被確定的內(nèi)容.新結(jié)點一定插入到該結(jié)點的后面.函數(shù)返回值：-1若指數(shù)expn值在某兩個結(jié)點之間，則返回1,參數(shù)p帶回的值為指數(shù)值小于expn的結(jié)點指針.0若指數(shù)expn值等于某結(jié)點的指數(shù)值，則返回0,參數(shù)p帶回的值為指數(shù)值等于expn的結(jié)點指針.1-若指數(shù)expn值大于最后一個結(jié)點的指數(shù)值，則返回1,參數(shù)p帶回最后一個結(jié)點的指針(10)結(jié)點插入函數(shù)：insert函數(shù)格式：voidinsert(Item*pre,Item*p)函數(shù)功能：在指定結(jié)點pre后插入一個新結(jié)點p.函數(shù)參數(shù)：Ite

12、m*pre被插入結(jié)點的前驅(qū)結(jié)點Item*p一要插入的新結(jié)點函數(shù)返回值：無(11)撤消鏈表函數(shù)：Destroy函數(shù)格式：voidDestroy(Polynh)函數(shù)功能：釋放鏈表所占用的存儲空間函數(shù)參數(shù)：Polynh一被撤消的鏈表的頭指針函數(shù)返回值：無(12)判鏈表非空函數(shù)：PolynNotEmpty5/15函數(shù)格式：intPolynNotEmpty(Polynh,char*p)函數(shù)功能：判斷鏈表是否非空，即代表了一個真正的多項式函數(shù)參數(shù)：Polynh一多項式鏈表的頭指針char*p多項式名函數(shù)返回值：0鏈表為空1一鏈表不為空(13)比較多項式兩項關(guān)系函數(shù)：ItemComp函數(shù)格式：intItem

13、Comp(ItemxItemy)函數(shù)功能：根據(jù)兩個多項式項的指數(shù)判斷它們的關(guān)系函數(shù)參數(shù)：Itemx表示多項式項的變量Itemy一表示多項式項的變量函數(shù)返回值：-1-x項的指數(shù)小于y項的指數(shù)0x項的指數(shù)等于y項的指數(shù)1x項的指數(shù)大于y項的指數(shù)六、兩個多項式的相乘運算算法【算法1】把Q(x)多項式的每一項分別去乘P(x)多項式的每一項所得到的每一個結(jié)果(一個結(jié)點)插入到結(jié)果多項式中，若結(jié)果多項式中無相同指數(shù)的項，則生成一個新結(jié)點插入；若有相同指數(shù)的項，則系數(shù)相加.算法如下：6/157/15函數(shù)接口：傳入多項式鏈表指針h1,h2初始化結(jié)果多項式鏈表h3Pb=h2->next;Pa=h1->

14、;next;CreateItem(h4);/.初始化鏈表h4Pa!=NULLL申請結(jié)點ss->expn=pb->expn+pa->expn;s->coef=pb->coef*pa->coef把結(jié)點s插亮鄴a網(wǎng)刎尾部多項式h3與h4相加，結(jié)果為h5撤消鏈表h3和h4,h5=>h3Pb!=NULLLreturn(h3)pb=pb->next七、思考題修改一元多項式相加運算的函數(shù)，實現(xiàn):1、兩個有序表合并為一個有序表.2、假設(shè)具有整數(shù)值的集合用有序的線性鏈表表示，實現(xiàn)求兩個集合的聯(lián)合運算，要求結(jié)果集合中不能有兩個值相同的元素.八、部分函數(shù)代碼卜面給出了

15、幾乎所有的【說明】：為了使學(xué)生掌握復(fù)雜程序設(shè)計的基本方法和程序的結(jié)構(gòu),輔助函數(shù)的程序代碼，學(xué)生只需要完成稀疏多項式的加、減、乘運算的程序代碼編寫工作希望學(xué)生通過下面程序代碼的閱讀、編碼、測試和運算，掌握一個完整程序的基本結(jié)構(gòu)和設(shè)計一個程序的基本方法#include<stdio.h>#include<stdlib.h>#include<conio.h>typedefstructItem8/15doublecoef;intexpn;structItem*next;Item,*Polyn;#defineCreateItem(p)p=(Item*)malloc(si

16、zeof(Item);#defineDeleteItem(p)free(void*)p);/*/*判斷選擇函數(shù)*/*/intSelect(char*str)charch;printf("%sn",str);printf("InputYorN:");doch=getch();while(ch!='Y'&&ch!='y'&&ch!='N'&&ch!='n');printf("n");if(ch='Y'|ch=&#

17、39;y')return(1);elsereturn(0);/*/*插入位置定位函數(shù)*/*/intInsertLocate(Polynh,intexpn,Item*p)Item*pre,*q;pre=h;q=h->next;while(q&&q->expn<expn)pre=q;q=q->next;if(!q)*p=pre;return(1);elseif(q->expn=expn)*p=q;return(0);else*p=pre;return(-1);9/15，*/*插入結(jié)點函數(shù)*/*/voidinsert(Item*pre,Item*

18、p)(p->next=pre->next;pre->next=p;)/*/*輸入多項式*/*/PolynInput(void)(doublecoef;intexpn,flag;Item*h,*p,*q,*pp;CreateItem(h);/產(chǎn)生頭結(jié)點h->next=NULL;printf("inputcoefandexpn(ifend,expn=-1)n");while(1)(scanf("%lf%d",&coef,&expn);if(expn=-1)break;/if(InsertLocate(h,expn,&a

19、mp;pp)/CreateItem(p);p->coef=coef;輸入多項式的系數(shù)和指數(shù)若指數(shù)為-1,表示輸入結(jié)束返回值非0表示插入新結(jié)點p->expn=expn;insert(pp,p);)elseif(Select("hasthesameexpn,Replaceoldervalue?")pp->coef=coef;/指數(shù)相同，替換系數(shù))returnh;)/*/*撤消多項式*/*/voidDestroy(Polynh)Item*p=h,*q;while(p!=NULL)q=p;10/15p=p->next;Deleteltem(q);)/*/*輸

20、出多項式*/*/voidOutput(Polynh,char*title)intflag=1;Item*p=h->next;printf("%s=",title);while(p)if(flag)/flag=0;if(p->expn=0)表示是否是多項式的第一項printf("%.2lf",p->coef);elseprintf("%.2lfxA%d",p->coef,p->expn);)elseif(p->coef>0)printf("+");if(p->expn=

21、0)printf("%.2lf",p->coef);elseprintf("%.2lfxA%d",p->coef,p->expn);)p=p->next;)printf("n");)/*/*判斷兩個多項式項的關(guān)系*/*/intItemComp(Itemx,Itemy)if(x.expn<y.expn)return(-1);elseif(x.expn=y.expn)return(0);elsereturn(1);)/*/*兩多項式多項式相加*/*/PolynAddPolyn(Polynh1,Polynh2)

22、Item*head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;11/15doublecoef;Createltem(head);last=head;last->next=NULL;returnhead;實現(xiàn)兩個多項式相加運算的代碼（由學(xué)生獨立完成）/*/*兩多項式多項式相減*/*/PolynSubtractPolyn(Polynh1,Polynh2)intflag;Item*head,*last,*pa=h1->next,*pb=h2->next,*s,*s0;doublecoef;CreateItem(head);last=h

23、ead;last->next=NULL;returnhead;實現(xiàn)兩個多項式相減運算的代碼（由學(xué)生獨立完成）/*/*兩多項式多項式相乘*/*/PolynMultPolyn(Polynh1,Polynh2)/intitem,expn;Item*head,*pa,*pb=h2->next,*s,*pp;doublecoef;CreateItem(head);head->next=NULL;兩個多項式相乘returnhead;實現(xiàn)兩個多項式相乘運算的代碼（由學(xué)生獨立完成）/*/*菜單選擇*/*/intmenu(void)intnum;clrscr();printf("%2

24、0c1-createP(x)n",'');printf("%20c2-createQ(x)n",'');printf("%20c3-p(x)+Q(x)n",'');printf("%20c4-P(x)-Q(x)n",'');printf("%20c5-p(x)*Q(x)n",'');12/15printf("%20c6-printP(x)n",'');printf("%20c7-p

25、rintQ(x)n",'');printf("%20c8-printP(x)+Q(x)n",'');printf("%20c9-printP(x)-Q(x)n",'');printf("%20c10-printP(x)*Q(x)n",'');printf("%20c11-Quitn",'');printf("pleaseselect1,2,3,4,5,6,7,8,9,10,11:");doscanf(&qu

26、ot;%d",&num);while(num<1|num>11);return(num);/*/*判斷多項式是否存在*/*/intPolynNotEmpty(Polynh,char*p)if(h=NULL)printf("%sisnotexist!n",p);getchar();return(0);elsereturn(1);/*/*主函數(shù)*/*/voidmain()intnum;Polynh1=NULL;/p(x)Polynh2=NULL;Q(x)Polynh3=NULL;/P(x)+Q(x)Polynh4=NULL;/P(x)-Q(x)Po

27、lynh5=NULL;/P(x)*Q(x)while(1)num=menu();getchar();switch(num)case 1: /輸入第一個多項式，若多項式存在，首先撤消然后再輸入if(h1!=NULL)if(Select("P(x)isnotEmpty,CreateP(x)again?")Destroy(h1);h1=Input();13/15)elseh1=Input();break;case 2: /輸入第二個多項式，若多項式存在，首先撤消然后再輸入if(h2!=NULL)if(Select("Q(x)isnotEmpty,CreateQ(x)ag

28、ain?")Destroy(h2);h2=Input();)elseh2=Input();break;case 3: /兩多項式相加if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)”)h3=AddPolyn(h1,h2);Output(h3,"P(x)+Q(X)");printf("P(x)+Q(x)hasfinished!n");getchar();)break;case 4: /兩多項式相減if(PolynNotEmpty(h1,"p(x)")&&PolynNotEmpty(h2,"Q(X)”)h4=SubtractPolyn(h1,h2);Output(h4,"Px)-Q(x)");printf("P(x)-Q(x)hasfinished!n&quo