數據結構課程設計--一元多項式計算問題(C語言)

1、長 沙 學 院課程設計說明書題目一元多項式計算問題系(部)計算機科學與技術系專業(yè)(班級)12軟件4班姓名謝仲蛟學號2012022411指導教師邱建雄起止日期2013.12.92013.12.20課程設計任務書課程名稱：數據結構與算法設計題目：一元多項式計算問題已知技術參數和設計要求：問題描述：設計一個稀疏多項式簡單計算器基本要求：(1)輸入并分別建立多項式a和b(2)輸入輸出多項式，輸出形式為整數序列：n,c1,e1,c2,e2，其中n是多項式的項數，ci和ei是第i項的系數和指數，序列按指數降序排列(3)完成兩個多項式的相加、相減，并將結果輸出；測試數據：(1) a+b a= 3x14-8x

2、8+6x2+2 b=2x10+4x8+-6x2 (2) a-b a=11x14+3x10+2x8+10x6+5 b=2x14+3x8+5x6+7(3) a+b a=x3+x1 b=-x3-x1(4) a+b a=0 b=x7+x5+x3+x1(5) a-b a=100x100+50x50+20x20+x b=10x100+10x50+10x20+x選作內容：（1）.多項式在x=1時的運算結果（2）求多項式a和b的乘積設計工作量：40課時工作計劃：班級時間節(jié)次地點內容指導老師12軟件4班15周周一5-6節(jié)致遠樓1403布置任務邱建雄15周周一9-10節(jié)致遠樓1403上機調試15周周二5-8節(jié)致遠

3、樓1403上機調試15周周三5-8節(jié)致遠樓1403上機調試15周周四1-4節(jié)涵虛樓c3302答疑15周周四7-8節(jié)致遠樓1403上機調試15周周五1-4節(jié)涵虛樓a1103答疑16周周一5-6節(jié)致遠樓1402上機調試16周周二5-8節(jié)致遠樓1403上機調試16周周三1-4節(jié)致遠樓1403上機調試16周周三5-8節(jié)致遠樓1403上機調試16周周五5-8節(jié)致遠樓1403答辯指導教師簽名：日期： 教研室主任簽名： 日期：系主任簽名： 日期：長沙學院課程設計鑒定表姓名謝仲蛟學號2012022411專業(yè)軟件工程班級軟件4班設計題目一元多項式計算問題指導教師邱建雄指導教師意見：評定等級： 教師簽名： 日期：

4、 答辯小組意見：評定等級：答辯小組長簽名：日期：教研室意見：教研室主任簽名： 日期： 系（部）意見：系主任簽名：日期：說明課程設計成績分“優(yōu)秀”、“良好”、“及格”、“不及格”四類；摘要本次課程設計是在數據結構基礎上設計以c語言來實現的，它的目的是幫助同學更深入的了解數據結構這門課程并熟練運用c語言，使同學達到熟練掌握的程度。課程設計一個稀疏多項式簡單計算器。其基本要求有六：其一，輸入建立兩個多項式；其二,輸出多項式，輸出形式為整數序列：n，c1,e1,c2,e2,其中n是多項式的項數，ci和ei是第i項的系數和指數，序列按指數的降序序列排列；其三，多項式排序，多項式按指數的降序序列排列；其四

5、，多項式相加，指數相同系數相加，指數不同則把此項加進去；其五，多項式相減，指數相同系數相加，指數不同則把此項取反再加進去；其六，返回多項式的項數。選做內容有二：其一，計算多項式的值；其二，多項式相乘。關鍵詞： 一元多項式，相加，相減，排序，相乘，計算，目錄1 設計內容與要求72 詳細設計83 測試16參考文獻18附錄：程序源代碼191 設計內容與要求1、設計內容：設計一個稀疏多項式簡單計算器2、基本要求：(1)輸入并分別建立多項式a和b(2)輸入輸出多項式，輸出形式為整數序列：n,c1,e1,c2,e2，其中n是多項式的項數，ci和 ei是第i項的系數和指數，序列按指數降序排列(3)完成兩個多

