數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-n元多項式乘法

1、-. z.數(shù)據(jù)構(gòu)造課程設(shè)計報告N元多項式乘法目錄 TOC o 1-3 h z u HYPERLINK l _Toc4231969201 課程設(shè)計內(nèi)容 PAGEREF _Toc423196920 h - 2 -HYPERLINK l _Toc4231969212 課程設(shè)計分析 PAGEREF _Toc423196921 h - 2 -HYPERLINK l _Toc4231969223 思路原理 PAGEREF _Toc423196922 h - 2 -HYPERLINK l _Toc4231969234 程序簡圖 PAGEREF _Toc423196923 h - 2 -HYPERLINK l

2、 _Toc4231969245 算法數(shù)據(jù)構(gòu)造描述 PAGEREF _Toc423196924 h - 2 -HYPERLINK l _Toc4231969256 程序清單 PAGEREF _Toc423196925 h - 2 -HYPERLINK l _Toc4231969266.1 單鏈表表示 PAGEREF _Toc423196926 h - 2 -HYPERLINK l _Toc4231969276.2 數(shù)組表示 PAGEREF _Toc423196927 h - 2 -HYPERLINK l _Toc4231969287 運行與調(diào)試分析 PAGEREF _Toc423196928 h

3、 - 2 -HYPERLINK l _Toc4231969298 收獲與體會 PAGEREF _Toc423196929 h - 2 -HYPERLINK l _Toc4231969309 參考文獻(xiàn) PAGEREF _Toc423196930 h - 2 -. z.1 課程設(shè)計內(nèi)容功能：完成兩個n元多項式作乘法，給出明確的等式形式。分步實施：1)初步完成總體設(shè)計，搭好框架，確定人機(jī)對話的界面，確定函數(shù)個數(shù)；2)完成最低要求：建立一個文件，實現(xiàn)兩個一元二次多項式作乘法。3)進(jìn)一步要求：實現(xiàn)三元二次多項式的乘法。有興趣的同學(xué)可以自己擴(kuò)大系統(tǒng)功能。2 課程設(shè)計分析本程序用的存儲方式是單鏈表，單鏈表在

4、C語言中是一種非常常見的構(gòu)造，而在C+中的實現(xiàn)卻又有不同，在一些地方更簡單，更嚴(yán)密。同時，由于C+的一些特點，使它具有C語言所不具有的平安化，所以本程序用C+。有了鏈表特定的數(shù)據(jù)類型Mulpoly，接下來就需要建立這個鏈表。這里定義了一個構(gòu)造函數(shù)CreatePoly來構(gòu)造鏈表。首先定義一個CreatePoly型的指針變量head作為頭結(jié)點，存儲多項式的信息項數(shù)，為head分配存儲空間建立一個頭結(jié)點并為其數(shù)據(jù)域賦值，分配存儲空間用c+語言中的malloc來實現(xiàn)；這時輸入多項式的項數(shù)num，把它賦值給head的coef域，e*p域賦值為1，此時再定義一個CreatePoly型的指針變量r指向hea

5、d頭結(jié)點。還要用類似的算法建立多項式的其它結(jié)點，剩余節(jié)點的插入用一個while循環(huán)來實現(xiàn)，while循環(huán)中的控制變量i從大于0的數(shù)n開場遞增，直到到達(dá)num，此時while循環(huán)完畢。While 循環(huán)的循環(huán)體由兩局部組成，第一局部是為指針變量s分配存儲空間和為其數(shù)據(jù)域賦值，分配存儲空間同樣用c+語言中的malloc來實現(xiàn)；第二局部是節(jié)點的指針域轉(zhuǎn)換過程，將r的指針域指向新生成的結(jié)點s，相當(dāng)于將生成結(jié)點依次用指針連接，然后將最后一個結(jié)點的指針域設(shè)置為NULL，具體代碼如下：MulPoly *CreatePoly() MulPoly *head,*r,*s; int m,n,num,i=1; hea

