數(shù)據(jù)結(jié)構課程設計一元多項式

1、湖南工學院課程設計一元多項式計算班級：信息本1002學號： 09姓名：班級：信息本1002學號：26姓名：班級：信息本1002學號：34姓名：班級：信息本1002學號：41姓名：目 錄一、課題任務1二、概要設計1三、詳細設計2四、調(diào)試分析6五、測試結(jié)果6六、課程設計總結(jié)9七、參考文獻9八、附錄10一、課題任務功能： 1）能夠按照指數(shù)降序排列建立并輸出多項式； 2）能夠完成兩個多項式的相加，并將結(jié)果輸出； 3）能根據(jù)輸入的多項式及變量的值，能進行計算。并輸出計算結(jié)果。 4）能對多個輸入的表達式按照指數(shù)大小排序輸出。二、概要設計一元多項式計算系統(tǒng)降序排列建立并輸出多項式多項式的相加減并輸出結(jié)果輸入

2、的多項式及變量的值計算多個表達式按照指數(shù)大小排序輸出按指數(shù)排序建立多項式相減建立多項式相加計算多項式建立多個多項式輸出多式項或計算值排序后輸出多個多項式排序三、詳細設計一元多項式定義系數(shù)和指數(shù)結(jié)構如下： coefexpnnextcoef域-存放結(jié)點的系數(shù)值expn域-存放結(jié)點的指數(shù)值next域-存放結(jié)點的直接后繼的地址（位置）的指針域（鏈域）一元多項式單鏈表存儲結(jié)構：typedef struct term float coef; /系數(shù) int expn; /指數(shù) struct term *next; term;有了鏈表特定的數(shù)據(jù)類型term，接下來就需要建立這個鏈表。這里我們自定義一個構造函

3、數(shù)CreatePoly（）來構造鏈表。首先定義一個term型的指針變量h=p作為頭結(jié)點，存儲多項式的信息（項數(shù)），為h分配存儲空間建立一個頭結(jié)點并為其數(shù)據(jù)域賦值，分配存儲空間用malloc()函數(shù)來實現(xiàn)；這時輸入多項式的項數(shù)m，先給p的coef賦值為0，此時利用一個for循環(huán)將p鏈表的coef與expn值從鍵盤輸入，用m來控制循環(huán)的次數(shù)，若該從鍵盤輸入的coef值不為0，則將該數(shù)值插入鏈表新建鏈表q，用malloc（）分配給p空間，p=p->next繼續(xù)從鍵盤輸入coef與expn的值，直到滿足p->next=null,輸入完成，返回鏈表q即為多項式的系數(shù)與指數(shù)，創(chuàng)建多項式完成。在

4、處理多項式相加的問題上，由于事先建立的多項式函數(shù)已經(jīng)按指數(shù)大小排好序，那么多項式的相加就變得不那么復雜了，我們只要找出兩個相加多項式指數(shù)相同的項進行合并，即將指數(shù)相同的項的系數(shù)相加，其它的保持不變存好即可。而查找指數(shù)相同的項，只要按鏈表從頭到尾進行掃描，若發(fā)現(xiàn)相同，則兩個同時往下移，否則只將其中指數(shù)較大的往下移。假若兩個指數(shù)相同的項進行合并時，其系數(shù)相加值為0，則消除該項，繼續(xù)下去。在處理輸入的多項式及變量的值計算結(jié)果的問題時，定義一個C（）函數(shù)實現(xiàn)，需要定義一個float變量sum來存儲和值，再引用一個pow()函數(shù)來計算多項式的和，利用一個for循環(huán)來一一計算x的q->expn次方后

5、與q->coef相乘的值，并存儲在sum中，q=q->next，直到q->next =unll，跳出for循環(huán)，返回 sum的值就是多項式在用x賦值后的值。對多個輸入的表達式按照指數(shù)從大到小排序輸出:，利用一個for（包含兩個函數(shù)CreatPolyn(M,n);selsort(M);）循環(huán)，用scanf()輸入k來控制for的次數(shù)可控制輸入的多項式個數(shù)，并一個trem型數(shù)組Gi來保存每一個多項式，方便后來的按最高指數(shù)大小排序。排序的思想利用枚舉排序法可將每個多項式最高次expn按從大到小排列并保存在Gi數(shù)組中，再次利用for將排序好的Gi多項式按指數(shù)從大到小輸出。開始具體子功