6、項式的相加、相減，并將結果輸出； 3、提升要求：（1）.多項式在x=1時的運算結果（2）求多項式a和b的乘積2 詳細設計1、主要設計思路本次設計的一元多項式計算問題以線性表的鏈式存儲結構來存儲多項式每一項的參數，采用二級存儲結構，定義了兩個結構體，一個用來存放每一項的信息如系數和指數，另一個用來存放指向鏈表的頭結點的指針和多項式的項數。2、主要模塊和流程開始操作界面創(chuàng)建多項式相加 1 5 排序相減 選擇操作 2 6返回項數計算 3 7 輸出多項式相乘 4 8 9 退出 結束3、數據結構pya *nexteiai*nexteiaiaiei*next*poln4、界面設計我的界面設計比較簡單。有一

7、個循環(huán)體構成，其中有八個選項，分別為：0.退出1.創(chuàng)建多項式2.排序3.相加4.相減5.計算6.相乘7.項數。用戶可以任意選擇其中的選項進行操作。其實現代碼為：#include#include#includepolynomial.hvoid main()printf(n*xiezhongjiao!*n);struct polynomial *pya,*pyb; pya = new polynomial; pyb = new polynomial;openface(); int a=1;int x0=1,x1=1;while(a)printf(選擇：);scanf(%d,&a);switch(a

8、)case 0: break;case 1: printf(pya:n); scan_polynomial(pya);/*創(chuàng)建*/printf(pyb:n); scan_polynomial(pyb);/*創(chuàng)建*/printf(pya = ); print_polynomial(pya);/*輸出*/ printf(pyb = ); print_polynomial(pyb);/*輸出*/ break;case 2: sort_polynomial(pya);/*排序*/ printf(pya = ); print_polynomial(pya);/*輸出*/sort_polynomial(p

9、yb); printf(pyb = ); print_polynomial(pyb);/*輸出*/ break;case 3: addition_polynomial(pya,pyb);/*相加*/ printf(pya+pyb = ); print_polynomial(pya);/*輸出*/ break;case 4: mimus_polynomial(pya,pyb);/*相減*/ printf(pya-pyb = ); print_polynomial(pya);/*輸出*/ break;case 5: printf(輸入x的值:);scanf(%d,&x0); count_polyn

10、omial(pya,x0);/*計算*/printf(輸入x的值:);scanf(%d,&x1); count_polynomial(pyb,x1);/*計算*/ break;case 6: product_polynomial(pya,pyb);/*相乘*/ printf(pya*pyb = ); print_polynomial(pya);/*輸出*/ break;case 7: printf(pya項數:); n_polynomial(pya);/*返回項數*/printf(pyb項數:); n_polynomial(pyb);/*返回項數*/ break;default: printf

11、(請正確輸入.); break;/*end of switch*/ /*end of while*/printf(n感謝xzj,感謝home,感謝xx,感謝cl,感謝501,感謝yyxsz,感謝ccsu!n); void openface()printf(n*n);printf(1:創(chuàng)建多項式n);printf(2:排序n);printf(3:相加n);printf(4:相減n);printf(5:計算n);printf(6:相乘n);printf(7:項數n);printf(0:退出n);printf(*n);5、功能設計1、輸入多項式此功能為創(chuàng)建一個線性鏈式鏈表，并將多項式每一項的信息輸入

