




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、要求完成如下功能:(1) 輸入并建立多項式creatpolyn()(2) 輸出多項式,輸出形式為整數(shù)序列,序列按指數(shù)升序排列printpolyn()(3) 多項式a和b相加,建立多項式a+b,輸出相加的多項式addpolyn()(4) 多項式a和b相減,建立多項式a-b,輸出相減的多項式subpolyn()用帶表頭結(jié)點(diǎn)的單鏈表存儲多項式。課 程 設(shè) 計學(xué)生姓名: 學(xué) 號: 專業(yè)班級: 課程名稱: 數(shù)據(jù)結(jié)構(gòu) 學(xué)年學(xué)期: 指導(dǎo)教師: 目 錄1需求分析說明12概要設(shè)計說明33詳細(xì)設(shè)計說明54調(diào)試分析105用戶使用說明116課程設(shè)計總結(jié)127測試結(jié)果138參考書目169. 附錄1724數(shù) 據(jù) 結(jié) 構(gòu)
2、課 程 設(shè) 計1 需求分析說明1.程序所能達(dá)到的功能是(1) 輸入并建立多項式creatpolyn()(2) 輸出多項式,輸出形式為整數(shù)序列,序列按指數(shù)升序排列printpolyn()(3) 多項式a和b相加,建立多項式a+b,輸出相加的多項式addpolyn()(4) 多項式a和b相減,建立多項式a-b,輸出相減的多項式subpolyn()用帶表頭結(jié)點(diǎn)的單鏈表存儲多項式。2輸入的形式和輸入值的范圍 :本系統(tǒng)要輸入的數(shù)據(jù)主要是有多項式中每項的系數(shù)和指數(shù),可以把它們定義為整形數(shù)據(jù),既可以為整數(shù)也可以為非負(fù)整數(shù),即有符號的整形數(shù)據(jù),由于整形數(shù)據(jù)在內(nèi)存里占用兩個字節(jié),所以它的取值范圍為-327683
3、2767。其次還有就是選擇功能時,要輸入的功能號,它們是字符型數(shù)據(jù),取值范圍是ASS|表中的字符。例如輸入的格式如下: 請輸入a的項數(shù):3請輸入第一項的系數(shù)與指數(shù):2,1請輸入第二項的系數(shù)和指數(shù):5,8請輸入第三項的系數(shù)和指數(shù):-3.1,11請輸入b的項數(shù):3請輸入第一項的系數(shù)和指數(shù):7,0請輸入第一項的系數(shù)和指數(shù):5,8請輸入第三項的系數(shù)和指數(shù):11,9* 多項式操作程序* A:輸出多項式a B:輸出多項式b * C:輸出a+b D:輸出a-b * F:退出程序 *請選擇操作:Ca+b=2x+5x8-3.1x11+7-5x8+11x9請選擇操作:Da-b=2x+5x8-3.1x11-7+5x
4、8-11x93.輸出的形式:本系統(tǒng)要輸出的是把創(chuàng)建好的第一個多項式和第二個多項式按指數(shù)升序排列,并把進(jìn)行運(yùn)算后的結(jié)果也按指數(shù)升序排列輸出,輸出形式如上面所示。4.測試數(shù)據(jù)正確的輸入及輸出結(jié)果:(1)(2x+5x8-3.1x11)+(7-5x8+11x9)(2) (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)(3)(x+x2+x3)+0(4)(x+x3)-(-x-x-3)2 概要設(shè)計說明模塊調(diào)用圖:主函數(shù)多項式相加建立鏈表輸出多項式 1. 抽象數(shù)據(jù)類型的定義多項式的結(jié)點(diǎn)類型定義typedef struct Polynomial/多項式結(jié)點(diǎn)類型 float coef
5、; /多項式的系數(shù) int expn; /多項式的指數(shù) struct Polynomial *next;/指向下一個結(jié)點(diǎn)*Polyn,Polynomial;建立表示一元多項式的有序表Polyn CreatePolyn(Polyn head,int m);銷毀一元多項式void DestroyPolyn(Polyn p);返回一元多項式的項數(shù)void PrintPolyn(Polyn P);完成多項式加法運(yùn)算Polyn AddPolyn(Polyn pa,Polyn pb);完成多項式相減運(yùn)算Polyn SubtractPolyn(Polyn pa,Polyn pb);2.主程序的流程(1)輸出
6、提示信息(2)輸入多項式項數(shù)(3) 輸入每項的系數(shù)和指數(shù)(4)輸出選擇操作的菜單(5) 根據(jù)選擇輸出多項式(6)釋放鏈表占用的內(nèi)存空間(7)完成退出程序3.各程序模塊之間的層次(調(diào)用)關(guān)系本系統(tǒng)首先是創(chuàng)建多項式,在進(jìn)行排序顯示,然后按提示輸入要實(shí)現(xiàn)的功能。此系統(tǒng)有五個模塊,它們的調(diào)用關(guān)系如下:在CreatePolyn函數(shù)中調(diào)用Insert;在main函數(shù)中調(diào)用CreatePolyn(pa,m). CreatePolyn(pb,n). PrintPolyn(pa). PrintPolyn(pb). AddPolyn(pa,pb). SubtractPolyn(pa,pb). DestroyPol
7、yn(pa). DestroyPolyn(pb)3 詳細(xì)設(shè)計說明1.設(shè)計中定義的所有數(shù)據(jù)類型偽碼算法(1)多項式建立的算法該算法是用來創(chuàng)建多項式鏈表。首先要創(chuàng)建一個結(jié)點(diǎn),并用一個指針指向它,并給它進(jìn)行初始化void CreatPolyn(polynomial &p,int m)/輸入m項的系數(shù)和指數(shù),建立一元多項式的有序鏈表pInitList(p); h=GetHead(p);e.coef=0.0;e.expn=-1; SetCurElem(h,e);/設(shè)置頭結(jié)點(diǎn)的數(shù)據(jù)元素for(i=1;inext; int flag=1;/項數(shù)計數(shù)器 if(!q) putchar(0); /若多項式為空,輸
8、出0 printf(n); return; while(q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項 if(q-coef!=1&q-coef!=-1) /系數(shù)非1或-1的普通情況 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coe
9、f=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);(3)多項式加法的算法該模塊是實(shí)現(xiàn)兩個多項式相加的算法。要求兩個多項式的指數(shù)從小到大的排列順序。 void AddPolyn(polynomial &pa,polynomial &pb) /多項式加法 ha=GetHead(pa);hb=GetHead(pb); /ha和hb分別指向pa和pb的頭結(jié)點(diǎn) qa=NexPos(pa,ha);qb=NexPos(pb,hb);
10、/qa和qb分別指向和中當(dāng)前結(jié)點(diǎn) while(qa&qb) /qa和qb均非空 a=GetCurElem(qa);b=GetCurElem(qb); /a/和b為表中當(dāng)前比較元素 switch(*cmp(a,b)case -1: /多項式pa中當(dāng)前結(jié)點(diǎn)的指數(shù)較小 Ha=qa; qa=NexPos(pa,ha);case 0: /兩者的指數(shù)相等 sum=a.coef+b. coef; if(sum!=0.0) /修改多項式pa中當(dāng)前結(jié)點(diǎn)的系數(shù)值 SetCurElem(qa,sum); ha=qa; else /刪除多項式pa中當(dāng)前結(jié)點(diǎn) DelFirst(ha,qa);FreeNode(qa);D
11、elFirst(hb,qb);FreeNode(qb); qb=NexPos(pb,qb);qa=NexPos(pa,ha);break;case 1: /多項式pb中當(dāng)前結(jié)點(diǎn)的指數(shù)較小 DelFirst(hb,qb); InFirst(ha,qb); qb=NexPos(pb,hb); ha=NexPos(pa,ha); break if(!ListEmpty(pb) Append(pa.qb); /鏈接pb中剩余結(jié)點(diǎn)FreeNode(hb); /釋放pb的頭結(jié)點(diǎn)(4)多項式減法的算法該模塊是實(shí)現(xiàn)兩個多項式相減,它的設(shè)計思想和多項式相加類似,只是實(shí)現(xiàn)有點(diǎn)差別。 void SubtractPo
12、lyn(Polyn pa,Polyn pb) /求解并建立多項式a-b,返回其頭指針 Polyn h=pb; Polyn p=p-next; Polyn pd; while(p) /將pb的系數(shù)取反 p-coef*=-1;p=p-next;pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢復(fù)pb的系數(shù)p=p-coef*=-1;return pd;2、主程序和其它主要函數(shù) void main() int m,n,a,x;Char flag; Polyn pa=0,pb=0,pc; float ValuePolyn(Polyn head,int x) vo
13、id DestroyPolyn(Polyn p) Polyn q1,q2; q1=p-next; while(q1-next) free(q1) q1=q2;q2=q2-next; 4 調(diào)試分析 (1)、調(diào)試過程中遇到的問題是如何解決的以及對設(shè)計與實(shí)現(xiàn)的回顧討論和分析 問題1:在進(jìn)行多項式減法時,沒有真正的實(shí)現(xiàn)該功能,即有些多項式的系數(shù)并沒有變化。 原因:在進(jìn)行最后插入處理時,沒有改變多項式的系數(shù)變?yōu)橄喾磾?shù)。 解決方法:加了一條語句,即q-coef*=-1. 問題2:在進(jìn)行多項式顯示時,出現(xiàn)了加號和減號同時顯示的錯誤,并且最后一想后面還帶有加號。 原因:在輸入時沒有考慮正負(fù)號顯示問題。 解決方
14、法:在結(jié)點(diǎn)系為負(fù)時,不要輸出正號,控制最后一個加號,只要加一條語句,即if(p-next=NULL).(2)、算法的時間復(fù)雜度和空間復(fù)雜度的分析,改進(jìn)設(shè)想該算法的核心算法是多項式的排序算法和加減算法,排序算法的時間復(fù)雜度為O(n*n),而實(shí)現(xiàn)多項式加法的時間復(fù)雜度為O(n),所以本程序的時間復(fù)雜度為O(n*n).其中n為多項式的項數(shù)。由于多項式的排序算法和加減算法中只使用了一些簡單變量和指針變量,它的空間復(fù)雜度為O(1). 改進(jìn)思想:在實(shí)現(xiàn)加減法過程中可以把第二多項式所占的存儲空間釋放掉,這樣便于存儲空間的回收。還有在顯示多項式時可以采取更簡潔的方式,類似于指數(shù)方式顯示形式。5 用戶使用說明1
15、本程序的運(yùn)行環(huán)境為Visualc+6.02進(jìn)入演示程序后,即顯示文本方式的用戶界面:3按照提示輸入需要測試的數(shù)據(jù)4選擇相應(yīng)的操作,輸入對應(yīng)的操作6 課程設(shè)計總結(jié)數(shù)據(jù)結(jié)構(gòu)雖然已經(jīng)學(xué)了一個學(xué)期,但有許多知識還不是很清楚,許多數(shù)據(jù)結(jié)構(gòu)中的程序需要c語言的添加才能執(zhí)行。通過課程設(shè)計對這些知識也有了更深的理解和很好的掌握。許多困惑,有許多已經(jīng)通過實(shí)際操作解決了,并能夠深刻認(rèn)識,但也有很多沒有明白。通過課程設(shè)計,明白到了原來開發(fā)一個小小的實(shí)用系統(tǒng),是需要考慮到很多方面的問題的,許多程序在運(yùn)行時有很多小錯誤,在不仔細(xì)的情況下是不容易發(fā)現(xiàn)及改正的,這些都是要在實(shí)踐中摸索的,另外就是要把錯誤總結(jié),有許多錯誤或者
16、陷阱是平時自己陷進(jìn)去的,因此很深刻,但也有些錯誤或者陷阱是自己還沒有接觸或者犯過的,這就應(yīng)該看多些別人的總結(jié),使自己不犯這些錯誤。不讓自己掉進(jìn)這些陷阱。這樣長期總結(jié),會對自己有很大的幫助。由于時間原因程序到目前為止,還并不健壯,在對輸入小數(shù)時,還需要進(jìn)一步改進(jìn)。不過通過這次課程設(shè)計,我體會到了理論與實(shí)際的差別,不僅要學(xué)習(xí)理論知識,還要勤動手,多實(shí)踐。我感覺到要真正做出一個程序并不是很容易,但只需用心去做,總會有收獲,特別是當(dāng)我遇到問題去問老師,問同學(xué),想盡辦法去解決。對于數(shù)據(jù)結(jié)構(gòu)有了更深層次的理解,循環(huán)隊列中對邊界條件的處理,滿足什么條件為隊滿,滿足什么條件為隊空。在以后的學(xué)習(xí)中我會更加注意各
17、個方面的能力的協(xié)調(diào)發(fā)展,選擇一兩門技術(shù)進(jìn)行深入研究,成為一個既可以統(tǒng)籌全局,又有一定技術(shù)專長的優(yōu)秀的程序開發(fā)人員。7 測試結(jié)果1. (2x+5x8-3.1x11)+(7-5x8+11x9)的測試結(jié)果: 請輸入a的項數(shù):3請輸入第一項的系數(shù)與指數(shù):2 1請輸入第二項的系數(shù)和指數(shù):5 8請輸入第三項的系數(shù)和指數(shù):-3.1 11請輸入b的項數(shù):3請輸入第一項的系數(shù)和指數(shù):7 0請輸入第一項的系數(shù)和指數(shù):5 8請輸入第三項的系數(shù)和指數(shù):11 9* 多項式操作程序* A:輸出多項式a B:輸出多項式b * C:輸出a+b D:輸出a-b * E:退出程序 *請選擇操作:Ca+b=2x+5x8-3.1x1
18、1+7-5x8+11x92. (6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)的測試結(jié)果: 請輸入a的項數(shù):4請輸入第一項的系數(shù)與指數(shù):6 O請輸入第二項的系數(shù)和指數(shù):-3 1請輸入第三項的系數(shù)和指數(shù):4.4 2請輸入第四項的系數(shù)和指數(shù):請輸入b的項數(shù):4請輸入第一項的系數(shù)和指數(shù):-6 0請輸入第一項的系數(shù)和指數(shù):-3 1請輸入第三項的系數(shù)和指數(shù):5.4 2請輸入第四項的系數(shù)和指數(shù):7.8 15* 多項式操作程序* A:輸出多項式a B:輸出多項式b * C:輸出a+b D:輸出a-b * E:退出程序 *請選擇操作:D a-b=12-x2-1.2x9-7.8x1
19、53. (x+x2+x3)+0的測試結(jié)果: 請輸入a的項數(shù):3請輸入第一項的系數(shù)與指數(shù):1 1請輸入第二項的系數(shù)和指數(shù):1 2請輸入第三項的系數(shù)和指數(shù):1 3請輸入b的項數(shù):0* 多項式操作程序* A:輸出多項式a B:輸出多項式b * C:輸出a+b D:輸出a-b * E:退出程序 *請選擇操作:C a+b=x+x2+x34. (x+x3)-(-x-x-3)的測試結(jié)果: 請輸入a的項數(shù):2請輸入第一項的系數(shù)與指數(shù):1 1請輸入第二項的系數(shù)和指數(shù):1 3請輸入b的項數(shù):2請輸入第一項的系數(shù)和指數(shù):-1 1請輸入第一項的系數(shù)和指數(shù):-1 -3* 多項式操作程序* A:輸出多項式a B:輸出多項
20、式b * C:輸出a+b D:輸出a-b * E:退出程序 *請選擇操作:D a-b=x-3+2x+x38 參考書目1數(shù)據(jù)結(jié)構(gòu),湯文兵,華東理工大學(xué)出版社2數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析,李春葆,清華大學(xué)出版社3C語言課程設(shè)計案例精編,郭翠英,中國水利出版社4BAIDU搜索9 附錄帶注釋的源代碼:/頭文件#include#include#include/定義多項式的項typedef struct Polynomial float coef; int expn; struct Polynomial *next;*Polyn,Polynomial;void Insert(Polyn p,Polyn h) if
21、(p-coef=0) free(p);/系數(shù)為0的話釋放結(jié)點(diǎn) else Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnq2-expn)/查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn)/將指數(shù)相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef)/系數(shù)為0的話釋放結(jié)點(diǎn) q1-next=q2-next; free(q2); else/指數(shù)為新時將結(jié)點(diǎn)插入 p-next=q2; q1-next=p;Polyn CreatePolyn(Polyn head,int m)/建立一個
22、頭指針為head、項數(shù)為m的一元多項式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;void DestroyPolyn(Polyn p)/銷毀多項式p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next) free(q1); q1=q2; q2=q2-next;void PrintPolyn(Pol
23、yn P)Polyn q=P-next; int flag=1;/項數(shù)計數(shù)器 if(!q) /若多項式為空,輸出0 putchar(0); printf(n); return; while(q) if(q-coef0&flag!=1) putchar(+); /系數(shù)大于0且不是第一項 if(q-coef!=1&q-coef!=-1)/系數(shù)非1或-1的普通情況 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1
24、); else if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);int compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else
25、if(!a&b) return -1;/a多項式已空,但b多項式非空 else return 1;/b多項式已空,但a多項式非空Polyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b,返回其頭指針 Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點(diǎn) hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial
26、); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時,釋放該結(jié)點(diǎn) return headc;Polyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式a-b,返回其頭指針 Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p) /將pb的系數(shù)取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 回爐培訓(xùn)實(shí)施方案
- 北京市大學(xué)線性代數(shù)(行列式與矩陣)期末考試真題解析
- 2025年校園體育器材借用與歸還的標(biāo)準(zhǔn)化執(zhí)行標(biāo)準(zhǔn)
- 2025年小學(xué)數(shù)學(xué)應(yīng)用題競賽試卷:一年級上學(xué)期應(yīng)用題解題競賽
- 2025年教師進(jìn)修項目審批流程及規(guī)范
- 護(hù)理病例討論實(shí)施要點(diǎn)
- 2025年資產(chǎn)評估實(shí)務(wù)(二)無形資產(chǎn)評估模擬試卷(含評估創(chuàng)新)
- 勞動課標(biāo)解讀課件
- 培訓(xùn)講座課件
- 針對性訓(xùn)練計算機(jī)二級Python試題及答案
- 非遺扎染創(chuàng)新創(chuàng)業(yè)計劃書
- 超星爾雅學(xué)習(xí)通《先秦諸子導(dǎo)讀(浙江大學(xué))》2025章節(jié)測試附答案
- 江蘇社工考試試題及答案
- 2025年勞務(wù)合同模板電子版簡短一點(diǎn)
- 二級建造師繼續(xù)教育題庫(帶答案)
- 市場監(jiān)管投訴舉報培訓(xùn)
- 《新能源乘用車二手車鑒定評估技術(shù)規(guī)范 第1部分:純電動》
- 課題申報參考:西藏地方與祖國關(guān)系史融入當(dāng)?shù)馗咝!爸腥A民族共同體概論”課教學(xué)研究
- 【MOOC】《C++程序設(shè)計基礎(chǔ)》(華中科技大學(xué))章節(jié)作業(yè)中國大學(xué)慕課答案
- 《南方航空公司匯率風(fēng)險管理策略案例分析》
- 病房心臟驟停應(yīng)急演練
評論
0/150
提交評論