6、能流程圖如下：輸入變量x的值Nq不空Ysum+=q->coef*pow(x,q->expn)q=q->nextreturn sum;完成多項式計算輸出多項式的計算開始從鍵盤輸入項數(shù)mm<=0返回空定義存儲多項式數(shù)據(jù)類型term動態(tài)分配空間完成建立多項式降次排序輸出YN 多項式的建立 按指數(shù)排序?qū)個有序多項式用數(shù)組G i保存輸入多項式個數(shù)k輸出開始開始定義存儲和鏈表h動態(tài)分配空間Pb=Pb->coef*(-1)兩多項式相加輸出Pb？Pb=pb->nextYN 多個多項式排序 多項式相減 定義存儲和鏈表h動態(tài)分配空間Pa&&Pb?C=a->

7、;expn - b->expnh=UNLL返回系統(tǒng)C>=1C>=0h=Pb Pb = Pb->next;h=Pa Pa = Pa->next;sum = Pa->coef + Pb->coef;sum=0Pa->coef = sum;h=Pa;Pa=Pa->next;Pa = Pa->next;Pa=0Pb=0h->next = Pa;h->next = Pa;h = h->next;Return hNYNYNYNYYNYYNN輸出開始完成多項式相加調(diào)用函數(shù)查找同類項同類項系數(shù)相加進行合并合并后檢查a b掃描是否完整

8、輸出多項式q流程圖：putchar(1)printf(“x%d”,q->expn)Putchar(x)q->expn=0p=p->nextputchar (0);開始printf(“%g”,q->coef)q!=UNLLq->coef!=1q->expn=1q->coef>=0q!=UNLLPutchar(+)退出 N Y N Y Y N Y N Y N Y N多項式輸出主要是對已建立的多項式按鏈表從頭到尾掃描指數(shù)跟系數(shù)進行多重判斷，根據(jù)指數(shù)和系數(shù)輸出相應的數(shù)值與符號，直到多項式輸出完成。四、調(diào)試分析程序的調(diào)試是程序順利完成中非常關鍵的一步。通過

9、程序的調(diào)試分析可以解決程序的運行錯誤也可以對程序的性能進行分析。這個多項式運算問題研究的程序最重要的就是看輸出的鏈表是否正確，是否帶有空結(jié)點，運行結(jié)果輸出是否正確。決定程序成功與否的第一步是定義的CreatPolyn()函數(shù)操作是否正確，如果這一步中出現(xiàn)錯誤，那么接下來的操作可以說是錯上加錯。在調(diào)試的時候可以在程序中加入刪除、釋放空結(jié)點操作，此操作是由Delet()與free()函數(shù)完成的，若輸出的多項式?jīng)]有空結(jié)點說明函數(shù)正確，可以繼續(xù)向下進行。接下來就是函數(shù)相加，控制此操作的關鍵是一個A ()函數(shù)，其中調(diào)用APolyn（）函數(shù)是決定成功與否的關鍵，而函數(shù)的相減正是相加一個負數(shù)，將減數(shù)多項式的

10、coef變?yōu)樨撝当銓崿F(xiàn)了多項式的相減?？梢韵仍诒旧蠈懗鰞蓚€正確的簡單的多項式，使其具有相加后出現(xiàn)空結(jié)點的特點，然后變換循環(huán)變量的范圍，當輸出吻合時則說明操作正確。對于根據(jù)輸入的多項式及變量的值進行計算，控制此操作的關鍵是如何計算多項式中多次方的值，此操作關鍵是一個C()函數(shù)，調(diào)用pow()函數(shù)來實現(xiàn)計算次方的功能，其中sum值的計算是否正確起關鍵作用。而對多個輸入的表達式按照指數(shù)從大到小排序輸出，這個主要是用到了一個trem型數(shù)組對各已按指數(shù)排序好的多項式保存，然后對數(shù)組中的每個多項式的第一個p->expn值利用枚舉排序法進行比較將多項式排序。各個關鍵部分都已檢查完畢，剩下的就是對程序的