12、到鏈表中存儲起來。其實現代碼為：struct polynomial *scan_polynomial(struct polynomial *py) /* 輸入多項式 */struct element *q,*p;q = (struct element *)malloc(sizeof(struct element); py-pol = q; py-n = 1;printf(輸入第1項的系數和指數(兩數逗號相隔)：);scanf(%d,%d,&q-ai,&q-ei); q-next = null;if(q-ai != 0)for(int k=0;kn;k+) p = (struct element

13、 *)malloc(sizeof(struct element);printf(輸入第%d項的系數和指數(兩數逗號相隔)：,k+2); scanf(%d,%d,&p-ai,&p-ei); if(p-ai = 0) break;p-next = null;q-next = p; q = q-next ;py-n = py-n + 1;/*end of for*/*end of if*/return py;2、 輸出多項式 此項功能為輸出創(chuàng)建的多項式。其實現代碼為：void print_polynomial(struct polynomial *py) /* 輸出多項式,項數為n項 */struc

14、t element *r;r = py-pol; for(int k=0;kn;k+) if(r-ei = 0)/*當指數為0時只輸出系數*/if(r-ai ai);if(r-ai 0)if(k = 0) printf(%d,r-ai);/*當此項為第一項時前面不輸出+*/if(k != 0) printf(+%d,r-ai);/*當此項不為第一項時前面輸出+*/ /*end of if*/if(r-ei = 1)/*當系數為1時只輸出系數和x*/if(r-ai ai = -1)printf(-x);/*系數為-1時取反輸出x*/if(r-ai != -1)printf(%dx,r-ai);/

15、*系數不為-1時輸出系數*/*end of if*/if(r-ai 0)/*系數大于0時輸出各項的參數*/if(r-ai = 1)/*系數為1時輸出不輸出系數*/if(k = 0) printf(x);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+x);/*當此項不為第一項時前面輸出+*/if(r-ai != 1)/*系數不為1時輸出輸出系數*/if(k = 0) printf(%dx,r-ai);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+%dx,r-ai);/*當此項不為第一項時前面輸出+*/ /*end of if*/ /*e

16、nd of if*/if(r-ei != 0 & r-ei != 1)/*當指數既不為0也不為1時輸出系數指數和*/if(r-ai ai = -1)printf(-x%d,r-ei);/*系數為-1時取反輸出x和指數*/if(r-ai != -1)printf(%dx%d,r-ai,r-ei);/*系數不為-1時輸出所有參數*/*end of if*/if(r-ai 0)/*系數大于0時輸出各項的參數*/if(r-ai = 1)/*系數為1時輸出不輸出系數*/if(k = 0) printf(x%d,r-ei);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+x%d

17、,r-ei);/*當此項不為第一項時前面輸出+*/if(r-ai != 1)/*系數不為1時輸出輸出系數*/if(k = 0) printf(%dx%d,r-ai,r-ei);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+%dx%d,r-ai,r-ei);/*當此項不為第一項時前面輸出+*/ /*end of if*/*end of if*/r = r-next ; /*指向下一項*/*end of for*/ printf(n); 3、排序多項式 此功能是將已經建立好的多項式按照其指數的降序序列排序，并按照內存的地址序列存儲起來。 其實現代碼為：struct p

18、olynomial *sort_polynomial(struct polynomial *py)/* 排序按指數降序排列 */struct element *sr1,*sr0;int ai,ei;for(int k0=0;k0n-1;k0+)sr0 = sr1 = py-pol;for(int k0=0;k0n-1;k0+)for(int k1=0;k1n-1-k0;k1+)if(sr0-ei next-ei)/*如果當前項小則將兩個結構中的值互換*/ai = sr0-ai ;ei = sr0-ei ;sr0-ai = sr1-next-ai ;sr0-ei = sr1-next-ei ;s

