1、課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設計 課題名稱 一元稀疏多項式計算器 目錄一、課題的主要功能4二、課題的功能模塊的劃分6三、主要功能的實現(xiàn)7四、程序調(diào)試9五、總結(jié)（程序設計心得與體會）11六、附件（所有程序的原代碼）12七、評分表18一、課題的主要功能a、課程題目 一元稀疏多項式計算器b、需求分析1、一元稀疏多項式簡單計算器的功能是：1.1 輸入并建立多項式；1.2 輸出多項式，輸出形式為整數(shù)序列：n，c1,e1,c2,e2,cn,en,其中n是多項式的項數(shù)，ci和ei分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列； 1.5多項式a和b相加，建立多項式a+b；1.6 多項式a和b相減，建立多項式a-b；1

2、.7 計算多項式在x處的值。2、設計思路:2.1 定義線性表的動態(tài)分配順序存儲結(jié)構(gòu)；2.2 建立多項式存儲結(jié)構(gòu)，定義指針*next2.3利用鏈表實現(xiàn)隊列的構(gòu)造。每次輸入一項的系數(shù)和指數(shù)，可以輸出構(gòu)造的一元多項式2.4演示程序以用戶和計算機的對話方式執(zhí)行，即在計算機終站上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運行命令；最后根據(jù)相應的輸入數(shù)據(jù)（濾去輸入中的非法字符）建立的多項式以及多項式相加的運行結(jié)果在屏幕上顯示。多項式顯示的格式為：c1xe1+c2xe2+cnxen3、設計思路分析要解決多項式相加，必須要有多項式，所以必須首先建立兩個多項式，在這里采用鏈表的方式存儲鏈表，所以我

3、將結(jié)點結(jié)構(gòu)體定義為序數(shù)coef指數(shù)expn指針域next運用尾插法建立兩條單鏈表，以單鏈表polyn p和polyn h分別表示兩個一元多項式a和b，a+b的求和運算等同于單鏈表的插入問題（將單鏈表polyn p中的結(jié)點插入到單鏈表polyn h中），因此“和多項式”中的結(jié)點無須另生成。為了實現(xiàn)處理，設p、q分別指向單鏈表polya和polyb的當前項，比較p、q結(jié)點的指數(shù)項，由此得到下列運算規(guī)則： 若p->expn<q->expn，則結(jié)點p所指的結(jié)點應是“和多項式”中的一項，令指針p后移。 若p->expn=q->expn，則將兩個結(jié)點中的系數(shù)相加，當和不為0時

4、修改結(jié)點p的系數(shù)。 若p->expn>q->expn，則結(jié)點q所指的結(jié)點應是“和多項式”中的一項，將結(jié)點q插入在結(jié)點p之前，且令指針q在原來的鏈表上后移。二、課題的功能模塊的劃分 內(nèi)容包括：函數(shù)CreatePolyn建立一個頭指針為head、項數(shù)為m的一元多項式，然后調(diào)運函數(shù)Insert向生成鏈表中保存多項式項數(shù)及每項的指數(shù)、系數(shù)。函數(shù)CreatePolyn生成多項式a和多項式b。通過函數(shù)compare和函數(shù)PrintPolyn對多項式a和多項式b指數(shù)、系數(shù)進行分析。當多項式a指數(shù)指數(shù)大于多項式b指數(shù)時，鏈表保存多項式a系數(shù)；當多項式b指數(shù)指數(shù)大于多項式a指數(shù)時，鏈表保存多項

5、式b系數(shù)；當多項式b指數(shù)指數(shù)等于多項式a指數(shù)時，對多項式a和多項式b系數(shù)進行加減運算，之后將系數(shù)保存在鏈表中。函數(shù)Polyn AddPolyn對多項式a和多項式b進行加運算，調(diào)運函數(shù)compare、函數(shù)PrintPolyn、函數(shù)CreatePolyn。函數(shù)SubtractPolyn對多項式a和多項式b進行減運算，其對多項式b中各系數(shù)正負取反，然后調(diào)用函數(shù)Polyn AddPolyn進行a+(-b)。主函數(shù)運行分別輸入多項式和多項式的項數(shù)、系數(shù)和指數(shù)，然后選擇對多項式操作A：a+b或 B：a-b，從而實現(xiàn)對多項式的加減運算。函數(shù)的調(diào)用關系圖：三、主要功能的實現(xiàn)1、元素類型、結(jié)點類型和指針類型：t

