【正文】 數(shù)據(jù)結構課程設計模板結構設計1． 課程設計概述共完成4個題目：編程語言：運行環(huán)境：二．一元稀疏多項式計算器問題描述： 輸入并建立多項式； 輸出多項式，輸出形式為整數(shù)序列：n，c1,e1,c2,e2,………,en,其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列； ，建立多項式a+b；，建立多項式ab。，建立乘積多項式ab。需求分析： 定義線性表的動態(tài)分配順序存儲結構； 建立多項式存儲結構，定義指針*next。每次輸入一項的系數(shù)和指數(shù)，可以輸出構造的一元多項式，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最后根據(jù)相應的輸入數(shù)據(jù)（濾去輸入中的非法字符）建立的多項式以及多項式相加的運行結果在屏幕上顯示。多項式顯示的格式為：c1x^e1+c2x^e2+…+x^en設計思路：要解決多項式相加，必須要有多項式，所以必須首先建立兩個多項式，在這里采用鏈表的方式存儲鏈表，所以我將結點結構體定義為序數(shù)coef指數(shù)expn指針域next運用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元多項式a和b，a+b的求和運算等同于單鏈表的插入問題（將單鏈表polyn p中的結點插入到單鏈表polyn h中），因此“和多項式”中的結點無須另生成。為了實現(xiàn)處理，設p、q分別指向單鏈表polya和polyb的當前項，比較p、q結點的指數(shù)項，由此得到下列運算規(guī)則：① 若pexpnqexpn，則結點p所指的結點應是“和多項式”中的一項，令指針p后移。② 若pexpn=qexpn，則將兩個結點中的系數(shù)相加，當和不為0時修改結點p的系數(shù)。③ 若pexpnqexpn，則結點q所指的結點應是“和多項式”中的一項，將結點q插入在結點p之前，且令指針q在原來的鏈表上后移。數(shù)據(jù)測試（1）、(2x+5x^^11)+(75x^8+11x^9)=(^11+11x^9+2x+7)。（2）、(2x+5x^^11)(75x^8+11x^9)=^1111x^9+10x^8+12x7。(3)(2x+5x^^11)*(75x^8+11x^9)=^20+^19+55x^1725x^^11+22x^1010x^9+35x^8+14x概要設計、結點類型和指針類型：typedef struct Polynomial{ float coef。 //系數(shù) int expn。 //指數(shù) struct Polynomial *next。}*Polyn,Polynomial。建立一個頭指針為head、項數(shù)為m的一元多項式, 建立新結點以接收數(shù)據(jù), 調(diào)用Insert函數(shù)插入結點: Polyn CreatePolyn(Polyn head,int m){ int i。 Polyn p。 p=head=(Polyn)malloc(sizeof(struct Polynomial))。 headnext=NULL。 for(i=0。im。i++) { p=(Polyn)malloc(sizeof(struct Polynomial))。 printf(請輸入第%d項的系數(shù)與指數(shù):,i+1)。 scanf(%f %d,amp。pcoef,amp。pexpn)。 Insert(p,head)。 } return head。}主函數(shù)和其他函數(shù)：void main(){ int m,n,a,x。 char flag。 Polyn pa=0,pb=0,pc。} 數(shù)據(jù)結構：帶頭結點單鏈表抽象數(shù)據(jù)類型的結點結構定義如下：typedef struct Polynode //多項式結點{ int coef。 //系數(shù) int exp。 //指數(shù) Polynode *next。}Polynode ,*Polylist。模塊劃分：(1) 帶頭結點的多項式的建立函數(shù)Polylist Polycreate()(2) 帶頭結點的多項式的降冪輸出函數(shù)void printf(Polylist poly)(3) 帶頭結點的多項式的相加函數(shù)Polylist Polyadd(Polylist a,Polylist b)(4) 帶頭結點的多項式的相減函數(shù)Polylist Polysub(Polylist a,Polylist b)(5) 主函數(shù)void main()流程圖：源代碼：includeinclude //定義多項式的項typedef struct Polynomial{ float coef。 //系數(shù) int expn。 //指數(shù) struct Polynomial *next。}*Polyn,Polynomial。void Insert(Polyn p,Polyn h){ if(pcoef==0) free(p)。 //系數(shù)為0的話釋放結點 else { Polyn q1,q2。 q1=h。 q2=hnext。 while(q2amp。amp。 pexpn q2expn) { //查找插入位置 q1=q2。 q2=q2next。 } if(q2amp。amp。 pexpn == q2expn) { //將指數(shù)相同相合并 q2coef += pcoef。 free(p)。 if(!q2coef) { //系數(shù)為0的話釋放結點 q1next=q2next。 free(q2)。 } } else { //指數(shù)為新時將結點插入 pnext=q2。 q1next=p。 } }}Polyn CreatePolyn(Polyn head,int m){ //建立一個頭指針為head、項數(shù)為m的一元多項式 int i。 Polyn p。 p=head=(Polyn)malloc(sizeof(struct Polynomial))。 headnext=NULL。 for(i=0。im。i++) { p=(Polyn)malloc(sizeof(struct Polynomial))。 //建立新結點以接收數(shù)據(jù) printf(請輸入第%d項的系數(shù)與指數(shù):,i+1)。 scanf(%f %d,amp。pcoef,amp。pexpn)。 Insert(p,head)。 //調(diào)用Insert函數(shù)插入結點 } return head。}void DestroyPolyn(Polyn p){ //銷毀多項式p Polyn q1,q2。 q1=pnext。 q2=q1next。 while(q1next) { free(q1)。 q1=q2。 q2=q2next。 }}void PrintPolyn(Polyn P){ Polyn q=Pnext。 int flag=1。 //項數(shù)計數(shù)器 if(!q) { //若多項式為空，輸出0 putchar(39。039。)。 printf(\n)。 return。 } while(q) { if(qcoef0amp。amp。 flag!=1) putchar(39。+39。)。 //系數(shù)大于0且不是第一項 if(qcoef!=1amp。amp。qcoef!=1) { //系數(shù)非1或1的普通情況 printf(%g,qcoef)。 if(qexpn==1) putchar(39。X39。)。 else if(qexpn) printf(X^%d,qexpn)。 } else { if(qcoef==1) { if(!qexpn) putchar(39。139。)。 else if(qexpn==1) putchar(39。X39。)。 else printf(X^%d,qexpn)。 } if(qcoef==1) { if(!qexpn) printf(1)。 else if(qexpn==1) printf(X)。 else printf(X^%d,qexpn)。 } } q=qnext。 flag++。 } printf(\n)。}int pare(Polyn a,Polyn b){ if(aamp。amp。b) { if(!b||aexpnbexpn) return 1。 else if(!a||aexpnbexpn) return 1。 else return 0。 } else if(!aamp。amp。b) return 1。 //a多項式已空，但b多項式非空 else return 1。 //b多項式已空，但a多項式非空}Polyn AddPolyn(Polyn pa,Polyn pb){ //求解并建立多項式a+b，返回其頭指針 Polyn qa=panext。 Polyn qb=pbnext。 Polyn headc,hc,qc。 hc=(Polyn)malloc(sizeof(struct Polynomial))。 //建立頭結點 hcnext=NULL。 headc=hc。 while(qa||qb) { qc=(Polyn)malloc(sizeof(struct Polynomial))。 switch(pare(qa,qb)){ case 1: { qccoef=qacoef。 qcexpn=qaexpn。 qa=qanext。