19、r1-next-ai = ai;sr1-next-ei = ei;/*end of if*/sr1 = sr1-next ;/*end of for3*/sr0 = sr0-next ;sr1 = sr0;/*end of for2*/*end of for1*/return py; 4、多項式相加 此項功能為將兩個多項式a、b進行相加，首先對多項式中的每一項進行比較，當指數相同時，將當前項的系數相加，當指數不同時，則將b中的此項插入a當中，直到每一項都比較完為止，最后得到一條新的線性鏈表a。其實現代碼為：struct polynomial *addition_polynomial(struc

20、t polynomial *pya,struct polynomial *pyb) /* 兩個多項式相加 */struct element *wa,*va,*wb,*vb;wb = vb = pyb-pol ;int a,b=pyb-n;for(int j0=0;j0pol ;a=0;for(int j1=0;j1n;j1+)if(wa-ei = wb-ei)/*如果所比較的兩個多項式中的指數相同則將兩系數相加*/ wa-ai=wa-ai+wb-ai; wb=wb-next; vb=wb; break;/*end of if*/if(wa-ei != wb-ei)/*如果所比較的兩個多項式中的

21、指數不同則將pyb中的此項插入到pya中*/ va = wa;wa=wa-next; a=a+1;if(a = pya-n) wb = wb-next;va-next = vb; vb-next = null;vb = wb;pya-n+;break;/*end of if*/*end of if1*/*end of for2*/*end of for1*/return pya;5、多形式相減此項功能為將兩個多項式a、b進行相減，此項功能與多項式相加算法相近，即首先對多項式中的每一項進行比較，當指數相同時，將當前項的項數相減，當指數不同時，則將b中此項插入到a當中，直到每一項都比較完為止，最后

22、得到一條新的線性鏈表a.其實現代碼為：struct polynomial *mimus_polynomial(struct polynomial *pya,struct polynomial *pyb) /* 兩個多項式相減 */struct element *wa,*va,*wb,*vb;wb = vb = pyb-pol ;int a,b=pyb-n;for(int j0=0;j0pol ;a=0;for(int j1=0;j1n;j1+)if(wa-ei = wb-ei)/*如果所比較的兩個多項式中的指數相同則將兩系數相減*/ wa-ai=wa-ai-wb-ai; wb=wb-next;

23、 vb=wb; break;/*end of if*/if(wa-ei != wb-ei)/*如果所比較的兩個多項式中的指數不同則將pyb中的此項插入到pya中*/ va = wa;wa=wa-next; a=a+1;if(a = pya-n) wb = wb-next;va-next = vb; vb-ai = -vb-ai ;vb-next = null;vb = wb;pya-n+;break;/*end of if*/*end of if1*/*end of for2*/*end of for1*/return pya; 6、返回項數 此項功能為得到一個多項式項數的值。其實現代碼為：v

24、oid n_polynomial(struct polynomial *py) /* 返回多項式的項數 */printf(%dn,py-n);7、計算多項式的值此項功能為計算多項式的值，輸入x的值，首先將第一項的值計算出來，并將下一項的值計算出，然后兩值相加，接著再計算第三項數的值，再將前兩項之和加上第三項的值，依次下去，計算出多項式每一項的值，得到多項式的值并輸出。其實現代碼為：void count_polynomial(struct polynomial *py,int x0) /* 計算多項式x=x1的結果 */struct element *z;z = py-pol;int x1,co

25、unt=0;for(int k0=0;k0n;k0+)x1 = 1;for(int k1=0;k1ei;k1+)/*計算每一項變量的值*/x1 = x1 * x0;count =count + x1 * z-ai;/*累加*/z = z-next ;printf(當x0 = %d 時,多項式的值為:%dn,x0,count);8、 多項式相乘此項功能為將兩個多項式a、b進行相乘，將多項式a中的每一項分別乘以b中的每一項并將得到的每項的信息用線性鏈表進行存儲；最終得到一條新的線性鏈表。其實現代碼為：struct polynomial *product_polynomial(struct poly

26、nomial *pya,struct polynomial *pyb) /* 兩個多項式相乘 */struct element *a0,*a1,*a2,*a3,*b0,*c0;a0 = a1 = a2 = a3 = pya-pol ;for(int k0=0;k0n;k0+)a0 = a2;a2 = a2-next ;b0 = pyb-pol ; for(int k1=0;k1n;k1+)/*先將pya中第一項乘以pyb中的每一項并把頭結點賦給pya，再將pya中的第二項乘以pyb中的每一項并把頭結點賦給新的pya的最后一項，依次下去直到沒一項都乘完為止*/ if(k1 = 0) a1-ai

27、= a0-ai * b0-ai ; a1-ei = a0-ei + b0-ei ;a1-next = null;/*emd of if*/ if(k1 != 0) c0 = (struct element *)malloc(sizeof(struct element);c0-ai = a0-ai * b0-ai ;c0-ei = a0-ei + b0-ei ; c0-next = null;a1-next = c0;a1 = a1-next ;/*end of if*/b0 = b0-next ; /*end of for2*/a1-next = a2;a1 = a2; /*end of fo

28、r1*/pya-n = pya-n * pyb-n;return pya;3 測試1、 創(chuàng)建多項式測試首先選擇1創(chuàng)建多項式選項，接著輸入多項式a和b的指數和系數，其中指數和系數用逗號相隔，最后輸出多項式a、b。2、 排序 選擇操作2排序選項，對多項式a、b進行了降序排列。3、 相加 選擇操作3多項式相加，對多項式a、b進行了相加。4、 相減 先選擇操作0退出后再重新進入，接著選擇創(chuàng)建多項式，后再選擇操作4對多項式進行相減比輸出。5、 計算 先選擇操作5，接著數如x的值，得到多項式a、b的值。6、 返回項數值 選擇操作7，返回了多項式a、b的項數。7、 相乘 選擇操作6對多項式a、b進行了相乘畢

29、輸出。參考文獻1 嚴蔚敏，吳偉民數據結構（c語言版）.北京：清華大學出版社，1997年.2 c程序設計/譚浩強.-3版.-北京：清華大學出版社，2005（2007重印）附錄：程序源代碼1、頭文件#includestruct element int ai; /*系數*/int ei; /*指數*/ struct element *next; ;struct polynomial struct element *pol; int n; /*項數*/;/* 輸入多項式 */struct polynomial *scan_polynomial(struct polynomial *py);/* 銷毀一

30、個多項式 */void destroy_polynomial(struct polynomial *py); /* 輸出多項式 */void print_polynomial(struct polynomial *py); /* 兩個多項式相加 */struct polynomial *addition_polynomial(struct polynomial *pya,struct polynomial *pyb);/* 兩個多項式相減 */struct polynomial *mimus_polynomial(struct polynomial *pya,struct polynomial

31、 *pyb); /* 排序按指數降序排列 */struct polynomial *sort_polynomial(struct polynomial *py);/* 多項式的項數 */void n_polynomial(struct polynomial *py);/* 計算多項式x=x1的結果 */void count_polynomial(struct polynomial *py,int x0); /* 兩個多項式相乘 */struct polynomial *product_polynomial(struct polynomial *pya,struct polynomial *py

32、b); void openface();2、主函數文件#include#include#includepolynomial.hvoid main()printf(n*xiezhongjiao!*n);struct polynomial *pya,*pyb; pya = new polynomial; pyb = new polynomial; openface(); int a=1;int x0=1,x1=1;while(a)printf(選擇：);scanf(%d,&a);switch(a)case 0: break;case 1: printf(pya:n); scan_polynomia

33、l(pya);/*創(chuàng)建*/printf(pyb:n); scan_polynomial(pyb);/*創(chuàng)建*/printf(pya = ); print_polynomial(pya);/*輸出*/ printf(pyb = ); print_polynomial(pyb);/*輸出*/ break;case 2: sort_polynomial(pya);/*排序*/ printf(pya = ); print_polynomial(pya);/*輸出*/sort_polynomial(pyb); printf(pyb = ); print_polynomial(pyb);/*輸出*/ br

34、eak;case 3: addition_polynomial(pya,pyb);/*相加*/ printf(pya+pyb = ); print_polynomial(pya);/*輸出*/ break;case 4: mimus_polynomial(pya,pyb);/*相減*/ printf(pya-pyb = ); print_polynomial(pya);/*輸出*/ break;case 5: printf(輸入x的值:);scanf(%d,&x0); count_polynomial(pya,x0);/*計算*/printf(輸入x的值:);scanf(%d,&x1); co

35、unt_polynomial(pyb,x1);/*計算*/ break;case 6: product_polynomial(pya,pyb);/*相乘*/ printf(pya*pyb = ); print_polynomial(pya);/*輸出*/ break;case 7: printf(pya項數:); n_polynomial(pya);/*返回項數*/printf(pyb項數:); n_polynomial(pyb);/*返回項數*/ break;default: printf(請正確輸入.); break;/*end of switch*/ /*end of while*/pr

36、intf(n感謝xzj,感謝home,感謝xx,感謝cl,感謝501,感謝yyxsz,感謝ccsu!n); void openface()printf(n*n);printf(1:創(chuàng)建多項式n);printf(2:排序n);printf(3:相加n);printf(4:相減n);printf(5:計算n);printf(6:相乘n);printf(7:項數n);printf(0:退出n);printf(*n);3、功能函數文件#include#include#include#includepolynomial.hstruct polynomial *scan_polynomial(struct

37、 polynomial *py) /* 輸入多項式 */struct element *q,*p;q = (struct element *)malloc(sizeof(struct element); py-pol = q; py-n = 1;printf(輸入第1項的系數和指數(兩數逗號相隔)：);scanf(%d,%d,&q-ai,&q-ei); q-next = null;if(q-ai != 0)for(int k=0;kn;k+) p = (struct element *)malloc(sizeof(struct element);printf(輸入第%d項的系數和指數(兩數逗號

38、相隔)：,k+2); scanf(%d,%d,&p-ai,&p-ei); if(p-ai = 0) break;p-next = null;q-next = p; q = q-next ;py-n = py-n + 1;/*end of for*/*end of if*/return py;void print_polynomial(struct polynomial *py) /* 輸出多項式,項數為n項 */struct element *r;r = py-pol; for(int k=0;kn;k+) if(r-ei = 0)/*當指數為0時只輸出系數*/if(r-ai ai);if(r

39、-ai 0)if(k = 0) printf(%d,r-ai);/*當此項為第一項時前面不輸出+*/if(k != 0) printf(+%d,r-ai);/*當此項不為第一項時前面輸出+*/ /*end of if*/if(r-ei = 1)/*當系數為1時只輸出系數和x*/if(r-ai ai = -1)printf(-x);/*系數為-1時取反輸出x*/if(r-ai != -1)printf(%dx,r-ai);/*系數不為-1時輸出系數*/*end of if*/if(r-ai 0)/*系數大于0時輸出各項的參數*/if(r-ai = 1)/*系數為1時輸出不輸出系數*/if(k =

40、 0) printf(x);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+x);/*當此項不為第一項時前面輸出+*/if(r-ai != 1)/*系數不為1時輸出輸出系數*/if(k = 0) printf(%dx,r-ai);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+%dx,r-ai);/*當此項不為第一項時前面輸出+*/ /*end of if*/ /*end of if*/if(r-ei != 0 & r-ei != 1)/*當指數既不為0也不為1時輸出系數指數和*/if(r-ai ai = -1)printf(-x%d,r

41、-ei);/*系數為-1時取反輸出x和指數*/if(r-ai != -1)printf(%dx%d,r-ai,r-ei);/*系數不為-1時輸出所有參數*/*end of if*/if(r-ai 0)/*系數大于0時輸出各項的參數*/if(r-ai = 1)/*系數為1時輸出不輸出系數*/if(k = 0) printf(x%d,r-ei);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+x%d,r-ei);/*當此項不為第一項時前面輸出+*/if(r-ai != 1)/*系數不為1時輸出輸出系數*/if(k = 0) printf(%dx%d,r-ai,r-ei);/*當此項為第一項時前面不輸出+*/ if(k != 0) printf(+%dx%d,r-ai,r-ei);/*當此項不為第一項時前面輸出+*/ /*end of if*/*end of if*/r = r-next ; /*指向下一項*/*end of for*/ printf(n);struct polynomial *addition_polynomial(struct polynomial *pya,struct polynomial