11、進一步細心的完善化、美觀化、清晰化直到滿足要求。下面我們分析一下程序的性能。在主函數(shù)中，首先調(diào)用構造單鏈表函數(shù)CreatePoly()，在這個函數(shù)中需要通過一個for循環(huán)為每個結(jié)點分配存儲空間，變換節(jié)點的next域，時間復雜度為O（n）。接下來執(zhí)行selsort()函數(shù)對多項式進行按指數(shù)排序，其中一個雙重for循環(huán)，在內(nèi)部的for循環(huán)中是對相鄰結(jié)點指數(shù)大小比較進行操作，所以每個結(jié)點的操作都需要m次，共n個結(jié)點，則需要mn次操作，時間復雜度為O（nn）。其后的for循環(huán)是比較將指數(shù)相同的數(shù)進行合并，時間復雜度為O（n）。五、測試結(jié)果系統(tǒng)選擇界面如圖 6-1圖6-1測試按照指數(shù)降序排列輸出多項式

12、8*x1+9*x0+7*x2+6*x3 輸入數(shù)據(jù)為：1（enter）4（enter）8 1 9 0 7 2 6 3（enter）輸出結(jié)果為：6*x3+7*x2+8*x1+9測試結(jié)果如圖6-2圖6-2測試兩個多項式相加8*x1+9*x0+7*x2+6*x3; 0*x0+1*x3+5*x2；輸入數(shù)據(jù)為：2（enter）4（enter）8 1 9 0 7 2 6 3 （enter）3（enter）0 0 1 3 5 2（enter）輸出結(jié)果為：7x3+12x2+8x+9測試結(jié)果如圖6-3圖6-3輸入的多項式及變量的值計算結(jié)果測試測試多項式4x3+5x4+6x1+7x0 當x值為2.5時的值為279.

13、8125輸入數(shù)據(jù)為：4（enter） 4（enter）4 3 5 4 6 1 7 0（enter）2.5（enter）測試結(jié)果如圖6-4圖6-4測試對多個輸入的表達式按照指數(shù)從大到小排序輸出測試多項式8*x1+9*x0+7*x2+6*x3; 0*x0+1*x3+5*x2；4x3+5x4+6x1+7x0輸入數(shù)據(jù)為：5（enter） 3（enter） 4（enter） 8 1 9 0 7 2 6 3 （enter）3（enter） 0 0 1 3 5 2 （enter）4（enter） 4 3 5 4 6 1 7 0 （enter）輸出結(jié)果為：5x4+4x3+6x+7； 6*x3+7*x2+8*x

14、 +9；x3+5*x2數(shù)組測試結(jié)果如圖6-5圖6-5六、課程設計總結(jié)計算一元多項式加法，其結(jié)果取決于多項式的各項系數(shù)與指數(shù)，因此程序核心是處理兩個多項式的系數(shù)與指數(shù)。定義結(jié)構體將多項式的各項系數(shù)與指數(shù)存放，定義結(jié)構體類型鏈表為程序的循環(huán)控制提供了可能，利用對鏈表的運算來確定結(jié)果多項式的各項系數(shù)與次數(shù)，同理算出相應的冪數(shù)。鏈表是在計算機內(nèi)存中使用一組連續(xù)的存儲單元保存數(shù)據(jù)類型和名字相同的變量。就鏈表這種數(shù)據(jù)類型而言，在排列上采用的方法也是按序排放，先存放第一行，接著存放第二行，直到所有數(shù)據(jù)元素被存放。多項式采用的是鏈表形式，以犧牲一定的空間提高程序的運行速度和可行性。算法思想：采用鏈式結(jié)構存儲多

15、項式，用鏈表結(jié)構體的一個域標記多項式的次數(shù)，另一個域標記多項式的系數(shù)，程序中采用的是m表示最高次系數(shù)，進行加法運算時，標記系數(shù)域相加即為相加的對應系數(shù)，標記指數(shù)域相同則表示為同類項。鏈表的特性是在中間任意位置添加刪除元素的都非常的快，不需要移動其它的元素。鏈表顧名思義，要把各個元素鏈接起來才算撒。通常鏈表每一個元素都要保存一個指向下一個元素的指針（單鏈表）。本次課程設計，我查找過資料，請教過同學，以及不懈的努力，不僅培養(yǎng)了獨立思考、動手操作的能力，在各種其它能力上也都有了提高。更重要的是，在程序設計中，我學會了很多學習的方法，而這是日后最實用的，真的是受益匪淺。本學期的程序設計課程，我鍛煉了能

