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

1、池 州 學(xué) 院CHIZHOU COLLEGE 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告學(xué) 號： 57 54 39 37 20 25 27 姓 名： 周田 張永鵬 武警 溫凱僑 李坤 米昌華 阮健健 班 級： 10計算機科學(xué)與技術(shù)（2）班 指導(dǎo)教師： 成 績： 數(shù)學(xué)與計算機科學(xué)系一、 課程設(shè)計基本情況1、設(shè)計名稱 一元多項式計算2、主要功能能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結(jié)果輸出；3、設(shè)計平臺 電腦、Visual c+ 6.0二、 系統(tǒng)設(shè)計1、算法思想 根據(jù)一元多項式相加的運算規(guī)則：對于兩個一元多項式中所有指數(shù)相同的項，對應(yīng)指數(shù)相加（減），若其和（差）不為零，則構(gòu)成“和（差

2、）多項式”中的一項；對于兩個一元多項式中所有指數(shù)不相同的項，則分別寫到“和（差）多項式”中去。 因為多項式指數(shù)最高項以及項數(shù)是不確定的，因此采用線性鏈表的存儲結(jié)構(gòu)便于實現(xiàn)一元多項式的運算。為了節(jié)省空間，我采用兩個鏈表分別存放多項式a和多項式b，對于最后計算所得的多項式則利用多項式a進行存儲。主要用到了單鏈表的插入和刪除操作。(1) 一元多項式加法運算它從兩個多項式的頭部開始，兩個多項式的某一項都不為空時，如果指數(shù)相等的話，系數(shù)就應(yīng)該相加；相加的和不為零的話，用頭插法建立一個新的節(jié)點。P的指數(shù)小于q的指數(shù)的話就應(yīng)該復(fù)制q的節(jié)點到多項式中。P的指數(shù)大于q的指數(shù)的話，就應(yīng)該復(fù)制p節(jié)點到多項式中。當(dāng)?shù)?/p>

3、二個多項式空，第一個多項式不為空時，將第一個多項式用新節(jié)點產(chǎn)生。當(dāng)?shù)谝粋€多項式空，第二個多項式不為空時，將第二個多項式用新節(jié)點產(chǎn)生。(2) 一元多項式的減法運算 它從兩個多項式的頭部開始，兩個多項式的某一項都不為空時，如果指數(shù)相等的話，系數(shù)就相減；相加的和不為零的話，用頭插法建立一個新的節(jié)點。p的指數(shù)小于q的指數(shù)的話，就應(yīng)該復(fù)制q的節(jié)點到多項式中。P的指數(shù)大于q的指數(shù)的話就應(yīng)該復(fù)制p的節(jié)點到多項式中，并且建立的節(jié)點的系數(shù)為原來的相反數(shù)；當(dāng)?shù)诙€多項式空，第一個多項式不為空時，將第一個多項式用新節(jié)點產(chǎn)生。當(dāng)?shù)谝粋€多項式空，第二個多項式不為空時，將第二個多項式用新節(jié)點產(chǎn)生，并且建立的節(jié)點的系數(shù)為原

4、來的相反數(shù)。2、概要設(shè)計(1)主函數(shù)流程圖：（注：a代表第一個一元二次方程，b代表第二個一元二次方程）開 始 定義結(jié)構(gòu)體定義函數(shù)類型及名稱 構(gòu)造指數(shù)比較函數(shù) 排列順序(降序） 用單鏈接儲存a,b項目的系數(shù)和指數(shù) 開 始 進 行 加 減 法 運 算 輸 出 構(gòu) 造 出 的 多 項 式指數(shù)不同 輸出多項式，求項數(shù) 創(chuàng)建并初始化多項式鏈表 輸 入 系 數(shù) 和 指 數(shù) 指數(shù)相同合并同類項 按指數(shù)排序 結(jié) 束 將 單 鏈 表 的 節(jié) 點 釋 放，使 已 建 立 的 多 項 式 銷 毀a項的指數(shù)值=b項的指數(shù)值 選 擇 語 句a項指數(shù)值<b項指數(shù)值 輸 出 計 算 后 的 多 項 式摘取b的指數(shù)值到

5、“和多項式” 按指數(shù)值按降序排列摘取a指數(shù)值到“和多項式” 釋放a和b的結(jié)點將a和b的系數(shù)相加(減) a項指數(shù)值>b項指數(shù)值 (2)一元多項式計算算法用類C語言表示： Typedef struct00 /項的表示，多項式的項作為LinkList的數(shù)據(jù)元素Float coef； /細數(shù)Int expn；/指數(shù)term，ElemType；/兩個類型名：term用于本ADT，ElemType為LinkList的數(shù)據(jù)對象名Typedef LinkList polynomial： /用帶表頭的節(jié)點的有序鏈表表示多項式/基本操作的函數(shù)原型說明Void CreatePolyn（polynomail&a

6、mp;P）；/輸入n的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P 銷毀一元多項式PVoid DestroyPolyn（polynomailP）；銷毀一元多項式PvoidPrintPoly（polynomail P）；/打印輸入一元多項式PIntPolynLength（polynnomail P);/返回一元多項式P中的項數(shù)void CreatPolyn（polynomail&Pa.polunomail&Pb);/完成多項式相加運算，即:Pa=Pa+Pb,并賢惠一元多項式PbvoidSubtractPolyn（polunomail&Papolunomail&Pb）

