數(shù)據(jù)結構課程設計--一元稀疏多項式簡單計數(shù)器

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

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

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

4、b相減，建立多項式a-b，輸出相減的多項式。用帶表頭結點的單鏈表存儲多項式。使我們進一步理解和掌握課堂上所學各種根本抽象數(shù)據(jù)類型的邏輯結構、存儲結構和操作實現(xiàn)算法，以及它們在程序中的使用方法。使我們掌握軟件設計的根本內(nèi)容和設計方法，并培養(yǎng)學生進行標準化軟件設計的能力。使我們掌握使用各種計算機資料和有關參考資料，提高學生進行程序設計的根本能力。熟練掌握數(shù)據(jù)結構這門課程，掌握線性表、棧、隊列、串、數(shù)組、廣義表、樹和二叉樹以及圖等根本類型的數(shù)據(jù)結構及其應用.進一步熟悉抽象數(shù)據(jù)類型的定義和實現(xiàn)、如何利用數(shù)組的動態(tài)分酚實現(xiàn)順序結構、繼承的實現(xiàn)方式。學會分析研究計算機加工的數(shù)據(jù)結構的特性，以便為應用涉及的

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

6、xpn，那么結點p所指的結點應是“和多項式中的一項，令指針p后移。 假設p->expn=q->expn，那么將兩個結點中的系數(shù)相加，當和不為0時修改結點p的系數(shù)。 假設p->expn>q->expn，那么結點q所指的結點應是“和多項式中的一項，將結點q插入在結點p之前，且令指針q在原來的鏈表上后移。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("請輸入第%d項的系數(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/項的表示 float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next; /指針域*Polyn,Polynomial; /Polyn為結點指針類型void Insert(Polyn p,Polyn h) /插入或者

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

10、; free(q2); else /指數(shù)為新時將結點插入即p->expn>q2expn情況 p->next=q2; q1->next=p; /InsertPolyn CreatePolyn(Polyn head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式 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); /建立新結

11、點以接收數(shù)據(jù) printf("請輸入第%d項的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); /調用Insert函數(shù)插入結點 return head;/CreatePolynvoid DestroyPolyn(Polyn p) /銷毀多項式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) /輸出多項式 Polyn q=P->next; int flag=1; /項數(shù)計數(shù)器 if(!q) /假設多項式為空，輸出0 putchar('0'); printf("n"); return; while (q) if(q->coef>0&&flag!=1) putchar('+'); /系數(shù)大于0且不是第一項 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多項式已空，但b多項式非空 else return 1;/b多項式已空，但a多項式非空/comparePolyn AddPolyn(Polyn pa,Polyn pb)/求解并建立多項式a+b，返回其頭指針 Polyn qa=pa->next; Polyn qb=pb->next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立頭結點 hc->next

16、=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(compare(qa,qb)/調用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);/當相加系數(shù)為0時，釋放該結點 /while return headc;/AddPolynPolyn SubtractPolyn(Polyn pa,Polyn pb)/求解并建立多項式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) /恢復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("請輸入a的項數(shù):"); scanf(&qu

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

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