1、目錄1.緒論21.1 前言21.2 問(wèn)題的提出22.課程設(shè)計(jì)目的33.需求分析43.1 功能分析43.2 設(shè)計(jì)思路44.概要設(shè)計(jì)5數(shù)據(jù)結(jié)構(gòu)的選用5多項(xiàng)式的輸入5主函數(shù)和其它函數(shù)55.流程圖設(shè)計(jì)6函數(shù)調(diào)用關(guān)系6程序流程圖76.程序代碼87.調(diào)試運(yùn)行158.總結(jié)17參考文獻(xiàn)18 摘要在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象數(shù)據(jù)元素以及它們之間的關(guān)系和運(yùn)算等的學(xué)科，而且確保經(jīng)過(guò)這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。在許多類型的程序的設(shè)計(jì)中，數(shù)據(jù)結(jié)構(gòu)的選擇是一個(gè)根本的設(shè)計(jì)考慮因素。許多大型系統(tǒng)的構(gòu)造經(jīng)驗(yàn)說(shuō)明，系統(tǒng)實(shí)現(xiàn)的困難程度和系統(tǒng)構(gòu)造的質(zhì)量都嚴(yán)重的依賴于是

2、否選擇了最優(yōu)的數(shù)據(jù)結(jié)構(gòu)。許多時(shí)候，確定了數(shù)據(jù)結(jié)構(gòu)后，算法就容易得到了。有些時(shí)候事情也會(huì)反過(guò)來(lái)，我們根據(jù)特定算法來(lái)選擇數(shù)據(jù)結(jié)構(gòu)與之適應(yīng)。不管哪種情況，選擇適宜的數(shù)據(jù)結(jié)構(gòu)都是非常重要的。選擇了數(shù)據(jù)結(jié)構(gòu)，算法也隨之確定，是數(shù)據(jù)而不是算法是系統(tǒng)構(gòu)造的關(guān)鍵因素。這種洞見(jiàn)導(dǎo)致了許多種軟件設(shè)計(jì)方法和程序設(shè)計(jì)語(yǔ)言的出現(xiàn)，面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言就是其中之一。經(jīng)過(guò)一學(xué)期的學(xué)習(xí)我對(duì)數(shù)據(jù)結(jié)構(gòu)的知識(shí)有所了解，運(yùn)用我所學(xué)的知識(shí)來(lái)完成這個(gè)課程設(shè)計(jì)。采用C語(yǔ)言編寫(xiě)，在對(duì)于多項(xiàng)式的存儲(chǔ)和計(jì)算操作中大量依賴于指針和結(jié)構(gòu)體。通過(guò)尾插法建立鏈表，指數(shù)的比擬來(lái)實(shí)現(xiàn)結(jié)點(diǎn)元素的相加減。關(guān)鍵字 數(shù)據(jù)結(jié)構(gòu) 多項(xiàng)式 鏈表 指針 結(jié)構(gòu)體 1.1

3、前言 算機(jī)的應(yīng)用已滲透到社會(huì)的各個(gè)領(lǐng)域，正在改變著人們的工作、學(xué)習(xí)和生活的方式，推動(dòng)著社會(huì)的開(kāi)展。歸納起來(lái)可分為以下幾個(gè)方面：如科學(xué)計(jì)算(數(shù)值計(jì)算)、數(shù)據(jù)處理(信息處理)、自動(dòng)控制、計(jì)算機(jī)輔助、人工智能、多媒體應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)本系統(tǒng)用C語(yǔ)言作為程序語(yǔ)言，設(shè)計(jì)出的系統(tǒng)功能完善，操作方便靈活。1.2 問(wèn)題的提出 一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)數(shù)器根本功能要求：(1)輸入并建立多項(xiàng)式(2)輸出多項(xiàng)式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2cn，en，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci，ei分別為第i項(xiàng)的系數(shù)和指數(shù)。序列按指數(shù)降序排列。(3)多項(xiàng)式a和b相加，建立多項(xiàng)式a+b，輸出相加的多項(xiàng)式。(4)多項(xiàng)式a和

