數據結構課程設計報告一元多項式的實現

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數：12 大小：107.00KB 人氣指數：12 舉報 版權申訴

已閱讀1頁，還剩11頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　《數據結構》課程設計　　題目一元多項式的實現　　學號 　　學生姓名 　　院系計算機　　專業(yè) </p

2、>　　指導教師 　　二Ｏ一二年 12 月 17 日　　需求分析　　建立一元多項式并按照指數降序排列輸出多項式，將一元多項式輸入并存儲在內存中，能夠完成兩個多項式的加減運算并輸出結果<p&

3、gt;　　概要設計　　存儲結構：一元多項式的表示在計算機內可以用鏈表來表示，為了節(jié)省存儲空間，只存儲多項式中系數非零的項。鏈表中的每一個結點存放多項式的一個系數非零項，它包含三個域，分別存放該項的系數、指數以及指向下一個多項式項結點的指針。創(chuàng)建一元多項式鏈表，對一元多項式的運算中會出現的各種可能情況進行分析，實現一元多項式的相加、相減操作。

4、;　　基本算法：　　1、輸入輸出　?。?）功能：將要進行運算的多項式輸入輸出。　?。?）數據流入：要輸入的多項式的系數與指數。　?。?）數據流出：合并同類項后的多項式。<

5、;/p>　　（4）程序流程圖：多項式輸入流程圖如圖1所示。　?。?）測試要點：輸入的多項式是否正確，若輸入錯誤則重新輸入　　2、多項式的加法　?。?）功能：將兩多項式相加。　?。?）數據流入：輸入函數。&l

6、t;/p>　　（3）數據流出：多項式相加后的結果。　?。?）程序流程圖：多項式的加法流程圖如圖2所示。　?。?）測試要點：兩多項式是否為空，為空則提示重新輸入，否則，進行運算。　　圖表 2

7、　　3、多項式的減法　?。?）功能：將兩多項式相減。　?。?）數據流入：調用輸入函數。　?。?）數據流出：多項式相減后的結果。　?。?）程序流程圖：多項式的減法流程圖如圖3所示。　?。?）測試要點：兩多項式是否

8、為空，為空則提示重新輸入，否則，進行運算。　　詳細設計 　　#include<stdio.h>　　#include<malloc.h>　　typedef struct Polynomial{

9、;　　float coef;　　int expn;　　struct Polynomial *next;　　}*Polyn,Polynomial; //Polyn為結點指針類型　　voi

10、d Insert(Polyn p,Polyn h){ 　　if(p->coef==0) free(p); //系數為0的話釋放結點　　else{　　Polyn q1,q2;　　q1=h;q2=h->ne

11、xt;　　while(q2&&p->expn<q2->expn){ //查找插入位置　　q1=q2;　　q2=q2->next;　　}

12、;　　if(q2&&p->expn==q2->expn){ //將指數相同相合并　　q2->coef+=p->coef;　　free(p);　　if(!q2->coef){ /

13、/系數為0的話釋放結點　　q1->next=q2->next;　　free(q2);　　}　　}　　el

14、se{ //指數為新時將結點插入　　p->next=q2;　　q1->next=p;　　}　　}<p&g

15、t;　　}//Insert　　Polyn CreatePolyn(Polyn head,int m){//建立一個頭指針為head、項數為m的一元多項式　　int i;　　Polyn p;</p

16、>　　p=head=(Polyn)malloc(sizeof(struct Polynomial));　　head->next=NULL;　　for(i=0;i<m;i++){　　p=(Polyn)malloc(sizeof(struct Polynomial));//建立

17、新結點以接收數據　　printf("請輸入第%d項的系數與指數:",i+1);　　scanf("%f %d",&p->coef,&p->expn);　　Insert(p,head); //調用Insert函數插入結點&

18、lt;p>　　}　　return head;　　}//CreatePolyn　　void DestroyPolyn(Polyn p){//銷毀多項式p　　Polyn q1,q2;　　q1

