順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)

1、課 程 設(shè) 計（數(shù)據(jù)結(jié)構(gòu)）班 級姓 名學(xué) 號 指導(dǎo)教師二一年七月十日課程設(shè)計任務(wù)書及成績評定課題名稱順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)。 、題目的目的和要求 1、設(shè)計目的鞏固和加深對數(shù)據(jù)結(jié)構(gòu)的理解，通過上機實驗、調(diào)試程序，加深對課本知識的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識寫程序。（1）通過本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。（2）能針對給定題目，選擇相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計算法，進而給出問題的正確求解過程并編寫代碼實現(xiàn)。2、設(shè)計題目要求（給出你所選擇的題目的要求描述）1) 首先判定多項式是否稀疏2) 分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)；3) 結(jié)果

2、m(x)中無重復(fù)階項和無零系數(shù)項；4) 要求輸出結(jié)果的升冪和降冪兩種排列情況；、設(shè)計進度及完成情況日 期內(nèi) 容2010.6.28-6.30選取參考書，查閱有關(guān)文獻資料，完成資料搜集和系統(tǒng)分析工作。2010.7.17.3創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu),錄入源程序。2010.7.57.7調(diào)試程序并記錄調(diào)試中的問題，初步完成課程設(shè)計報告。2009.7.87.9上交課程設(shè)計報告打印版并進行課程設(shè)計答辯，要求每個同學(xué)針對自己的設(shè)計回答指導(dǎo)教師3-4個問題。考核結(jié)束后將課程設(shè)計報告和源程序的電子版交班長統(tǒng)一刻光盤上交。、主要參考文獻及資料1 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)（c語言版）清華大學(xué)出版社，20072 嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)題集（c語

3、言版）清華大學(xué)出版社，20073 譚浩強c語言程序設(shè)計清華大學(xué)出版社，20054 與所用編程環(huán)境相配套的c語言或c+相關(guān)的資料、成績評定設(shè)計成績： （教師填寫）指導(dǎo)老師： （簽字）二一年 七 月 十 日目 錄第一章 概述1第二章 系統(tǒng)分析2第三章 概要設(shè)計3第四章 詳細(xì)設(shè)計4第五章 運行與測試5第六章 總結(jié)與心得6參考文獻7本目錄是根據(jù)正文文檔自動生成的，請在報告完成后，更新目錄的頁碼，更新方法如下：1.鼠標(biāo)單擊目錄任意部分選中目錄；2.單擊鼠標(biāo)右鍵選擇“更新域”；3.在出現(xiàn)的“更新目錄”的對話框中選擇“只更新頁碼”， 見圖1-3，單擊“確定”按鈕，目錄頁碼將被更新。更新完成后，最好再核對一下

4、。圖1-3 更新目錄頁碼示意圖第一章 概述課程設(shè)計是實踐性教學(xué)中的一個重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個方面，是一門獨立于課程之外的特殊課程。課程設(shè)計是讓同學(xué)們對所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計算機理論和應(yīng)用的核心基礎(chǔ)課程。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面，加深對課程基本內(nèi)容的理解。同時，在程序設(shè)計方法以及上機操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。在這次的課程設(shè)計中我選擇的題目是順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、

5、乘法的實現(xiàn)。分別采用順序結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，利用多項得結(jié)果，最后得多項式中不含有重復(fù)階項和零系數(shù)得項。除此之外，還得分為降冪和升冪兩種排序方式。第二章 系統(tǒng)分析1 順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)?？梢苑譃閹讉€模塊：輸入模塊、輸出模塊（升冪降冪）、數(shù)據(jù)處理模塊（多項式的加減乘）、主程序模塊。2 在程序過程中加入漢字提示符，讓讀者清楚明白的操作該程序。運行程序時看起來簡潔有序，操作簡單明了。3 程序執(zhí)行時的命令：選擇創(chuàng)建兩個一元多項式輸入第一個一元多項式的項數(shù)依次輸入一元多項式的系數(shù)和指數(shù)以相同方式輸入第二個一元多項式選擇操作方式選擇降冪或升冪排序輸出結(jié)果是否退出4.

6、測試數(shù)據(jù)。輸入的一元多項式系數(shù)指數(shù)分別為7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法結(jié)果為；升冪 降冪減法結(jié)果為：升冪 降冪乘法結(jié)果為：升冪 降冪 第三章 概要設(shè)計1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計 在該程序中分別分為順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)。2、算法的設(shè)計本程序主要分為四大模塊主程序模塊輸入模塊：通過getpolyn函數(shù)輸入輸出模塊（升冪降冪）：printpolyn函數(shù)實現(xiàn)輸出數(shù)據(jù)處理模塊（多項式的加減乘）：通過一元多項式的polynomial基本操作實現(xiàn)3、抽象數(shù)據(jù)類型的設(shè)計一元多項式抽象數(shù)據(jù)類型的定義：抽象數(shù)據(jù)類型polynomial的定義：第四章 詳細(xì)設(shè)計#include#incl

7、udetypedef struct float coef; /系數(shù) int expn; /指數(shù)term;typedef struct lnode term data; /term多項式值 struct lnode *next;lnode,*linklist;typedef linklist polynomail;/*比較指數(shù)*/int cmp(term a,term b) if(a.expnb.expn) return 1; if(a.expn=b.expn) return 0; if(a.expnnext!=null;p=p-next); r=p; for(h=pa;h-next!=r;)/