6、ypedef struct Polynomial float coef; /系數(shù) int expn; /指數(shù) struct Polynomial *next;*Polyn,Polynomial;2、建立一個頭指針為head、項數(shù)為m的一元多項式, 建立新結(jié)點以接收數(shù)據(jù), 調(diào)用Insert函數(shù)插入結(jié)點: Polyn CreatePolyn(Polyn head,int m) int i; Polyn p; p=head=(Polyn)malloc(sizeof(struct Polynomial); head->next=NULL; for(i=0;i<m;i+) p=(Polyn)

7、malloc(sizeof(struct Polynomial); printf("請輸入第%d項的系數(shù)與指數(shù):",i+1); scanf("%f %d",&p->coef,&p->expn); Insert(p,head); return head;3、主函數(shù)和其他函數(shù)：void main() int m,n,a,x; char flag; Polyn pa=0,pb=0,pc; float ValuePolyn(Polyn head,int x) /輸入x值，計算并返回多項式的值主要函數(shù)的流程圖：四、程序調(diào)試測試數(shù)據(jù)a.；

8、b.；c.；d.；e. ；五、總結(jié)經(jīng)過這段為期不久的課程設計，使我對于數(shù)據(jù)結(jié)構(gòu)有了更深層次的理解,循環(huán)隊列中對邊界條件的處理,滿足什么條件為隊滿,滿足什么條件為隊空。在這個過程中。我也曾因為實踐經(jīng)驗缺乏失落過；也曾經(jīng)仿真成功而熱情高漲。生活就這樣；雖然這只是一次極其簡單的課程設計；可是平心而論，也耗費我不少的心血。這讓我不得不對我們社會的付出的老一輩；為了我們的生活更美好，他們?yōu)槲覀兏冻龆嗌傩难Ｎ腋杏X用心細心地做好一件事情的重要性，在這次課程設計中，體會到了做設計的嚴謹，更加加深了我對課程設計的興趣，我覺得我們不僅是在完成一個課題，更是對自我知識的探索以及團隊合作的重要性，在此次課程設計過程

9、中，遇到不懂的問題我會及時向老師，同學請教，以更好地完成該項課題設計。一個人的能力有限；此次的程序設計能夠成功，是我自身的努力和尋求老師同學的幫助共同努力作用的結(jié)果。在這一段努力學習的過程中，收獲還真是不少，雖然說以前非常不懂這門語言，在它上面花費了好多心血，覺得它很難，是需用花費了大量的時間編寫出來的。現(xiàn)在真正的明白了一些代碼的應用，每個程序都有一些共同點，通用的結(jié)構(gòu)，相似的格式。只要努力去學習，就會靈活的去應用它。以后，努力學習好這么課程，讓自己擁有更多的知識，才能解決更多的問題。六、附件用帶表頭結(jié)點的單鏈表存儲多項式。 #include <stdio.h>#incl

10、ude <malloc.h>typedef struct nodefloat coef;int expn;struct node *next;Lnode, *polynmial;void create(polynmial &L);   /輸入并建立多項式Lvoid display(polynmial L);   /顯示，輸出多項式Lvoid sort(polynmial &L);   /多項式L按指數(shù)排序void reverse(polynmial &L);   /逆置void

11、select();      /用戶選擇加減操作void add(polynmial La, polynmial Lb, polynmial &Lc);   /多項式La,Lb相加void subtract(polynmial La, polynmial Lb, polynmial &Ld); /多項式La減去Lb，結(jié)果給Ldvoid create(polynmial &L) /輸入并建立多項式Lint i, n;static struct node *p;scanf("%d",

12、&n);L = (struct node *)malloc (sizeof(struct node);L->next = NULL;for(i = 0; i < n; i+)   p = (struct node *)malloc(sizeof(struct node);   scanf("%f %d", &p->coef, &p->expn);   p->next = L->next;   L->next = p;void di

13、splay(polynmial L)/顯示，輸出多項式Lstruct node *p, *q;int flag = 0;int k = 0;q = L->next;while(q)   if(q->coef != 0)    k+;   q = q->next;printf("%d, ", k);p = L->next;if(p->coef != 0)   printf("%.1f,%d, ", p->coef, p->ex

14、pn);   flag+;for(p = p->next; p; p = p->next)   if(p->coef != 0)       printf("%.1f,%d, ", p->coef, p->expn);    flag+;   if(flag = 0)   printf("%dn", flag);else   printf(&quo

15、t;n");void sort(polynmial &L)/多項式L按指數(shù)排序polynmial p, q, r, u;p = L->next;L->next = NULL;while(p != NULL)   r = L;   q = L->next;   while(q != NULL) && (q->expn <= p->expn)       r = q;    q = q-&g

16、t;next;      u = p->next;   r->next = p;   p->next = q;   p = u;void reverse(polynmial &L)/逆置polynmial H;static struct node *p, *q, *s;H = (struct node*)malloc(sizeof(struct node);H->next = NULL;p = (struct node*)malloc(sizeof(struct

17、node);s = L->next;p->coef = s->coef;p->expn = s->expn;p->next = s->next;while(s)   p->coef = s->coef;   p->expn = s->expn;   p->next = s->next;   q = H->next;   H->next = p;   p->next = q;

18、0;  p = (struct node*)malloc(sizeof(struct node);   s = s->next;p = H->next;q = L->next;while(p)   q->coef = p->coef;   q->expn = p->expn;   q = q->next;   p = p->next;void select() /用戶選擇加減操作printf("請選擇加減操作n"

19、);printf("1.兩個一元多項式相加n");printf("2.兩個一元多項式相減n");void add(polynmial La, polynmial Lb, polynmial &Lc)/多項式La,Lb相加struct node *pa, *pb;static struct node *pc;Lc = (struct node*)malloc(sizeof(struct node);pa = La->next;pb = Lb->next;Lc->next = NULL;while(pa && pb)

20、   pc = (struct node*)malloc(sizeof(struct node);   if(pa->expn < pb->expn)       pc->next = Lc->next;    Lc->next = pc;    pc->coef = pa->coef;    pc->expn = pa->expn;  

21、  pa = pa->next;      else    if(pa->expn = pb->expn)         pc->next = Lc->next;     Lc->next = pc;     pc->expn = pa->expn;     pc->coe

22、f = pa->coef + pb->coef;     pa = pa->next;     pb = pb->next;        else         pc->next = Lc->next;     Lc->next = pc;     pc->

23、coef = pb->coef;     pc->expn = pb->expn;     pb = pb->next;    while(pa)   pc = (struct node*)malloc(sizeof(struct node);   pc->next = Lc->next;   Lc->next = pc;   pc->coef = pa-&g

24、t;coef;   pc->expn = pa->expn;   pa = pa->next;while(pb)   pc = (struct node*)malloc(sizeof(struct node);   pc->next = Lc->next;   Lc->next = pc;   pc->coef = pb->coef;   pc->expn = pb->expn; 

25、60; pb = pb->next;void subtract(polynmial La, polynmial Lb, polynmial &Ld)/多項式La減去Lb，結(jié)果給Ldstruct node *pa, *pb;static struct node *pd;Ld = (struct node*)malloc(sizeof(struct node);pa = La->next;pb = Lb->next;Ld->next = NULL;while(pa && pb)   pd = (struct node*)mallo

26、c(sizeof(struct node);   if(pa->expn < pb->expn)       pd->next = Ld->next;    Ld->next = pd;    pd->coef = pa->coef;    pd->expn = pa->expn;    pa = pa->next;  

27、   else    if(pa->expn = pb->expn)         pd->next = Ld->next;     Ld->next = pd;     pd->expn = pa->expn;     pd->coef = pa->coef - pb->coef; &

28、#160;   pa = pa->next;     pb = pb->next;        else         pd->next = Ld->next;     Ld->next = pd;     pd->coef = pb->coef;     pd->expn = pb->expn;     pb = pb->next;    while(pa)   pd = (struct node*)malloc(sizeof(struct node);   pd->next = Ld->next;   Ld->next = pd;   pd->coef = pa->coef;