4、b相減，建立多項(xiàng)式a-b，輸出相減的多項(xiàng)式。用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。使我們進(jìn)一步理解和掌握課堂上所學(xué)各種根本抽象數(shù)據(jù)類型的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)算法，以及它們?cè)诔绦蛑械氖褂梅椒āＪ刮覀冋莆哲浖O(shè)計(jì)的根本內(nèi)容和設(shè)計(jì)方法，并培養(yǎng)學(xué)生進(jìn)行標(biāo)準(zhǔn)化軟件設(shè)計(jì)的能力。使我們掌握使用各種計(jì)算機(jī)資料和有關(guān)參考資料，提高學(xué)生進(jìn)行程序設(shè)計(jì)的根本能力。熟練掌握數(shù)據(jù)結(jié)構(gòu)這門(mén)課程，掌握線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹(shù)和二叉樹(shù)以及圖等根本類型的數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用.進(jìn)一步熟悉抽象數(shù)據(jù)類型的定義和實(shí)現(xiàn)、如何利用數(shù)組的動(dòng)態(tài)分酚實(shí)現(xiàn)順序結(jié)構(gòu)、繼承的實(shí)現(xiàn)方式。學(xué)會(huì)分析研究計(jì)算機(jī)加工的數(shù)據(jù)結(jié)構(gòu)的特性，以便為應(yīng)用涉及的

5、數(shù)據(jù)選擇適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、想念結(jié)構(gòu)及基相應(yīng)的算法并初步掌握算法的時(shí)間分析和空間分析的技術(shù)。根本掌握程序設(shè)計(jì)的根本思路和方法。利用所學(xué)的根本知識(shí)和技能，解決簡(jiǎn)單的程序設(shè)計(jì)問(wèn)題各算法描述培養(yǎng)我們的數(shù)據(jù)抽象能力。3.1 功能分析 本程序要求輸入并建立多項(xiàng)式，能夠降冪顯示出多項(xiàng)式，實(shí)現(xiàn)多項(xiàng)式相加相減的計(jì)算問(wèn)題，輸出結(jié)果。3.2 設(shè)計(jì)思路采用鏈表的方式存儲(chǔ)鏈表，定義結(jié)點(diǎn)結(jié)構(gòu)體。運(yùn)用尾差法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個(gè)一元多項(xiàng)式a和b。為實(shí)現(xiàn)處理，社p、q分別指向單鏈表polya和polyb的當(dāng)前項(xiàng)，比擬p、q結(jié)點(diǎn)的指數(shù)項(xiàng)。 假設(shè)p->expn<q->e

6、xpn，那么結(jié)點(diǎn)p所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式中的一項(xiàng)，令指針p后移。 假設(shè)p->expn=q->expn，那么將兩個(gè)結(jié)點(diǎn)中的系數(shù)相加，當(dāng)和不為0時(shí)修改結(jié)點(diǎn)p的系數(shù)。 假設(shè)p->expn>q->expn，那么結(jié)點(diǎn)q所指的結(jié)點(diǎn)應(yīng)是“和多項(xiàng)式中的一項(xiàng)，將結(jié)點(diǎn)q插入在結(jié)點(diǎn)p之前，且令指針q在原來(lái)的鏈表上后移。typedef struct Polynomial float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next;*Polyn,Polynomial; Polyn CreatePolyn(Polyn head,int m)

7、. for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Polynomial); printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); return head; void main() int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; void DestroyPolyn(Polyn p) void PrintPolyn(Polyn P)in

8、t compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn SubtractPolyn(Polyn pa,Polyn pb)#include<stdio.h>#include<malloc.h>typedef struct Polynomial/項(xiàng)的表示 float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next; /指針域*Polyn,Polynomial; /Polyn為結(jié)點(diǎn)指針類型void Insert(Polyn p,Polyn h) /插入或者

9、合并 if(p->coef=0) free(p); /系數(shù)為0的話釋放結(jié)點(diǎn) else Polyn q1,q2; q1=h;q2=h->next; while(q2&&p->expn<q2->expn) /查找插入位置p與h項(xiàng)一次比擬指數(shù) q1=q2; q2=q2->next; if(q2&&p->expn=q2->expn) /將指數(shù)相同相合并 q2->coef+=p->coef; free(p); if(!q2->coef) /系數(shù)為0的話釋放結(jié)點(diǎn) q1->next=q2->next