19、=p->next;　　q2=q1->next;　　while(q1->next){　　free(q1);　　q1=q2;//指針后移　　q2=q2->next;<

20、/p>　　}　　}　　void PrintPolyn(Polyn P){ 　　Polyn q=P->next; 　　int flag=1;//項數計數器</

21、p>　　if(!q) { //若多項式為空，輸出0　　putchar('0'); 　　printf("\n");　　return;　　} </

22、b>　　while (q){　　if(q->coef>0&&flag!=1) putchar('+'); //系數大于0且不是第一項　　if(q->coef!=1&&q->coef!=-1){//系數非1或-1的普通情況</p&g

23、t;　　printf("%g",q->coef); 　　if(q->expn==1) putchar('X');　　else if(q->expn) printf("X^%d",q->expn);

24、;　　}　　else{　　if(q->coef==1){　　if(!q->expn) putchar('1'); 　　else if(q->expn==1) putchar(

25、9;X'); 　　else printf("X^%d",q->expn);　　}　　if(q->coef==-1){　　if(!q->expn) printf("-1"

26、); 　　else if(q->expn==1) printf("-X"); 　　else printf("-X^%d",q->expn);　　}　　}</b

27、>　　q=q->next; 　　flag++;　　}//while　　printf("\n");　　}//PrintPol

28、yn　　int compare(Polyn a,Polyn b){　　if(a&&b){　　if(!b||a->expn>b->expn) return 1;　　else if(!a||a->e

29、xpn<b->expn) return -1;　　else return 0;　　}　　else if(!a&&b) return -1;//a多項式已空，但b多項式非空　　else return 1;//

30、b多項式已空，但a多項式非空　　}//compare　　Polyn AddPolyn(Polyn pa,Polyn pb){//求解并建立多項式a+b，返回其頭指針　　Polyn qa=pa->next;　　Polyn qb=pb->next;</p&g

31、t;　　Polyn headc,hc,qc;　　hc=(Polyn)malloc(sizeof(struct Polynomial));//建立頭結點　　hc->next=NULL;　　headc=hc;

32、　while(qa||qb){　　qc=(Polyn)malloc(sizeof(struct Polynomial));　　switch(compare(qa,qb)){　　case 1:　　{

33、　　qc->coef=qa->coef;　　qc->expn=qa->expn;　　qa=qa->next;　　break;　　}</b&

34、gt;　　case 0:　　{ 　　qc->coef=qa->coef+qb->coef;　　qc->expn=qa->expn;<p&

35、gt;　　qa=qa->next;　　qb=qb->next;　　break;　　}　　case -1:

36、　　{　　qc->coef=qb->coef;　　qc->expn=qb->expn;　　qb=qb->next;　　break;<p&

37、gt;　　} 　　}//switch　　if(qc->coef!=0){　　qc->next=hc->next;　　hc->next=qc;<

38、p>　　hc=qc;　　}　　else free(qc);//當相加系數為0時，釋放該結點　　}//while　　return headc;</p

39、>　　}//AddPolyn　　Polyn SubtractPolyn(Polyn pa,Polyn pb){//求解并建立多項式a+b，返回其頭指針　　Polyn h=pb;　　Polyn p=pb->next;　　P

40、olyn pd;　　while(p){ //將pb的系數取反　　p->coef*=-1;　　p=p->next;　　}　　pd=AddPol

41、yn(pa,h);　　for(p=h->next;p;p=p->next) //恢復pb的系數　　p->coef*=-1;　　return pd;　　}//SubtractPolyn　　int main()

42、{　　int m,n,flag=0;　　float x;　　Polyn pa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULL　　printf("請輸入a的項數:");&

43、lt;/p>　　scanf("%d",&m);　　pa=CreatePolyn(pa,m);//建立多項式a　　printf("請輸入b的項數:");　　scanf("%d",&n);&

44、lt;p>　　pb=CreatePolyn(pb,n);//建立多項式a　　//輸出菜單　　printf("**********************************************\n");　　printf("操作提示：

45、\n\t1.輸出多項式a和b\n\t2.建立多項式a+b\n\t3.建立多項式a-b\n");　　printf("\t4.退出\n**********************************************\n");　　for(;;flag=0){　　printf(&

46、quot;執(zhí)行操作：");　　scanf("%d",&flag);　　if(flag==1){　　printf("多項式a：");PrintPolyn(pa);　　printf("多項式b：")

47、;PrintPolyn(pb);continue;　　}　　if(flag==2){　　pc=AddPolyn(pa,pb);　　printf("多項式a+b：");PrintPolyn(pc);

48、;　　DestroyPolyn(pc);continue;　　}　　if(flag==3){　　pd=SubtractPolyn(pa,pb);　　printf("多項式a-b：");Prin

49、tPolyn(pd);　　DestroyPolyn(pd);continue;　　}　　if(flag==4) break;　　if(flag<1||flag>4) printf("Error!!!\n"

50、;);continue;　　}//for　　DestroyPolyn(pa);　　DestroyPolyn(pb);　　return 0;

51、;　　}　　調試結果　　測試的數據及結果　　算法的時間復雜度及改進　　算法的時間復雜度：一元多項式的加法運算的時間復雜度為O(m+n）,減法運算的時間復雜度為O(m-n)，其中

52、m，n分別表示二個一元多項式的項數。　　問題和改進思想：在設計該算法時，出現了一些問題，例如在建立鏈表時頭指針的設立導致了之后運用到相關的指針時沒能很好的移動指針出現了數據重復輸出或是輸出系統(tǒng)缺省值，不能實現算法。實現加法時該鏈表并沒有向通常那樣通過建立第三個鏈表來存放運算結果，而是再度利用了鏈表之一來進行節(jié)點的比較插入刪除等操作。為了使輸入數據按指數降序排列，可在數據的輸入后先做一個節(jié)點的排序

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數據結構課程設計報告一元多項式的實現

文檔簡介

溫馨提示

最新文檔

評論

數據結構課程設計報告一元多項式的實現

文檔簡介

溫馨提示

最新文檔

評論

免費下載