8、大的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-data,p-next-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向參與比較的最后一個，不斷向前移動 /*由大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=null) exit(-2); for(p=pa;p-next!=null;p=p-next); r=p; for(h=pa;h-next

9、!=r;)/小的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-next-data,p-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向參與比較的最后一個，不斷向前移動 /*打印多項式,求項數(shù)*/int printpolyn(polynomail p) int i; polynomail q; if(p=null) printf(無項！n); else if(p-next=null) printf(y=0n); else pri

10、ntf(該多項式為y=);q=p-next;i=1; if(q-data.coef!=0&q-data.expn!=0) printf(%.2fx%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) printf(%.2f,q-data.coef);/打印第一項 q=q-next; if(q=null) printf(n);return 1; while(1)/while中，打印剩下項中系數(shù)非零的項， if(q-data.coef!=0&q-data.expn!=0) if(q-data.coef0) printf(

11、+); printf(%.2fx%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) if(q-data.coef0) printf(+); printf(%f,q-data.coef); q=q-next; if(q=null) printf(n); break; return 1;/*1、創(chuàng)建并初始化多項式鏈表*/polynomail creatpolyn(polynomail p,int m) polynomail r,q,p,s,q; int i; p=(lnode*)malloc(sizeof(lnode)

12、; r=p; for(i=0;idata.coef,&s-data.expn); r-next=s; r=s; r-next=null; if(p-next-next!=null) for(q=p-next;q!=null/*&q-next!=null*/;q=q-next)/合并同類項 for(p=q-next,r=q;p!=null;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; q=p;p=p-next; free(q); else r=r-next; p=p-next;

13、return p;/*2、兩多項式相加*/polynomail addpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r;int j; p=pa-next;q=pb-next; newp=(lnode*)malloc(sizeof(lnode); r=newp; while(p&q) s=(lnode*)malloc(sizeof(lnode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=

14、s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef+q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(lnode*)malloc(sizeof(lnod

15、e); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(lnode*)malloc(sizeof(lnode); s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=null; for(q=newp-next;q-next!=null;q=q-next)/合并同類項 for(p=q;p!=null&p-next!=null;p=p-next) if(q-dat

16、a.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); printf(升序 1 , 降序 2n); printf(選擇:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*3、兩多項式相減*/polynomail subpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r,q;

17、int j; p=pa-next;q=pb-next; newp=(lnode*)malloc(sizeof(lnode); r=newp; while(p&q) s=(lnode*)malloc(sizeof(lnode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef-q-data.coef; if(s-data.coef!=0.0) s-d

18、ata.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(lnode*)malloc(sizeof(lnode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(ln

19、ode*)malloc(sizeof(lnode); s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=null; if(newp-next!=null&newp-next-next!=null)/合并同類項 for(q=newp-next;q!=null;q=q-next) for(p=q-next,r=q;p!=null;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-ne

20、xt; q=p;p=p-next; free(q); else r=r-next; p=p-next; printf(升序 1 , 降序 2n); printf(選擇:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*4兩多項式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r; int i=20,j; newp=(lnode*)malloc(sizeof(lnode); r=newp; fo

21、r(p=pa-next;p!=null;p=p-next) for(q=pb-next;q!=null;q=q-next) s=(lnode*)malloc(sizeof(lnode); s-data.coef=p-data.coef*q-data.coef; s-data.expn=p-data.expn+q-data.expn; r-next=s; r=s; r-next=null; printf(升序 1 , 降序 2n); printf(選擇:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); for(;i!=0;

22、i-) for(q=newp-next;q-next!=null;q=q-next)/合并同類項 for(p=q;p!=null&p-next!=null;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); return newp;/*5、銷毀已建立的兩個多項式*/void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; whil

23、e(p!=null) q=p; p=p-next; free(q); p=pb; while(p!=null) q=p; p=p-next; free(q); printf(兩個多項式已經(jīng)銷毀n);void main() polynomail pa=null,pb=null; polynomail p,q; polynomail addp=null,subp=null,mulp=null; int n,m; int sign=y; printf(1、創(chuàng)建兩個一元多項式n); printf(2、兩多項式相加得一新多項式n); printf(3、兩多項式相減得一新多項式n); printf(4、兩

24、多項式相乘得一新多項式n); printf(5、銷毀已建立的兩個多項式n); printf(6、退出n); printf(n); while(sign!=n) printf(請選擇：); scanf(%d,&n); switch(n) case 1: if(pa!=null) printf(已建立兩個一元多項式，請選擇其他操作！); break; printf(請輸入第一個多項式：n); printf(要輸入幾項：); scanf(%d,&m); while(m=0) printf(m不能為0，請重新輸入m:); scanf(%d,&m); pa=creatpolyn(pa,m); printpolyn(pa); printf(請輸入第二個多項式：n); printf(要輸入幾項：); scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=null) printf(請先創(chuàng)建兩個一元多項式！n); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=null) printf(請先創(chuàng)建兩個一元多項式！n); break; subp=subpolyn(pa,pb); prin