10、; free(q2); else /指數(shù)為新時(shí)將結(jié)點(diǎn)插入即p->expn>q2expn情況 p->next=q2; q1->next=p; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式 int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL; for(i=0;i<m;i+) p=(Polyn)malloc(sizeof(struct Polynomial); /建立新結(jié)

11、點(diǎn)以接收數(shù)據(jù) printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調(diào)用Insert函數(shù)插入結(jié)點(diǎn) return head;/CreatePolynvoid DestroyPolyn(Polyn p) /銷毀多項(xiàng)式p Polyn q1,q2; q1=p->next; q2=q1->next; while(q1->next) free(q1); /釋放q1 q1=q2;/指針后移，循環(huán)繼續(xù)釋放，直至銷毀 q

12、2=q2->next; void PrintPolyn(Polyn P) /輸出多項(xiàng)式 Polyn q=P->next; int flag=1; /項(xiàng)數(shù)計(jì)數(shù)器 if(!q) /假設(shè)多項(xiàng)式為空，輸出0 putchar('0'); printf("n"); return; while (q) if(q->coef>0&&flag!=1) putchar('+'); /系數(shù)大于0且不是第一項(xiàng) if(q->coef!=1&&q->coef!=-1)/系數(shù)非1或-1的普通情況 prin

13、tf("%g",q->coef); if(q->expn=1) putchar('X');/系數(shù)為1的情況 else if(q->expn) printf("X%d",q->expn); else if(q->coef=1) if(!q->expn) putchar('1'); else if(q->expn=1) putchar('X'); else printf("X%d",q->expn); if(q->coef=-1) if(

14、!q->expn) printf("-1"); else if(q->expn=1) printf("-X"); else printf("-X%d",q->expn); q=q->next; flag+; /while printf("n");/PrintPolynint compare(Polyn a,Polyn b) if(a&&b) if(!b|a->expn>b->expn) return 1; else if(!a|a->expn<b

15、->expn) return -1; else return 0; else if(!a&&b) return -1;/a多項(xiàng)式已空，但b多項(xiàng)式非空 else return 1;/b多項(xiàng)式已空，但a多項(xiàng)式非空/comparePolyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)式a+b，返回其頭指針 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結(jié)點(diǎn) hc->next

16、=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb)/調(diào)用compare返回值 case 1: qc->coef=qa->coef; qc->expn=qa->expn; qa=qa->next; break; case 0: qc->coef=qa->coef+qb->coef; qc->expn=qa->expn; qa=qa->next; qb=qb->next; break; c

17、ase -1: qc->coef=qb->coef; qc->expn=qb->expn; qb=qb->next; break; /switch if(qc->coef!=0) qc->next=hc->next; hc->next=qc; hc=qc; else free(qc);/當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn) /while return headc;/AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項(xiàng)式a-b，返回其頭指針 Polyn h=pb; Polyn p=pb->

18、next; Polyn pd; while(p) /將pb的系數(shù)取反 p->coef*=-1; p=p->next; pd=AddPolyn(pa,h); for(p=h->next;p;p=p->next) /恢復(fù)pb的系數(shù) p->coef*=-1; return pd;/SubtractPolynint main()/主函數(shù) int m,n,flag=0; float x; Polyn pa=0,pb=0,pc,pd,pe,pf;/定義各式的頭指針，pa與pb在使用前付初值NULL printf("請(qǐng)輸入a的項(xiàng)數(shù):"); scanf(&qu

19、ot;%d",&m); pa=CreatePolyn(pa,m);/建立多項(xiàng)式a printf("請(qǐng)輸入b的項(xiàng)數(shù):"); scanf("%d",&n); pb=CreatePolyn(pb,n);/建立多項(xiàng)式a /輸出菜單 printf("*n"); printf("操作提示：nt1.輸出多項(xiàng)式a和bnt2.建立多項(xiàng)式a+bnt3.建立多項(xiàng)式a-bnt4.退出n"); for(;flag=0) printf("執(zhí)行操作"); scanf("%d",&

20、amp;flag); if(flag=1)/輸出多項(xiàng)式 printf("多項(xiàng)式a：");PrintPolyn(pa); printf("多項(xiàng)式b：");PrintPolyn(pb);continue; if(flag=2)/多項(xiàng)式相加 pc=AddPolyn(pa,pb); /調(diào)用函數(shù)，實(shí)現(xiàn)相加 printf("多項(xiàng)式a+b：");PrintPolyn(pc); DestroyPolyn(pc);continue; if(flag=3)/多項(xiàng)式相減 pd=SubtractPolyn(pa,pb); printf("多項(xiàng)式a-b：");PrintPolyn(pd); DestroyPolyn(pd);continue; if(flag=4) break; /結(jié)束循環(huán)，退出 Destro