16、力，學到很多東西，比如思考問題的角度也會從多方面著手；對自己的專業(yè)也有自己的想法在和同學的交流過程中，互動學習，將知識融會貫通。通過這次課程設計，我對很多的函數(shù)有了新的認識，也學會了運用多種函數(shù)，我也明白了寫軟件的基本過程和基本方法。在程序的設計過程中遇到拉很多的困難，在程序一次一次的調(diào)試失敗下曾經(jīng)想過要放棄，我最后還是讓自己堅持啦下來，毫不畏懼困難，在同學的幫助與講解下我總算是順利的完成了程序的課程設計。在這幾天的編寫過程中我對語言有了更進一步的認識和了解，也感受到了編程給我?guī)淼目鞓放c充實，明白了想成為一個合格的甚至是優(yōu)秀的程序員，我還需要更多更難的鍛煉。所以我還要不斷地學習不斷地說活，不

17、斷地成長，為我的理想而奮斗。七、參考文獻1） 嚴蔚敏 吳偉民 數(shù)據(jù)結(jié)構(C語言版) 清華大學出版社.2006.2） 恰汗 合孜爾 C語言程序設計 中國鐵道出版社2009.3） 楊永斌 數(shù)據(jù)結(jié)構(理論與實踐). 天津科學技術出版社4） 百度資料八、附錄#include<stdlib.h>#include<stdio.h> #include<ctype.h> #include<iostream>#include<math.h>#define null 0#define W 10using namespace std;typedef str

