數(shù)據(jù)結(jié)構(gòu) 實(shí)驗(yàn)2 多項(xiàng)式求和

1、1、 實(shí)驗(yàn)?zāi)康模?) 掌握線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)；（2) 掌握線性表插入、刪除等基本運(yùn)算；（3) 掌握線性表的典型運(yùn)用多項(xiàng)式求和。2、 實(shí)驗(yàn)內(nèi)容編程實(shí)現(xiàn)多項(xiàng)式的求和運(yùn)算：（1) 順序存儲結(jié)構(gòu)的實(shí)現(xiàn)例如，已知：f(x)=8x6+5x5-10x4+32x2-x+10，g(x)=7x5+10x4-20x3-10x2+x，求和結(jié)果：f(x)+g(x)=8x6+12x5-20x3+22x2+10。順序表的定義類型如下：#define MAXLEN 100typedef struct int dataMAXLEN;Int last;SeqList;（2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)的實(shí)現(xiàn)例如，已知：f(x)

2、=100x100+5x50-30x10 +10，g(x)=150x90-5x50+40x20-20x10+3x，求和結(jié)果：f(x)+g(x)= 100x100+150x90+40x20-10x10+3x+10。3、 實(shí)驗(yàn)要求（1) 利用C（C+）語言完成程序設(shè)計(jì)。（2) 上機(jī)調(diào)試通過實(shí)驗(yàn)程序。（3) 輸入數(shù)據(jù)，檢驗(yàn)程序運(yùn)行結(jié)果。（4) 給出具體的算法分析，包括時間復(fù)雜度和空間復(fù)雜度等。（5) 撰寫實(shí)驗(yàn)報告（把輸入實(shí)驗(yàn)數(shù)據(jù)及運(yùn)行結(jié)果用抓圖的形式粘貼到實(shí)驗(yàn)報告上）。4、 實(shí)驗(yàn)步驟與源程序 實(shí)驗(yàn)步驟我先從具體的問題中抽象出適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)出相應(yīng)的算法，對于用順序存儲結(jié)構(gòu)實(shí)現(xiàn)多項(xiàng)式求和而言，需

3、要設(shè)計(jì)3個main函數(shù)調(diào)用的子函數(shù)，分別實(shí)現(xiàn)創(chuàng)建多項(xiàng)式，多項(xiàng)式相加和顯示多項(xiàng)式；對于用鏈?zhǔn)酱鎯Y(jié)構(gòu)實(shí)現(xiàn)多項(xiàng)式求和，也同樣需要3個這樣的子函數(shù)，最后，編寫程序，并調(diào)試程序，得出實(shí)驗(yàn)結(jié)果。 源代碼順序存儲結(jié)構(gòu)：#include#define MAXLEN 100typedef struct int dataMAXLEN; int last; SeqList;void add_List(SeqList A, SeqList B, SeqList *C) int i;C-last=A.lastB.last? A.last:B.last;for(i=0;ilast;i+) C-datai=A.datai

4、+B.datai;void show_list(SeqList C) int i; for(i=C.last;i=1;i-) if(C.datai) printf(%dx%d)+,C.datai,i); printf(%dx%d)n,C.data0,0); void create_list(SeqList *D) int n,i; printf(tt請輸入多項(xiàng)式X的最高次數(shù)：);scanf(%d,&n);for(int k=99;k=0;k-) D-datak=0;printf(tt請輸入多項(xiàng)式X的次數(shù)由大到小輸入系數(shù)，缺少項(xiàng)用0補(bǔ)齊n); for(i=n;i=0;i-)printf(tt輸入

5、X%d項(xiàng)的系數(shù): ,i); scanf(%d,&D-datai); D-last=n;void main() SeqList A,B,C; printf(tt創(chuàng)建多項(xiàng)式f(x):n); create_list(&A); printf(ttf(x)=); show_list(A); printf(tt創(chuàng)建多項(xiàng)式g(x):n); create_list(&B); printf(ttg(x)=); show_list(B); printf(tt多項(xiàng)式f(x)和g(x)的和: ); add_List (A,B,&C); printf(nttf(x)+g(x)=); show_list(C);鏈?zhǔn)酱鎯Y(jié)

6、構(gòu)：#include#include#includetypedef struct linknode float coef; int expn; struct linknode *next; Node;void create_link_list(Node *L) Node *p,*q; int n=1; float x=1; q=L; printf(n請按多項(xiàng)式指數(shù)由大到小輸入系數(shù)和指數(shù):n); printf(提示: 系數(shù)和指數(shù)間用空格間隔，每組數(shù)據(jù)之間用回車間隔(系數(shù)和指數(shù)為0時結(jié)束輸入)n); while(fabs(x)0.000001 ) scanf(%f %d,&x,&n); if(fa

7、bs(x)0.00001) p=(Node *) malloc(sizeof(Node); p-coef=x; p-expn=n; p-next=NULL; q-next=p ; q=p; void show_link_list(Node *L) Node *p; p=L-next;while(p&p-next ) printf(%.1fx%d) + ,p-coef,p-expn); p=p-next; printf(%.1fx%d) ,p-coef,p-expn);printf(n);void mergelist(Node *La,Node *Lb,Node *Lc) / 多項(xiàng)式合并 Nod

8、e *pa,*pb,*pc; Node *q1,*q2; Lc=La;pc=Lc; pa=La-next;pb=Lb-next; while(pa & pb) if(pa-expn pb-expn) pc-next=pa;pc=pa;pa=pa-next; else if(pa-expn expn) pc-next=pb;pc=pb;pb=pb-next; else if(fabs(pa-coef+pb-coef)next; pb=pb-next; free(q1); free(q2); else q1=pb;pa-coef=pa-coef+pb-coef; pc-next=pa; pc=pa

9、; pa=pa-next; pb=pb-next; free(q1); if(pa) pc-next=pa; else pc-next=pb;void main() Node *LA,*LB,*LC;LA=(Node *)malloc(sizeof(Node); LA-next=NULL;LB=(Node *)malloc(sizeof(Node); LB-next=NULL; LC=LA; create_link_list( LA); printf(f(x) = );show_link_list(LA);create_link_list( LB);printf(g(x) = );show_l

10、ink_list(LB);mergelist(LA,LB,LC);printf(nf(x)+g(x)= );show_link_list(LC);5、 測試數(shù)據(jù)與實(shí)驗(yàn)結(jié)果（可以抓圖粘貼）順序存儲結(jié)構(gòu)的實(shí)現(xiàn)調(diào)試結(jié)果如圖所示：鏈?zhǔn)酱鎯Y(jié)構(gòu)的實(shí)現(xiàn)調(diào)試結(jié)果如圖所示：6、 結(jié)果分析與實(shí)驗(yàn)體會本次實(shí)驗(yàn)是參考了范例程序，經(jīng)過自己的改寫，從而實(shí)現(xiàn)要求。先做簡單的輸出，一步步的再做其它格式的設(shè)置。而且，在具體操作中我對順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)和缺點(diǎn)有了更深刻的體會，順序存儲結(jié)構(gòu)的算法較為簡單，但是在輸入的過程中有很大的局限性，必須從大到小依次且連續(xù)的輸入多項(xiàng)式次數(shù)，所以，它只適合最高次數(shù)較小的多項(xiàng)式求和，而鏈?zhǔn)酱鎯Y(jié)構(gòu)設(shè)計(jì)的算法則更靈活，