一元多項式相加 數(shù)據(jù)結(jié)構(gòu)實驗報告

1、南昌航空大學(xué)實驗報告課程名稱： 數(shù)據(jù)結(jié)構(gòu) 實驗名稱： 實驗二 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 班 級： 080611 學(xué)生姓名： 學(xué)號： 08 指導(dǎo)教師評定： 簽 名: 題目：設(shè)計并實現(xiàn)以下算法：給出用單鏈表存儲多項式的結(jié)構(gòu)，利用后接法生成多項式的單鏈表結(jié)構(gòu)，實現(xiàn)兩個多項式相加的運算，并就地逆置相加后的多項式鏈?zhǔn)?。一?需求分析1. 用戶可以根據(jù)自己的需求分別輸入兩個一元多項式，并且能夠?qū)崿F(xiàn)輸入的一元多項式的顯示。2. 能夠完成兩個一元多項式的相加功能，而且還能顯示相加后的逆置的一元多項式。3. 程序執(zhí)行的命令包括：（1）構(gòu)造鏈表A （2）構(gòu)造鏈表B （3）兩個鏈表的相加 （4）求鏈表的長度 （5）打印

2、（顯示）已有的鏈表 （6）將已相加的鏈表進行逆序排列二、概要設(shè)計 為實現(xiàn)上述算法，需要線性表的抽象數(shù)據(jù)類型：ADT Polynomial 數(shù)據(jù)對象：D=ai:|aiTermSet,i=1n,n0TermSet 中的每個元素包含一個表示系數(shù)的實數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：R1=<ai-1,ai>|ai-1,aiD,且ai-1中的指數(shù)值< ai 中的指數(shù)值i=2,n0基本操作:initlink(& L)操作結(jié)果：構(gòu)造一個空的鏈表L。 Creatlink(&L,n) 操作結(jié)果：輸入n項的系數(shù)和指數(shù)，建立一個非空的一元多項式L。LinkLength(L)初始條件：鏈表

3、L已經(jīng)存在。操作結(jié)果：返回一元多項式L中的項數(shù)。 Displaylink（L） 初始條件：鏈表L已經(jīng)存在。 操作結(jié)果：打印輸出一元多項式L。Addpolyn(A,B,&C)初始條件：一元多項式A和B已存在。操作結(jié)果：完成多項式相加運算，即：C=A+B，并且?guī)Щ谻。subtracypolyn(&La,&Lb,)初始條件：一元多項式La和Lb已存在。操作結(jié)果：完成多項式的相減運算La=La+Lb，并且銷毀多項式Lb。Multiplypolyn(&La ,&Lb)初始條件：多項式La，Lb已經(jīng)存在。操作結(jié)果：完成多項式的相乘運算，即La=La*Lb，并銷毀多項