18、uct term /項的表示，多項式的項作為LinkList的數(shù)據(jù)元素 float coef; /系數(shù) int expn; /指數(shù) struct term *next; term; int Empty(term *L) if(L->next!=null) return 1; return 0;void Delete(term * L,term * p) term * s,*q; s=L; q=L->next; while(p!=q) s=q; q=q->next; s->next=q->next; free(q); term* CreatPolyn(term *P

19、,int m) / 輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P if(m <= 0) return NULL; term *h = P = (term*)malloc(sizeof(term), *q; P->coef = 0.0; int i; printf("依次輸入%d個數(shù)（前一個為系數(shù)，后一個為指數(shù)）n",m*2); for (i = 1; i <= m; +i) / 依次輸入m個非零項 scanf("%f%d",&P->coef,&P->expn); if(P->coef) q =

20、P; /若該系數(shù)值不為0，則p數(shù)值插入鏈表qP = P->next = (term*)malloc(sizeof(term); q->next = NULL; free(P); return h; / CreatPolyn term* selsort(term *h) /將有序鏈表進行指數(shù)排列term *g, *p, *q; if(!h) return NULL; float f; int i, fini = 1; for(g = h;g->next&&fini;g = g->next) /確定排序需要掃描的次數(shù) fini = 0; for(p = h,

21、q = h->next;q;p = p->next,q = q->next) /相鄰的指數(shù)進行比較，一次循環(huán)將最小指數(shù)排到最后，若兩兩比較沒交換，則.if (p->expn < q->expn) /將鏈表中的元素按指數(shù)從高到低排列 f = p->coef;i = p->expn; p->coef = q->coef;p->expn = q->expn; q->coef = f;q->expn = i; fini = 1; for(g = h,p = g->next;p;) /比較將指數(shù)相同的數(shù)進行合并 i

22、f(g->expn=p->expn) g->coef += p->coef; g->next = p->next; /合并后跳過一個元素，并刪除該結(jié)點 q = p; p = p->next; free(q); else if(g->next) g = g->next; p = p->next; return h; void PrintfPoly(term *P) /輸出按指數(shù)從大到小排列后的一元多次式term *q = P; if(!q) putchar('0'); return; if(q->coef!=1)

23、printf("%g",q->coef); /%g用來輸出實數(shù)，它根據(jù)數(shù)值的大小，自動選f格式或e格式，且不輸出無意義的0 if(q->expn=1) putchar('X'); /若指數(shù)值大小為1，則指數(shù)省略 else if(q->expn) printf("X%d",q->expn); else if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d"

24、,q->expn); q = q->next; while (q) if(q->coef > =0) putchar('+'); if(q->coef!=1) printf("%g",q->coef); if(q->expn=1) putchar('X'); else if(q->expn) printf("X%d",q->expn); else if(!q->expn) putchar('1'); else if(q->expn=1) pu

25、tchar('X'); else printf("X%d",q->expn); q = q->next; int Compare(term *a, term *b) if (a->expn < b->expn) return -1; if (a->expn > b->expn) return 1; return 0; float C(term *c,float x) /計算輸入變量的多項式的值 float sum=0,a; int b; term *q=c; for(;q ;q=q->next) a=q-

26、>coef ;b=q->expn ; sum+=a*pow(x,b); return sum;term* APolyn(term *Pa, term *Pb) / 多項式加法：Pa = PaPb，利用兩個多項式的結(jié)點構成"和多項式"。 term *h, *qa = Pa, *qb = Pb, *p, *q; float sum; h = p = (term*)malloc(sizeof(term); p->next = NULL; while (qa && qb) / Pa和Pb均非空 switch (Compare(qa,qb) case

27、 -1: / 多項式PA中當前結(jié)點的指數(shù)值小 p->next = qb; p = qb; qb = qb->next; break; case 0: / 兩者的指數(shù)值相等 sum = qa->coef + qb->coef; if (sum != 0.0) / 修改多項式PA中當前結(jié)點的系數(shù)值 p->next = qa; qa->coef = sum; p = qa; qa = qa->next; else / 刪除多項式PA中當前結(jié)點 q = qa; qa = qa->next; free(q); q = qb; qb = qb->nex

28、t; free(q); break; case 1: / 多項式PB中當前結(jié)點的指數(shù)值小 p->next = qa; p = qa; qa = qa->next; break; / 結(jié)束switch / 結(jié)束while if (Pa) p->next = qa; / 鏈接Pa中剩余結(jié)點 if (Pb) p->next = qb; / 鏈接Pb中剩余結(jié)點 q = h; h = h->next; free(q); return h; / APolyn term* A(term *Pa, term *Pb) int n; printf("請輸入第二個一元多項式

29、的項數(shù): "); scanf("%d",&n); Pb = CreatPolyn(Pb,n); Pb = selsort(Pb); cout<<"兩個多項式相加結(jié)果為："PrintfPoly(Pa); if(Pb && Pb->coef>0) printf(" + "); PrintfPoly(Pb); Pa = APolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa

30、; term* BPolyn(term *Pa, term *Pb) / 多項式減法：Pa = Pa-Pb，利用兩個多項式的結(jié)點構成"差多項式"。 term *p = Pb; while(p) p->coef *= -1; p = p->next; return APolyn(Pa,Pb); / BPolyn term* B(term *Pa, term *Pb) int n; printf("請輸入第二個一元多項式的項數(shù): ");scanf("%d",&n); Pb = CreatPolyn(Pb,n); Pb

31、= selsort(Pb); cout<<"兩個多項式相減結(jié)果為："PrintfPoly(Pa); printf(" - "); putchar('(');PrintfPoly(Pb);putchar(')'); Pa = BPolyn(Pa,Pb); printf(" = "); Pa = selsort(Pa); PrintfPoly(Pa); return Pa; void main() term *M,*N; term *q;int i,j,n; float x,y; term *G

32、W;int k; f: puts("t= 一元多項式計算系統(tǒng)：="); printf("nttt1:按照指數(shù)降序排列輸出多項式nttt2:一元多項式的加法運算"); printf("nttt3:一元多項式的減法運算nttt4:輸入的多項式及變量的值計算結(jié)果"); puts("nttt5:對多個輸入的表達式按照指數(shù)從大到小排序輸出nttt0:退出系統(tǒng)"); puts("t="); printf("n請選擇您要進行的操作：");cin>>i;switch(i) cas

33、e 1:printf("nttt按照指數(shù)降序排列輸出多項式:n請輸入該一元多項式的項數(shù): "); scanf("%d",&n); M = CreatPolyn(M,n); M = selsort(M); cout<<"您輸入的多項式按指數(shù)降序排列為： "PrintfPoly(M);cout<<endl<<endl; goto f;case 2: printf("nttt一元多項式加法計算:n請輸入第一個一元多項式的項數(shù): "); scanf("%d",&n); M = CreatPolyn(M,n); M = selsort(M); M = A(M,N); cout<<endl<<endl;goto f; case 3: printf