6、d=(MulPoly *)malloc(sizeof(MulPoly); cout請輸入多項式的項數(shù):num; head-coef=num; head-e*p=1; r=head; while(i=num) /n不為0時建立多項式鏈表 s=(MulPoly *)malloc(sizeof(MulPoly); cout輸入第i組系數(shù)和指數(shù):nm; s-e*p=m; s-coef=n; r-ne*t=s; r=s; i+; r-ne*t=null; return(head); 在處理多項式相乘的問題時，定義一個PolyMulti函數(shù)實現(xiàn)，需要再建立一個MulPoly型的鏈表存儲相乘之后的鏈表，定義

7、結(jié)果鏈表的系數(shù)等于鏈表P1的系數(shù)乘以鏈表P2的系數(shù)：(p-coef)=(p1-coef)*(p2-coef) 結(jié)果鏈表的指數(shù)等于鏈表P1的指數(shù)乘以鏈表P2的指數(shù)：(p-e*p)=(p1-e*p)+(p2-e*p)。在整理之后可能出現(xiàn)零結(jié)點，則就需要進(jìn)展判斷和刪除操作同時釋放零結(jié)點，這些操作是通過一個while循環(huán)來完成。具體代碼如下：while(p!=q) s=q; q=q-ne*t; s-ne*t=q-ne*t; free(q); 還需要定義一個輸出函數(shù)，在主函數(shù)中調(diào)用輸出兩個多項式相乘后的結(jié)果。程序的最終都是由主函數(shù)來實現(xiàn)。在主函數(shù)中通過對一些自定義函數(shù)的調(diào)用實現(xiàn)具體的操作。在此主函數(shù)調(diào)用

8、了一個構(gòu)建鏈表的函數(shù)CreatePoly、一個刪除空結(jié)點的函數(shù)Delete和輸出函數(shù)Print。在主函數(shù)的開場需要定義三個MulPoly型指針變量，分別用來存儲調(diào)用CreatePoly函數(shù)和PolyMulti函數(shù)生成的鏈表和結(jié)果鏈表。在構(gòu)建鏈表之前要給節(jié)點分配存儲空間，s=(MulPoly *)malloc(sizeof(MulPoly);這條語句便可完成此操作。此條語句運用了c+語言庫函數(shù)中的malloc函數(shù)，這個函數(shù)的作用是在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為sizeof(MulPoly)的內(nèi)存空間。調(diào)用構(gòu)建鏈表函數(shù)CreatePoly后鏈表Pl便構(gòu)建完成。接下來需要執(zhí)行m=PolyMult

9、i(p,q);語句，這條語句的目的是把多項式P1和P2相乘的結(jié)果多項式存儲在鏈表m當(dāng)中，然后執(zhí)行Print(m);語句顯示輸出。主函數(shù)的程序框架如下：int main() MulPoly *p,*q,*m; p=CreatePoly(); q=CreatePoly(); m=PolyMulti(p,q); Merge_Same(m); Print(m); system(pause); 程序的調(diào)試是程序順利完成中非常關(guān)鍵的一步。通過程序的調(diào)試分析可以解決程序的運行錯誤也可以對程序的性能進(jìn)展分析。這個多項式運算問題研究的程序最重要的就是看輸出的鏈表是否正確，是否帶有空結(jié)點，合并是否完全。決定程序成

10、功與否的第一步是定義的PolyMulti函數(shù)操作是否正確。如果這一步中出現(xiàn)錯誤，則接下來的操作可以說是錯上加錯。在調(diào)試的時候可以在程序中參加刪除、釋放空結(jié)點操作，此操作便是由Delete函數(shù)完成的，假設(shè)輸出的多項式?jīng)]有空結(jié)點說明函數(shù)正確，可以繼續(xù)向下進(jìn)展。接下來就是相乘后的合并同類項，控制此操作的關(guān)鍵是一個Merge_Same函數(shù)，調(diào)用Delete函數(shù)是決定成功與否的關(guān)鍵?？梢韵仍诒旧蠈懗鰞蓚€正確的簡單的多項式，使其具有相加后出現(xiàn)空結(jié)點的特點，然后變換循環(huán)變量的*圍，當(dāng)輸出吻合時則說明操作正確。各個關(guān)鍵局部都已檢查完畢，剩下的就是對程序的進(jìn)一步細(xì)心的完善直到滿足要求。下面分析一下程序的性能。在

11、主函數(shù)中，首先調(diào)用的是構(gòu)造單鏈表函數(shù)CreatePoly，在這個函數(shù)中需要通過一個for循環(huán)為每個結(jié)點分配存儲空間，變換節(jié)點的ne*t域，時間復(fù)雜度為On。接下來執(zhí)行一個雙重for循環(huán)，在內(nèi)部的for循環(huán)中是對結(jié)點的相加、相乘操作，因為是按著指針的方向就可以對結(jié)點進(jìn)展相加、相乘操作，所以每個結(jié)點的操作都需要m次，共n個結(jié)點，則需要 QUOTE 次操作，時間復(fù)雜度為O QUOTE 。3 思路原理先要設(shè)置兩個單鏈表，每個單鏈表中可寫入一個多項式。加法：取第兩個鏈表中最高項和另一鏈表各項比指數(shù)，假設(shè)不同則放在第三個空鏈表里作為第一項，假設(shè)一樣則系數(shù)相加指數(shù)不變，放在第三個空鏈表里作為第一項，并且要刪

12、除兩鏈表里此指數(shù)項。取第兩個鏈表中最高項和另一鏈表各項比指數(shù)，以此類推。乘法：取第一個鏈表第一項和第二鏈表的每一項相乘，系數(shù)相乘，指數(shù)相加，作為一個新鏈表。取第一個鏈表第二項和第二鏈表的每一項相乘最后再把每個新鏈表做加法。最后顯示答案。4 程序簡圖5 算法數(shù)據(jù)構(gòu)造描述定義單鏈表的抽象數(shù)據(jù)類型：ADT LinkList數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,3,，n=0數(shù)據(jù)關(guān)系：R=|ai,ai+1 D/線性表的單鏈表根本操作/LinkList InitList(void); 構(gòu)造一個空的線性表void DestroyList(LinkList *L);初始條件：線性表L已存在。操作

13、結(jié)果：銷毀線性表L。LinkList MakeEmpty(LinkList L)初始條件：線性表L已存在。操作結(jié)果：將線性表L重置為空表。int IsEmpty(LinkList L);初始條件：線性表L已存在。操作結(jié)果：判斷線性表是否為空表。int ListLength(LinkList L);初始條件：線性表L已存在。操作結(jié)果：返回線性表L結(jié)點的個數(shù)。LNode IsLast(LinkList L);初始條件：線性表L已存在。操作結(jié)果：返回線性表L的最后一個結(jié)點尾結(jié)點。LNode NewLNode(ElemType *);構(gòu)造一個數(shù)據(jù)域為*的新結(jié)點LNode FindPrefious(El

14、emType *, LinkList L);初始條件：線性表L已存在。操作結(jié)果：在線性表L中尋找值為*的結(jié)點，假設(shè)找到則返回該結(jié)點的前驅(qū)，否則返回NULL。void ListDelete(LNode Pre);初始條件：線性表L中結(jié)點P已找到。操作結(jié)果：刪除該結(jié)點。鏈表的結(jié)點構(gòu)造:datane*tdata域-存放結(jié)點值的數(shù)據(jù)域ne*t域-存放結(jié)點的直接后繼的地址位置的指針域鏈域此題定義系數(shù)和指數(shù)構(gòu)造如下：coefe*pne*t/線性表的單鏈表存儲構(gòu)造/Typedef struct Lnode ElemType data;/結(jié)點的數(shù)據(jù)域 Struct Lnode *ne*t;/結(jié)點的指針域Lno

15、de, *LinkList;/根本操作/InitArray(&A, n, bound1, ., boundn)操作結(jié)果：假設(shè)維數(shù) n 和各維長度合法則構(gòu)造相應(yīng)數(shù)組 A。DestroyArray(&A)初始條件：數(shù)組 A 已經(jīng)存在。操作結(jié)果：銷毀數(shù)組 A。Value(A, &e, inde*1, ., inde*n)初始條件：A 是 n 維數(shù)組，e 為元素變量， n 個下標(biāo)值。操作結(jié)果：假設(shè)各下標(biāo)不超界，則e賦值為所指定的A的元素值，并返回OK。Assign(&A, e, inde*1, ., inde*n)初始條件：A 是 n 維數(shù)組，e 為元素變量，n 個下標(biāo)值。操作結(jié)果：假設(shè)下標(biāo)不超界，則

16、將 e 的值賦給A中指定下標(biāo)的元素。 ADT Array6 程序清單6.1 單鏈表表示/*程序源代碼：*/#include #include #include #include#define null 0using namespace std;typedef struct term/項的表示，多項式的項作為LinkList的數(shù)據(jù)元素float coef; /系數(shù)int e*pn; /指數(shù)struct term *ne*t;term;int Empty(term *L)if (L-ne*t != null)return 1;return 0;term *CreatePoly()term *hea

17、d, *r, *s;int m, n, num, i = 1;head = (term *)malloc(sizeof(term);/建立一個頭結(jié)點cout 請輸入多項式的項數(shù): num;head-coef = num;head-e*pn = 1;r = head;while (i = num) /n不為0時建立多項式鏈表s = (term *)malloc(sizeof(term);/建立一個新結(jié)點cout 輸入第 i 組系數(shù)和指數(shù): n m;s-e*pn = m;s-coef = n;r-ne*t = s;r = s;i+;r-ne*t = null;return(head);term *

18、PolyMulti(term *f, term*g)term *p1, *p2, *p, *r, *head;head = (term *)malloc(sizeof(term);head-coef = null;head-e*pn = null;r = head;for (p1 = f-ne*t; p1 != null; p1 = p1-ne*t)for (p2 = g-ne*t; p2 != null; p2 = p2-ne*t)p = (term *)malloc(sizeof(term);(p-coef) = (p1-coef)*(p2-coef);(p-e*pn) = (p1-e*p

19、n) + (p2-e*pn);r-ne*t = p;r = p;r-ne*t = null;return head;void Delete(term * L, term * p)term * s, *q;s = L;q = L-ne*t;while (p != q)s = q;q = q-ne*t;s-ne*t = q-ne*t;free(q);void Print(term * L)term * p;cout 兩個多項式相乘的結(jié)果為： endl ne*t; p != null; p = p-ne*t)cout ( coef ) * e*pn +;cout b;elsecout ne*t; p

20、 != null; p = p-ne*t)for (q = p-ne*t; q != null; q = q-ne*t)if (p-e*pn = q-e*pn)(p-coef) = (p-coef) + (q-coef);Delete(f, q);if (p-coef = 0)Delete(f, p);break;term* CreatPolyn(term *P, int m)/ 輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P if (m coef = 0.0;int i;printf(依次輸入%d個數(shù)前一個為系數(shù)，后一個為指數(shù)n, m * 2);for (i = 1; i coef,

21、&P-e*pn);if (P-coef)q = P;P = P-ne*t = (term*)malloc(sizeof(term);q-ne*t = NULL;free(P);return h; / CreatPolyn term* selsort(term *h)term *g, *p, *q;if (!h) return NULL;float f;int i, fini = 1;for (g = h; g-ne*t&fini; g = g-ne*t)fini = 0;for (p = h, q = h-ne*t; q; p = p-ne*t, q = q-ne*t)if (p-e*pn e

22、*pn)f = p-coef; i = p-e*pn;p-coef = q-coef; p-e*pn = q-e*pn;q-coef = f; q-e*pn = i;fini = 1;for (g = h, p = g-ne*t; p;)if (g-e*pn = p-e*pn)g-coef += p-coef;g-ne*t = p-ne*t;q = p;p = p-ne*t;free(q);else if (g-ne*t)g = g-ne*t;p = p-ne*t;return h;void PrintfPoly(term *P)term *q = P;if (!q)putchar(0);re

23、turn;if (q-coef != 1)printf(%g, q-coef);if (q-e*pn = 1) putchar(*);else if (q-e*pn) printf(*%d, q-e*pn);else if (!q-e*pn) putchar(1);else if (q-e*pn = 1) putchar(*);else printf(*%d, q-e*pn);q = q-ne*t;while (q)if (q-coef 0) putchar(+);if (q-coef != 1)printf(%g, q-coef);if (q-e*pn = 1) putchar(*);els

24、e if (q-e*pn) printf(*%d, q-e*pn);else if (!q-e*pn) putchar(1);else if (q-e*pn = 1) putchar(*);else printf(*%d, q-e*pn);q = q-ne*t;int pare(term *a, term *b)if (a-e*pn e*pn) return -1;if (a-e*pn b-e*pn) return 1;return 0;term* APolyn(term *Pa, term *Pb)/ 多項式加法：Pa = PaPb，利用兩個多項式的結(jié)點構(gòu)成和多項式。term *h, *qa

25、 = Pa, *qb = Pb, *p, *q;float sum;h = p = (term*)malloc(sizeof(term);p-ne*t = NULL;while (qa & qb)/ Pa和Pb均非空switch (pare(qa, qb)case -1: / 多項式PA中當(dāng)前結(jié)點的指數(shù)值小p-ne*t = qb;p = qb;qb = qb-ne*t;break;case 0: / 兩者的指數(shù)值相等sum = qa-coef + qb-coef;if (sum != 0.0)/ 修改多項式PA中當(dāng)前結(jié)點的系數(shù)值p-ne*t = qa;qa-coef = sum;p = qa;

26、qa = qa-ne*t;else/ 刪除多項式PA中當(dāng)前結(jié)點q = qa;qa = qa-ne*t;free(q);q = qb;qb = qb-ne*t;free(q);break;case 1: / 多項式PB中當(dāng)前結(jié)點的指數(shù)值小p-ne*t = qa;p = qa;qa = qa-ne*t;break; / switch / while if (Pa) p-ne*t = qa; / Pa中剩余結(jié)點if (Pb) p-ne*t = qb; / Pb中剩余結(jié)點q = h;h = h-ne*t;free(q);return h; / APolyn term* A(term *Pa, term

27、 *Pb)int n;puts(輸入第二個一元多項式的項數(shù));scanf(%d, &n);Pb = CreatPolyn(Pb, n);Pb = selsort(Pb);PrintfPoly(Pa);if (Pb & Pb-coef0) printf( + );PrintfPoly(Pb);Pa = APolyn(Pa, Pb);printf( = );Pa = selsort(Pa);PrintfPoly(Pa);return Pa;term* BPolyn(term *Pa, term *Pb)/ 多項式減法：Pa = Pa-Pb，利用兩個多項式的結(jié)點構(gòu)成差多項式。term *p = Pb

28、;while (p)p-coef *= -1;p = p-ne*t;return APolyn(Pa, Pb); / BPolyn term* B(term *Pa, term *Pb)int n;puts(輸入第二個一元多項式的項數(shù));scanf(%d, &n);Pb = CreatPolyn(Pb, n);Pb = selsort(Pb);PrintfPoly(Pa);printf( - );putchar(); PrintfPoly(Pb); putchar();Pa = BPolyn(Pa, Pb);printf( = );Pa = selsort(Pa);PrintfPoly(Pa)

29、;return Pa;int main()term *M=NULL, *N=NULL;term *p, *q, *m;char s2;int i, n;f: puts(n1:加n2:乘n3:下一步);cin i;switch (i)case 1:puts(一元多項式計算:n輸入第一個一元多項式的項數(shù));scanf(%d, &n);M = CreatPolyn(M, n);M = selsort(M);PrintfPoly(M);M = A(M, N);goto f;case 2:p = CreatePoly();q = CreatePoly();m = PolyMulti(p, q);Merg

30、e_Same(m);Print(m);goto f;case 3:break;default:puts(輸入有誤,請重新輸入!);6.2 數(shù)組表示/*程序源代碼：*/#include stdio.h#define N 100 /宏定義，為多項式的系數(shù)數(shù)組開辟空間static int k = 1;/記錄多項式的個數(shù)void input(float a, int na)/多項式a的系數(shù)輸入，其中na為次數(shù)int i;printf(請輸入多項式P%d(*)的各項系數(shù)數(shù)(從高次項到低次項，中間缺項則為0):n, k);for (i = 0; i = na; i+)/輸入各項系數(shù)scanf(%f, &a

31、i);while (a0 = 0)/首項系數(shù)不為0printf(首項系數(shù)不能為0，請重新輸入首項系數(shù)：);scanf(%f, &a0);printf(P%d(*)=%0.2f*%d, k, a0, na);for (i = 1; ina; i+)/打印輸入的多項式if (ai != 0)printf(+%0.2f*%d, ai, na - i);if (ana != 0)printf(+%0.2f, ana);printf(n);k+;/自增，記錄下個多項式void mul(float a, float b, int na, int nb)/系數(shù)相乘int n, i, j;float cN;/

32、記錄乘積的系數(shù)n = na + nb;/乘積的最高系數(shù)for (i = 0; i = n; i+)/乘積系數(shù)初始化為0ci = 0;for (i = 0; i = na; i+)for (j = 0; j = nb; j+)ci + j += ai * bj;/對應(yīng)一樣次數(shù)的系數(shù)相加printf(乘積P(*)=%0.2f*%d, c0, n);for (i = 1; in; i+)/打印輸入的多項式if (ai != 0)printf(+%0.2f*%d, ci, n - i);if (an != 0)printf(+%0.2f, an);printf(n);void main()float AN, BN;/開辟兩個數(shù)組，記錄多項式的值int n1, n2;printf(請輸入多項式P%d(*)的次數(shù)：, k);scanf(%d, &n1);input(