4、式Lb。Changlink（L） 初始條件：一元多項式L已經(jīng)存在。 操作結(jié)果：完成多項式的逆置功能，即將鏈表逆置。ADT Polynomial2. 本程序有三個模塊： 主程序模塊 main()初始化；接受命令；顯示結(jié)果； 鏈表單元模塊：實現(xiàn)鏈表抽象數(shù)據(jù)類型操作，即函數(shù)的定義模塊；三、詳細設(shè)計元素類型，結(jié)點類型typedef struct lnode float num; int expn; struct lnode *next;*linklist,lnode; linklist initlink() linklist p; p=(lnode*)malloc(sizeof(lnode); p-&

5、gt;next=null; return p;2.對抽象數(shù)據(jù)類型中的部分基本操作的偽碼算法如下：/*創(chuàng)建一個非空鏈表*/linklist creatlink(linklist p,float a,int b,int n) linklist r,s; int i; r=p; for(i=0;i<n;i+) s=(lnode*)malloc(sizeof(lnode); s->num=ai; s->expn=bi; r->next=s; r=s; r->next=null; return p;/*求鏈表的長度*/int length(linklist p) int n

6、=0; linklist q=p->next; while(q!=null) n+; q=q->next; return n;/*顯示鏈表*/void display(linklist p) int n=length(p),i; linklist q=p->next; if(n=0) printf("The Polymial is nulln"); else if(n=1) printf("%3.1f%3d",q->num,q->expn); else for(i=1;i<n;i+) printf("%3.1

7、f%3d->",q->num,q->expn); q=q->next; printf("%3.1f%3d",q->num,q->expn); printf("n");/*比較指數(shù)*/int cmpexpn(int expn1,int expn2) if(expn1>expn2) return -1; else if(expn1=expn2) return 0; else return 1;/*兩個一元多項式相加*/linklist addPolyn(linklist ha,linklist hb,lin

8、klist hc) linklist la,lb,lc,r; float sum; la=ha->next; lb=hb->next; lc=hc; while(la && lb) switch (cmpexpn(la->expn,lb->expn) case -1: r=(lnode*)malloc(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc->next=r; lc=r; r->next=null; lb=lb->next; break; case 0

9、: sum=la->num+lb->num; if(sum!=0) r=(lnode*)malloc(sizeof(lnode); r->num=sum; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; lb=lb->next; else la=la->next; lb=lb->next; break; case 1: r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la

10、->expn; lc->next=r; lc=r; r->next=null; la=la->next; break; if(la) r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; if(lb) r=(lnode*)malloc(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc-&

11、gt;next=r; lc=r; r->next=null; lb=lb->next; return lc;/*逆置鏈表*/void changlink(linklist L) linklist p,q,r; p=L->next; q=p->next;while(q) r=q->next;q->next=p; p=q; q=r; L->next->next=NULL; L->next=p; free(p); free(q); free(r);3.主函數(shù)和其他函數(shù)的偽碼算法void main() int len1,len2; int i,n,

12、a2100,b2100; float m,a1100,b1100; linklist A,B,C;A=initlink(); B=initlink(); C=initlink(); printf("Please input Polymial A's length:n"); scanf("%d",&len1); printf("Please input Polymial A's num and expn:n"); for(i=0;i<len1;i+) scanf("%f",&m)

13、; scanf("%d",&n); a1i=m; a2i=n; printf("Please input Polymial B's length:n"); scanf("%d",&len2); printf("Please input Polymial B's num and expn:n"); for(i=0;i<len2;i+) scanf("%f",&m); scanf("%d",&n); b1i=m; b2i=n;

14、 creatlink(A,a1,a2,len1); creatlink(B,b1,b2,len2); printf("The Polymial A is;n"); display(A); printf("The Polymial B is;n"); display(B); addPolyn(A,B,C); changlink(C); printf("The Polymial's result is;n"); display(C);4 函數(shù)調(diào)用關(guān)系maininitlink changlink addPolyn initlink

15、display creatlink cmpexpn length 四、調(diào)試分析在剛開始的時候，我先創(chuàng)建鏈表，在運行時程序報“錯誤 mimi.c 17: 未定義的符號'null'在 initlink 函數(shù)中”和“警告 mimi.c 17: 不可移動的指針（地址常數(shù)）賦值在 initlink 函數(shù)中”，在我查閱C語言的課本說NULL實際是由stdio.h頭文件中的一條宏定義命令定義的。但是在我的程序中卻報錯，最后我記得C語言是識別大小寫的，如果將null改為NULL程序就不會報錯的。 其實該實驗的重心是實現(xiàn)兩個一元多項式的相加，在我首次編好程序后，運行發(fā)現(xiàn)結(jié)果中的相加結(jié)果只進行了一

16、次的相加，后面的幾個項是原La的項，最后我只能再重新編寫該函數(shù)。4. 在函數(shù)addPolyn中我發(fā)現(xiàn)好多語句是相似的，想用一個函數(shù)來實現(xiàn)這樣的功能，可惜沒有想到好的函數(shù)。4. 算法的時空分析各操作的算法時間復(fù)雜度比較合理Initlist，cmpexpn為O(1)printList, length,creatlink，changlink為O(n), addPolyn為0（n1+n2）注：n為鏈表的長度，n1為一元多項式A的長度，n2為一元多項式B的長度。5.本次實驗采用數(shù)據(jù)抽象的程序設(shè)計方法，將程序化為三層次結(jié)構(gòu)，設(shè)計時思路清晰，使調(diào)試也較順利，各模塊有較好的可重用性。五、用戶手冊 本程序的運行

17、環(huán)境為windows xp操作系統(tǒng)，并且在TC2.0中運行，執(zhí)行文件為Exp2Prb2.c； 進入演示程序后，完成編譯，再點擊超級工具集里的中文DOS環(huán)境運行選項，進入DOS環(huán)境中，用戶根據(jù)需求鍵入相應(yīng)的數(shù)據(jù)，可以看到相應(yīng)的結(jié)果。六、測試結(jié)果 因為在wintc中的運行結(jié)果不好截屏，所以在TC2.0中運行得到的結(jié)果如下圖所示：我輸入的一元多項式是Y1=1+3X2 Y2=1+4X+3X2+4X3運行的結(jié)果是 Y=4X3+6X2+4X+2七、附錄：源程序#include<stdio.h>#include<stdlib.h>#define null 0/*一元多項式的鏈?zhǔn)蕉x*

18、/typedef struct lnode float num; int expn; struct lnode *next;*linklist,lnode;/*創(chuàng)建一個空鏈表*/linklist initlink() linklist p; p=(lnode*)malloc(sizeof(lnode); p->next=null; return p;/*創(chuàng)建一個非空鏈表*/linklist creatlink(linklist p,float a,int b,int n) linklist r,s; int i; r=p; for(i=0;i<n;i+) s=(lnode*)mal

19、loc(sizeof(lnode); s->num=ai; s->expn=bi; r->next=s; r=s; r->next=null; return p;/*求鏈表的長度*/int length(linklist p) int n=0; linklist q=p->next; while(q!=null) n+; q=q->next return n;/*顯示鏈表*/void display(linklist p) int n=length(p),i; linklist q=p->next; if(n=0) printf("The P

20、olymial is nulln"); else if(n=1) printf("%3.1f%3d",q->num,q->expn); else for(i=1;i<n;i+) printf("%3.1f%3d->",q->num,q->expn); q=q->next; printf("%3.1f%3d",q->num,q->expn); printf("n");/*比較指數(shù)*/int cmpexpn(int expn1,int expn2) if(

21、expn1>expn2) return -1; else if(expn1=expn2) return 0; else return 1;/*兩個一元多項式相加*/linklist addPolyn(linklist ha,linklist hb,linklist hc) linklist la,lb,lc,r; float sum; la=ha->next; lb=hb->next; lc=hc; while(la && lb) switch (cmpexpn(la->expn,lb->expn) case -1: r=(lnode*)mallo

22、c(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc->next=r; lc=r; r->next=null; lb=lb->next; break; case 0: sum=la->num+lb->num; if(sum!=0) r=(lnode*)malloc(sizeof(lnode); r->num=sum; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; lb=lb

23、->next; else la=la->next; lb=lb->next; break; case 1: r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la->expn; lc->next=r; lc=r; r->next=null; la=la->next; break; if(la) r=(lnode*)malloc(sizeof(lnode); r->num=la->num; r->expn=la->expn; lc->next=r

24、; lc=r; r->next=null; la=la->next; if(lb) r=(lnode*)malloc(sizeof(lnode); r->num=lb->num; r->expn=lb->expn; lc->next=r; lc=r; r->next=null; lb=lb->next; return lc;/*逆置鏈表*/void changlink(linklist L) linklist p,q,r; p=L->next; q=p->next;while(q) r=q->next; q->next=p; p=q; q=r; L->next->next=NULL; L->next=p; free(p); free(q); free(r);/*主函數(shù)*/void main() int len1,len2; int i,n,a2100,b2100; float m,a1100,b1100; lin