7、；/完成多項式相減運算，即：Pa=Pa-Pb，并銷毀一元多項式Pb/基本操作的算法描述Int cmp(tem a，temp b）；/依a的指數(shù)值<（或=）（或>b的住數(shù)值，分別返回-1、0和+1Void CreatePolyn（polynomail&P,int m)/輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表PInitList（P）；h=GetHead（P）；E.coef=0.0；e.expn=-1；SerCurElem（h，e）；/設(shè)置頭結(jié)點的數(shù)據(jù)元素For （i=1；i<=m；+i）/依次輸入m個非零項Scanf（e.coef，e.epn）；If（！Loc

8、ateElem（P，e，q，（*cmp）（）/當(dāng)前鏈表中不存在該指數(shù)項If(MakeNode（s，e）InsFirst（q，s）；/生成節(jié)點并插入鏈表/CreatPolun三、 詳細設(shè)計1、算法實現(xiàn)(1) 輸入一元多項式函數(shù)：void shuchu(pnode *head) pnode *p; int one_time=1; p=head; while(p!=NULL) /*如果不為空*/ if(one_time=1) if(p->zhishu=0) /*如果指數(shù)為0的話，直接輸出系數(shù)*/ printf("%5.2f",p->xishu); /*如果系數(shù)是正的話

9、前面就要加+號*/ else if(p->xishu=1|p->xishu=-1) printf("X%d",p->zhishu); /*如果系數(shù)是1的話就直接輸出+x*/ /*如果系數(shù)是-1的話就直接輸出-x號*/ else if(p->xishu>0) /*如果系數(shù)是大于0的話就輸出+系數(shù)x指數(shù)的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系數(shù)是小于0的話就輸出系數(shù)x指數(shù)的形式*/ printf("

10、;%5.2fX%d",p->xishu,p->zhishu); one_time=0; else if(p->zhishu=0) /*如果指數(shù)為0的話，直接輸出系數(shù)*/ if(p->xishu>0) printf("+%5.2f",p->xishu); /*如果系數(shù)是正的話前面就要加+號*/ else if(p->xishu=1) /*如果系數(shù)是1的話就直接輸出+x號*/ printf("+X%d",p->zhishu); else if(p->xishu=-1) /*如果系數(shù)是-1的話就直

11、接輸出-x號*/ printf("X%d",p->zhishu); else if(p->xishu>0) /*如果系數(shù)是大于0的話就輸出+系數(shù)x指數(shù)的形式*/ printf("+%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系數(shù)是小于0的話就輸出系數(shù)x指數(shù)的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); p=p->next; /*指向下一個指針*/ printf(&quo

12、t;n"); (2) 加法函數(shù)/*兩個多項式的加法運算*/ pnode * add(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; /*headc為頭指針，r,s為臨時指針，p指向第1個多項式并向右移動，q指向第2個多項式并向右移動*/ float x; /*x為系數(shù)的求和*/ p=heada; /*指向第一個多項式的頭*/ q=headb; /*指向第二個多項式的頭*/ headc=(pnode *)malloc(sizeof(pnode); /*開辟空間*/ r=headc; while(p!=NULL&&

13、q!=NULL) /*2個多項式的某一項都不為空時*/ if(p->zhishu=q->zhishu) /*指數(shù)相等的話*/ x=p->xishu+q->xishu; /*系數(shù)就應(yīng)該相加*/ if(x!=0) /*相加的和不為0的話*/ s=(pnode *)malloc(sizeof(pnode); /*用頭插法建立一個新的節(jié)點*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2個多項式都向右移*/ else if(p->zhi

14、shu<q->zhishu) /*p的系數(shù)小于q的系數(shù)的話，就應(yīng)該復(fù)制q節(jié)點到多項式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q向右移動*/ else/*p的系數(shù)大于q的系數(shù)的話，就應(yīng)該復(fù)制p節(jié)點到多項式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu;

15、r->next=s; r=s; p=p->next; /*p向右移動*/ /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ while(p!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ while(q!=NULL) s=(pnode *)malloc(sizeof(pnode);

16、s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一個頭沒有用到*/ return headc; /*返回頭接點*/ (3) 減法函數(shù)/*兩個多項式的加法運算*/ pnode * add(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; /*headc為頭指針，r,s為臨時指針，p指向第1個多項式并向右移動，q指向第2

17、個多項式并向右移動*/ float x; /*x為系數(shù)的求和*/ p=heada; /*指向第一個多項式的頭*/ q=headb; /*指向第二個多項式的頭*/ headc=(pnode *)malloc(sizeof(pnode); /*開辟空間*/ r=headc; while(p!=NULL&&q!=NULL) /*2個多項式的某一項都不為空時*/ if(p->zhishu=q->zhishu) /*指數(shù)相等的話*/ x=p->xishu+q->xishu; /*系數(shù)就應(yīng)該相加*/ if(x!=0) /*相加的和不為0的話*/ s=(pnode *

18、)malloc(sizeof(pnode); /*用頭插法建立一個新的節(jié)點*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2個多項式都向右移*/ else if(p->zhishu<q->zhishu) /*p的系數(shù)小于q的系數(shù)的話，就應(yīng)該復(fù)制q節(jié)點到多項式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r-&g

19、t;next=s; r=s; q=q->next; /*q向右移動*/ else/*p的系數(shù)大于q的系數(shù)的話，就應(yīng)該復(fù)制p節(jié)點到多項式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p向右移動*/ /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ while(p!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=

20、p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ while(q!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一個頭沒

21、有用到*/ return headc; /*返回頭接點*/ 2、 程序代碼/*一元多項式計算*/*程序功能：能夠按照指數(shù)降序排列建立并輸出多項式；能夠完成兩個多項式的相加、相減，并將結(jié)果輸出；*/*提示：輸入完一元多項式之后，輸入“0 0”結(jié)束本一元多項式的輸入*/*注意：系數(shù)只精確到百分位，最大系數(shù)只能為999.99,指數(shù)為整數(shù).如果需要輸入更大的系數(shù)，可以對程序中5.2%f進行相應(yīng)的修改*/#include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<conio.h> /*建

22、立結(jié)構(gòu)體*/ typedef struct pnode float xishu; /*系數(shù) */ int zhishu; /*指數(shù) */ struct pnode *next; /*下一個指針*/ pnode; /*用頭插法生成一個多項式，系數(shù)和指數(shù)輸入0時退出輸入*/ pnode * creat() int m; float n; pnode *head,*rear,*s; /*head為頭指針，rear和s為臨時指針*/ head=(pnode *)malloc(sizeof(pnode); rear=head; /*指向頭*/ scanf("%f",&n);

23、/*系數(shù)*/scanf("%d",&m); /*輸入指數(shù)*/while(n!=0) /*輸入0退出*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=n; s->zhishu=m; s->next=NULL; rear->next=s; /*頭插法*/ rear=s; scanf("%f",&n); /*輸入系數(shù)*/ scanf("%d",&m); /*輸入指數(shù)*/ head=head->next; /*第一個頭沒有用到*/ return he

24、ad; /*調(diào)整多項式*/ void tiaozhen(pnode *head) pnode *p,*q,*t; float temp; p=head; while(p!=NULL) q=p; t=q->next; while(t!=NULL) if(t->zhishu>q->zhishu) q=t; t=t->next; temp=p->xishu;p->xishu=q->xishu;q->xishu=temp; temp=p->zhishu;p->zhishu=q->zhishu;q->zhishu=temp;

25、p=p->next; /*顯示一個多項式*/ void shuchu(pnode *head) pnode *p; int one_time=1; p=head; while(p!=NULL) /*如果不為空*/ if(one_time=1) if(p->zhishu=0) /*如果指數(shù)為0的話，直接輸出系數(shù)*/ printf("%5.2f",p->xishu); /*如果系數(shù)是正的話前面就要加+號*/ else if(p->xishu=1|p->xishu=-1) printf("X%d",p->zhishu); /

26、*如果系數(shù)是1的話就直接輸出+x*/ /*如果系數(shù)是-1的話就直接輸出-x號*/ else if(p->xishu>0) /*如果系數(shù)是大于0的話就輸出+系數(shù)x指數(shù)的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系數(shù)是小于0的話就輸出系數(shù)x指數(shù)的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); one_time=0; else if(p->zhishu=0) /*如果指數(shù)為0

27、的話，直接輸出系數(shù)*/ if(p->xishu>0) printf("+%5.2f",p->xishu); /*如果系數(shù)是正的話前面就要加+號*/ else if(p->xishu=1) /*如果系數(shù)是1的話就直接輸出+x號*/ printf("+X%d",p->zhishu); else if(p->xishu=-1) /*如果系數(shù)是-1的話就直接輸出-x號*/ printf("X%d",p->zhishu); else if(p->xishu>0) /*如果系數(shù)是大于0的話就輸

28、出+系數(shù)x指數(shù)的形式*/ printf("+%5.2fX%d",p->xishu,p->zhishu); else if(p->xishu<0) /*如果系數(shù)是小于0的話就輸出系數(shù)x指數(shù)的形式*/ printf("%5.2fX%d",p->xishu,p->zhishu); p=p->next; /*指向下一個指針*/ printf("n"); /*兩個多項式的加法運算*/ pnode * add(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s

29、,*r; /*headc為頭指針，r,s為臨時指針，p指向第1個多項式并向右移動，q指向第2個多項式并向右移動*/ float x; /*x為系數(shù)的求和*/ p=heada; /*指向第一個多項式的頭*/ q=headb; /*指向第二個多項式的頭*/ headc=(pnode *)malloc(sizeof(pnode); /*開辟空間*/ r=headc; while(p!=NULL&&q!=NULL) /*2個多項式的某一項都不為空時*/ if(p->zhishu=q->zhishu) /*指數(shù)相等的話*/ x=p->xishu+q->xishu;

30、 /*系數(shù)就應(yīng)該相加*/ if(x!=0) /*相加的和不為0的話*/ s=(pnode *)malloc(sizeof(pnode); /*用頭插法建立一個新的節(jié)點*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2個多項式都向右移*/ else if(p->zhishu<q->zhishu) /*p的系數(shù)小于q的系數(shù)的話，就應(yīng)該復(fù)制q節(jié)點到多項式中*/ s=(pnode *)malloc(sizeof(pnode); s->xish

31、u=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; /*q向右移動*/ else/*p的系數(shù)大于q的系數(shù)的話，就應(yīng)該復(fù)制p節(jié)點到多項式中*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*p向右移動*/ /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ while(p!=NULL)

32、 s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ while(q!=NULL) s=(pnode *)malloc(sizeof(pnode); s->xishu=q->xishu; s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next

33、=NULL; /*最后指向空*/ headc=headc->next; /*第一個頭沒有用到*/ return headc; /*返回頭接點*/ /*兩個多項式的減法運算*/ pnode * sub(pnode *heada,pnode *headb) pnode *headc,*p,*q,*s,*r; float x; /*x為系數(shù)相減*/ p=heada; /*指向第一個多項式的頭*/ q=headb; /*指向第二個多項式的頭*/ headc=(pnode *)malloc(sizeof(pnode); /*開辟空間*/ r=headc; while(p!=NULL&&am

34、p;q!=NULL) /*兩個多項式的某一項都不為空時*/ if(p->zhishu=q->zhishu) /*指數(shù)相等的話*/ x=p->xishu-q->xishu; /*系數(shù)相減*/ if(x!=0) /*相減的差不為0的話*/ s=(pnode *)malloc(sizeof(pnode); /*用頭插法建立一個新的節(jié)點*/ s->xishu=x; s->zhishu=p->zhishu; r->next=s; r=s; q=q->next;p=p->next; /*2個多項式都向右移*/ else if(p->zhis

35、hu<q->zhishu) /*p的系數(shù)小于q的系數(shù)的話*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=-q->xishu; /*建立的節(jié)點的系數(shù)為原來的相反數(shù)*/ s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; else s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; /

36、*p向右移動*/ while(p!=NULL) /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第一個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=p->xishu; s->zhishu=p->zhishu; r->next=s; r=s; p=p->next; while(q!=NULL) /*當(dāng)?shù)?個多項式空，第1個數(shù)不為空時，將第2個數(shù)剩下的全用新節(jié)點產(chǎn)生*/ s=(pnode *)malloc(sizeof(pnode); s->xishu=-q->xishu; /*建立的節(jié)點的

37、系數(shù)為原來的相反數(shù)*/ s->zhishu=q->zhishu; r->next=s; r=s; q=q->next; r->next=NULL; /*最后指向空*/ headc=headc->next; /*第一個頭沒有用到*/ return headc; /*返回頭接點*/ void add_main() pnode * a,*b,*c; printf("n輸入第一個一元多項式:n系數(shù) 指數(shù)n"); a=creat(); tiaozhen(a); printf("n輸入第二個一元多項式:n系數(shù) 指數(shù)n"); b=creat(); tiaozhen(b); c=add(a,b); printf("第一個一元多項式如下:");shuchu(a); printf("第二個一元多項式如下:");shuchu(b); printf("兩式相加如下:");shuchu(c); void sub_main() pnode * a,*b,*c; p