




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、成績 南京工程學院 課程設計說明書(論文) 題目 課程名稱數(shù)據(jù)結構 院(系、部、中心)通信工程 專業(yè)計算機通信 班級算通111 學生姓名余丹紅 學號 208110410 設計地點信息樓322 指導教師郝慧珍 設計起止時間:2012年12月17日至2012年12月18日 目錄 1設計目標 1 2總體設計 1 21 數(shù)據(jù)結構描述與定義 1 22 模塊設計 2 3測試結果與分析 11 4課程設計總結 13 參考文獻 : 15 附錄 A : 源程序清單 15 通過課程設計,達到理論與實際應用相結合,提高學生組織數(shù)據(jù)及編寫大型 程序的能力,使學生能夠根據(jù)數(shù)據(jù)對象的特性,掌握數(shù)據(jù)組織、算法設計、算法 性能
2、分析的方法,并培養(yǎng)良好的程序設計能力。 本程序是利用單鏈表來表示一元多項式然后實現(xiàn)各項指數(shù)和系數(shù)的輸入, 進 行多項式建立,并以多項式的形式輸出,實現(xiàn)多項式的相加,相減和多項式的相 乘這三種運算。 2 總體設計 2 .1數(shù)據(jù)結構描述與定義 元多項式定義系數(shù)和指數(shù)結構如下: coef exp n n ext coef域-存放結點的系數(shù)值 expn域-存放結點的指數(shù)值 next域-存放結點的直接后繼的地址(位置)的指針域(鏈域) 定義多項式的結構為線性鏈表的存儲結構,每個結點包含三個元素:系數(shù) coef,指數(shù)expn和指向下一個結點的指針*next。通過指針,我們就可以把多個 單項式連接起來,形式
3、一個多項式,需要說明的是從廣義的角度講,單項式也是 一個多項式?;谝陨系姆治?,我們定義多項式的數(shù)據(jù)結構為如下結構體形式: typedef struct Poly no mial float coef;/ 系數(shù) int exp n;/ 指數(shù) struct Poly nomial *n ext;/ 下一個指針 *Poly n,Poly no mial; /Polyn結構體變量名 從實現(xiàn)多項式式運算過程的角度來分析,至少需要這樣一些子功能模塊 多項式創(chuàng)建功能 多項式銷毀功能 多項式輸出功能 多項式的相加功能 多項式的相減功能 多項式的相乘功能 定義并調用的函數(shù)有: void Insert(Poly
4、n p,Polyn h);將結點 p 插入鏈表 h Polyn CreatePoly n(Polyn head,i nt m);創(chuàng)建鏈表(多項式) void DestroyPoly n(Polyn p);銷毀 void Prin tPoly n(Polyn P); 輸出 Polyn AddPoly n(Polyn pa,Pol yn pb);/a+b Polyn SubtractPoly n(Polyn pa,Pol yn pb);/a-b Polyn MultiplyPolyn(Polyn pa,Polyn pb);/a*b void ma in()主函數(shù) 系統(tǒng)共分幾個模塊,每個模塊的算法描
5、述及流程圖(核心模塊) 1 系統(tǒng)模塊圖(模塊劃分) 程諾躊攜矗 窯項式的創(chuàng)建 多項式的相乘 多項式的相減 多項式的相加 多項式的輸出 多項式的銷毀 圖1系統(tǒng)模塊劃分圖 2. 模塊流程圖及算法描述 分模塊流程圖 多項式的銷毀 多項式的創(chuàng)建 (3)多項式的輸出 (4) 多項式的相加 開始 定義存儲和鏈表 he動態(tài)分配空間 qa=pa-n ext qb=pb-n ext qa的各個值賦給qe qa指向qa的next qb的各個值賦給qc qb指向qb的next qa的系數(shù)加qb的系數(shù)賦 給qe的系數(shù) qa的指數(shù)賦給qc的指數(shù) qa指向qa的next qb指向qb的next (5)多項式的相減多項式的
6、相乘 結束 算法描述 (1) 多項式的創(chuàng)建 Polyn CreatePolyn(Polyn head,int m) /建立一個頭指針為head、項數(shù)為m的一元多項式 /在主程序初始時,先輸入的多項式中的項數(shù)m n在這里為 m主程序中的pa、pb在此 為 head int i;/ 用來計數(shù) 動態(tài)分配空間,建立頭結點 建立新結點以接收數(shù)據(jù) 上面循環(huán)中 i 從 0 開始,所以 Polyn p;/ 定義一個 p 鏈表 p=head=(Polyn)malloc(sizeof(struct Polynomial);/ head-next=NULL; for(i=0;icoef, Insert(p,head
7、); /調用 Insert 函數(shù)插入結點 p return head; (2) 多項式的銷毀 利用循環(huán)逐漸銷毀多項式 void DestroyPolyn(Polyn p) /銷毀多項式 p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next)/ 利用循環(huán)逐漸銷毀多項式 P free(q1); q1=q2;/ 指針后移 q2=q2-next; free(q1); (3) 多項式的輸出 void PrintPolyn(Polyn P) / 輸出多項式 Polyn q=P-next; int flag=1;/項數(shù)計數(shù)器 if(!q) / 若多項式為空,
8、輸出 0 putchar(0); printf(n); return; while(q) / 多項式存在 if(q-coef0 / 系數(shù)大于 0 且不是第一項 if(q-coef!=1 /%g 哪一個 if(q-expn=1) putchar(X); / else if(q-expn) prin tf(XA%d,q-exp n); /指數(shù)不為 1 else if(q-coef=1) /系數(shù)為 1 的情況 if(!q-expn) putchar(1); /指數(shù)為 0,則為 1 else if(q-expn=1) putchar(X); / 指數(shù)為 1 則為 x else prin tf(XA%d
9、,q-exp n); if(q-coef=-1)/ 系數(shù)為 -1 的情況 if(!q-expn) printf(-1); /指數(shù)為 0,則為 -1 else if(q-expn=1) printf(-X); / 指數(shù)為 1, 則為 -x else printf(-XA%d,q-expn); q=q-next; flag+; / 項數(shù)加 1 printf(n); (4) 多項式的相加 利用對 a、b 兩個多項式每一項分模塊討論進行的,如a 指數(shù)大或者 b 空,則將 a 項該節(jié)點插入新鏈 c 中,若 b 指數(shù)大或者 a 空,則將 b 項插入到 c 中,如若 a、 b 兩項指數(shù)相等,則合并后再插入到
10、 c 鏈中。 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);/建立頭結點 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb) case 1: qc-coef=qa-coef; qc-exp
11、n=qa-expn; / a qa=qa-next; /qa break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; /qc qa=qa-next; qb=qb-next; /qa break; case -1: 的指數(shù)大或 b 為空,把 qa 賦值給 qc 指向下一個 等于 qa 與 qb 的和 , qb 都分別指向下一個 的指數(shù)大或 a 為空,把 qb 賦值給 qc 指向下一個 qc-coef=qb-coef; /b qc-expn=qb-expn; qb=qb-next; /qb break; if(qc-coef!=0) qc-
12、next=hc-next;/qc 插入到 hc 中去,并重新生成新的 hc ,到最后實現(xiàn) a 與 b 的和 hc-next=qc; hc=qc; else free(qc);/ 當相加系數(shù)為 0 時,釋放該結點 return headc; /返回頭指針,實現(xiàn)多項式 a 與 b 的相加 (5) 多項式的相減 利用 a-b=a+(-b) 來進行的,即只將 b 系數(shù)取反即可。 Polyn SubtractPolyn(Polyn pa,Polyn pb) / 求解并建立多項式 a-b ,返回其頭指針,將 pb 的系數(shù)取反后調用相加的函數(shù),實現(xiàn)相減 功能 Polyn h=pb; Polyn p=pb-n
13、ext; Polyn pd; while(p) 將 pb 的系數(shù)取反 向后移動 恢復 pb 的系數(shù) / p-coef*=-1; p=p-next; /p pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) / 返回 pd 的值,實現(xiàn) a 與 b 兩個多項式相減 p-coef*=-1; return pd; / (6) 多項式的相乘 將 a 中的每一項乘 b 中的每一項, 即系數(shù)相乘, 指數(shù)相加, 將它放在新節(jié)點中并 插入新鏈h,最后返回鏈ho Polyn MultiplyPolyn(Polyn pa,Polyn pb) / 求解并建立多項式 a*b ,返回其
14、頭指針 Polyn hf,pf; Polyn qa=pa-next; 建立頭結點 Polyn qb=pb-n ext; hf=(Po lyn) malloc(sizeof(struct Polyno mial);/ hf-n ext=NULL; for(;qa;qa=qa-n ext) for(qb=pb-n ext;qb;qb=qb-n ext) pf=(Po lyn) malloc(sizeof(struct Polyno mial); pf-coef=qa-coef*qb-coef; pf-exp n=qa_exp n+qb_exp n; Insert(pf,hf);/調用Insert函
15、數(shù)以合并指數(shù)相同的項 return hf; 3.測試結果與分析 系統(tǒng)選擇界面如圖1 圖1 輸入數(shù)據(jù)為: 2( enter) 2( pase) 3( enter) 8( pase) 2( enter) 3( enter) 5( pase) 1 ( enter) 3( pase) 6( enter) 7( pase) 2( enter)請揃一入扶的項數(shù)池 請勒入壘項的系數(shù)與扌旨數(shù)汐3 請輸入笫項的系數(shù)與箱數(shù)涓2 請輸入h的項數(shù)汩 項的系數(shù)與扌旨數(shù)汚1 請輸人響項的系數(shù)則旨數(shù)汩6 請侖入靂3項的系數(shù)與塘數(shù)汐2 圖2 輸出菜單:如圖2 圖3 分別輸入a,b,c,d,e五個選項 顯示結果:如圖4 輸入f
16、,結束,顯示結果:如圖五 圖4 X *D: UserDat aAdinist rat or桌面Debugyydxs. exe I i-i r -i f. q I I I I I I I r r-斗 I 、 Press any key to continue zi 4.課程設計總結 一.程序總結 計算一元多項式加法,其結果取決于多項式的各項系數(shù)與指數(shù), 因此程序核 心是處理兩個多項式的系數(shù)與指數(shù)。定義結構體將多項式的各項系數(shù)與指數(shù)存 放,定義結構體類型鏈表為程序的循環(huán)控制提供了可能,利用對鏈表的運算來確 定結果多項式的各項系數(shù)與次數(shù),同理算出相應的幕數(shù)。鏈表是在計算機內存中 使用一組連續(xù)的存儲單
17、元保存數(shù)據(jù)類型和名字相同的變量。就鏈表這種數(shù)據(jù)類型 而言,在排列上采用的方法也是按序排放,先存放第一行,接著存放第二行, 直到所有數(shù)據(jù)元素被存放。多項式采用的是鏈表形式,以犧牲一定的空間提高程 序的運行速度和可行性。 采用鏈式結構存儲多項式,用鏈表結構體的一個域標記多項式的次數(shù),另一 個域標記多項式的系數(shù),程序中采用的是m表示最高次系數(shù),進行加法運算時, 標記系數(shù)域相加即為相加的對應系數(shù),標記指數(shù)域相同則表示為同類項。 鏈表的特性是在中間任意位置添加刪除元素的都非常的快, 不需要移動其它 的元素。鏈表顧名思義,要把各個元素鏈接起來才算撒。 通常鏈表每一個元素都 要保存一個指向下一個元素的指針(
18、單鏈表)。 二.錯誤分析 錯誤產生的原因有很多: 1. 函數(shù)定義沖突; 2. 函數(shù)調用錯誤; 3. 符號字母等輸入錯誤; 4. 鏈表的定義錯誤; 5. 變量名重復發(fā)生沖突; 6. 指針指向發(fā)生錯誤; 7. 未釋放空空間; 錯誤顯示:如圖6 D:UserDatafldniinistrator D:UserDataftdiiinistrator D:userDatafldministrator D:LJi serDataA dnini strator D:MJ5erDatafldiiini5trator D:UsprDataAdninitrator D:userDataAdninistrator
19、D:UserDataArlrainistrator D:UserDataXfidninistrator D:UserDataArirainistrator D:MJ5erDataAditini5trator D:UserDataAdMnistrator D:U5BrDataA dni n i stratorX D:UserDatafldrainistrator D:UserDataXdiiini5trator 執(zhí)行cl.exe時出錯- Qipdxs,cpp(59) : error jfdxs.cpp(62) : error jjipdxs.cpp(62) : error 面iydKs.cpp(
20、9li) : error i)j)i(jxs.cpp(95) : error 面jjpdxspdxs.cpp(99): 面vpdxs4cpp(101): pdxs.cppf 182)1 : 面 iijji(lxs,cpp(1flU): 面列妣呂q)p(1仙): 面|iydxscpp(164): dxs-cpp(105): 面dxs.cpp(117): ujjidxs.cpp(196) : earning1 vstroyPoluo : fuoction error i :error i error :error error error error error error C2A1B: unkno
21、w character * 0 xe2p C21K3: C2143: C2O4kfi: C2BU: C20Q1I: C2143: C20fi; C2lfi: C2S01: C2O65: C2143: C2U6: C28W: syntax error : missing syntax error : missing illegal cm呂 illegal case mB before syntax error : missing 1; (?ror : missing ; illegal default identifier before before should breaK string1 i
22、dentifier printf return s value; S 三.收獲與體會 本次課程設計,我查找過資料,請教過同學,以及自己的努力,不僅培養(yǎng)了 獨立思考、動手操作的能力,在各種其它能力上也都有了提高。更重要的是,在 程序設計中,我學會了很多學習的方法,而這是日后最實用的,真的是受益匪淺。 本學期的程序設計課程,我鍛煉了能力,學到很多東西,比如思考問題的角度也 會從多方面著手;對自己的專業(yè)也有自己的想法 在和同學的交流過程中,互 動學習,將知識融會貫通。通過這次課程設計,我對很多的函數(shù)有了新的認識, 也學會了運用多種函數(shù),我也明白了寫軟件的基本過程和基本方法。在程序的設 計過程中遇到了
23、很多的困難, 在程序一次一次的調試失敗下曾經想過要放棄, 我 最后還是讓自己堅持下來, 毫不畏懼困難, 在同學的幫助與講解下我總算是順利 的完成了程序的課程設計。 另外也需要提出的是在這次程序設計的過程中, 非常 感謝老師對我們的耐心指導。 老師在教學過程中表現(xiàn)出來的對學術專研一絲不茍 的精神讓我非常有收獲。 在這幾天的編寫過程中我對語言有了更進一步的認識和了解, 也感受到了編 程給我?guī)淼目鞓放c充實, 明白了想成為一個合格的甚至是優(yōu)秀的程序員, 我還 需要更多更難的鍛煉。所以我還要不斷地學習不斷地學習 , 不斷地成長。 參考文獻 : 1 嚴蔚敏,吳偉民數(shù)據(jù)結構(C語言版).北京:清華大學出版
24、社,1997 2朱戰(zhàn)立 數(shù)據(jù)結構西安:西安電子科技大學出版社 ,2004 3嚴蔚敏,吳偉民. 數(shù)據(jù)結構題集(C語言版).北京:清華大學出版社,2000 附錄 A: 源程序清單 #include #include #include /定義多項式數(shù)據(jù)結構 typedef struct Polynomial float coef;/系數(shù) int expn;/指數(shù) struct Polynomial *next; /下一個指針 *Polyn,Polynomial; /Polyn 結構體變量名 void Insert(Polyn p,Polyn h);/ 將結點 p 插入鏈表 h Polyn Creat
25、ePolyn(Polyn head,int m);/ 創(chuàng)建鏈表(多項式) void DestroyPolyn(Polyn p);/ 銷毀 void PrintPolyn(Polyn P);/ 輸出 int compare(Polyn a,Polyn b);/ 比較 a, b 的指數(shù)大小,為下面 a+b 做鋪墊 Polyn AddPolyn(Polyn pa,Polyn pb);/a+b Polyn SubtractPolyn(Polyn pa,Polyn pb);/a-b Polyn MultiplyPolyn(Polyn pa,Polyn pb);/a*b /* 主函數(shù) */ void ma
26、in() int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; /system(color F5);/ 字體顏色 system(color 5F);/ 背景顏色 printf(n); E* printf( * * *nn); E L C O M printf( * 歡迎使用簡便式一元多項式計算程序】 * *nn); printf( * *nn ); * printf( * *nn ); printf( * 請按 以下提示請輸入 您所需的數(shù) * *nn); printf(* 【使用說明:您可建立 a,b 兩個多項式,并進行相加、相減、相乘三種運 算】 *nn);
27、 * printf( * printf( * *n); printf( * *n); printf( * *n); printf( * *n); printf( * *n); printf( * A. 【 輸 出多項 式 B. 【 輸 出多 項 式 C. 【 輸出 a+b D. 【 輸出 a-b E. 【 輸出 a*b F. 【 退出 程 序 a】 b】 】 】 】 】 printf( 請輸入 a 的項數(shù) :); scanf(%d, pa=CreatePolyn(pa,m);/ 建立多項式 a printf( 請輸入 b 的項數(shù) :); scanf(%d, pb=CreatePolyn(pb,
28、n);/ 建立多項式 b system(cls); printf(n); H* *n); * printf( H* ); while(1) printf(n 請選擇操作: ); scanf( %c,/ 空格符號一定要注意 switch(flag) caseA: casea: printf(n 多項式 a=); PrintPolyn(pa); break; caseB: caseb: printf(n 多項式 b=); PrintPolyn(pb); break; caseC: casec: pc=AddPolyn(pa,pb); printf(n a+b=); PrintPolyn(pc);
29、break; caseD: cased: pc=SubtractPolyn(pa,pb); printf(n a-b=); PrintPolyn(pc); break; caseE: casee: pc=MultiplyPolyn(pa,pb); printf(n a*b=); PrintPolyn(pc); break; caseF: casef: system(cls); printf(n); printf(n); printf(t* * n); printf(t* * *nn); printf(t* * *nn); printf(t* * *nn); printf(t* * 感謝使用此
30、0( n _ 再 Made by 程序 n )0 見 YDH * *nn); printf(t* * n); DestroyPolyn(pa); DestroyPolyn(pb); return; default: printf(n 您的選擇錯誤,請重新選擇 !n); * 合并兩個多項式 * void Insert(Polyn p,Polyn h) /將兩個多項式合并的算法,即將p 插入 h 來實現(xiàn) if(p-coef=0) free(p);/ 系數(shù)為 0 的話釋放結點 else Polyn q1,q2; q1=h; q2=h-next; while(q2 q2=q2-next; if(q2
31、free(p); if(!q2-coef) / 系數(shù)為 0 的話釋放結點 q1-next=q2-next;/ 將 q2 釋放掉 free(q2); else / 指數(shù)為新時將結點插入 p-next=q2; / 將 p 結點插入到 h 中去 q1-next=p; * 建立一元多項式 * Polyn CreatePolyn(Polyn head,int m) /建立一個頭指針為 head、項數(shù)為m的一元多項式 pa、 pb 在此 在主程序初始時,先輸入的多項式中的項數(shù)m、n在這里為m。主程序中的 為 head int i;/ 用來計數(shù) Polyn p;/ 定義一個 p 鏈表 p=head=(Pol
32、yn)malloc(sizeof(struct Polynomial);/ 動態(tài)分配空間,建立頭結點 head-next=NULL; for(i=0;icoef, Insert(p,head);/調用 Insert 函數(shù)插入結點 p return head; * 銷毀多項式 * void DestroyPolyn(Polyn p)/銷毀多項式 p Polyn q1,q2; q1=p-next; q2=q1-next; while(q1-next)/ 利用循環(huán)逐漸銷毀多項式 P free(q1); q1=q2;/ 指針后移 q2=q2-next; free(q1); 輸出多項式 * /* voi
33、d PrintPolyn(Polyn P) /輸出多項式 Polyn q=P-next; int flag=1;/ 項數(shù)計數(shù)器 if(!q) / 若多項式為空,輸出0 putchar(0); printf(n); return; while(q)/多項式存在 if(q-coef0 / 系數(shù)大于 0 且不是第一項 if(q-coef!=1g表示使用%e或f,哪個輸出寬度稍短就使用哪 一個 if(q-expn=1) putchar(X); /若指數(shù)為 1 else if(q-expn) prin tf(XA%d,q-exp n);/ 指數(shù)不為 1 else if(q-coef=1)/系數(shù)為 1 的
34、情況 if(!q-expn) putchar(1);/指數(shù)為 0,則為 1 else if(q-expn=1) putchar(X); / 指數(shù)為 1 則為 x else prin tf(XA%d,q-exp n); if(q-coef=-1)/ 系數(shù)為 -1 的情況 if(!q-expn) printf(-1);/指數(shù)為 0,則為 -1 else if(q-expn=1) printf(-X); / 指數(shù)為 1,則為 -x else prin tf(-XA%d,q-exp n); q=q-next; flag+;/ 項數(shù)加 1 printf(n); * 分模塊討論 * int compare
35、(Polyn a,Polyn b) if(a/b 為空或 a 的指數(shù)大 else if(a-expnexpn) return -1;/a 為空或者 b 的指數(shù)大 else return 0; else if(!a/a 多項式已空,但 b 多項式非空 else return 1;/b 多項式已空,但 a 多項式非空 /* 建立多項式 a+b*/ 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);/ 建立頭結點 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(str
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論