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

1、實(shí)習(xí) 1、一元稀疏多項(xiàng)式計(jì)算器一、需求分析1. 問(wèn)題描述設(shè)計(jì)一個(gè)一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器。2. 基本要求一元稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器的基本功能是：(1)輸入并建立多項(xiàng)式。(2)輸出多項(xiàng)式，輸出形式為整數(shù)序列：n, c1, e1, c 2, e2,········ ,cn, en，其中n 是多項(xiàng)式的項(xiàng)數(shù)， ci,ei 分別是第i 項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列。(3)多項(xiàng)式 a 和 b 想加，建立多項(xiàng)式a+b 。(4)多項(xiàng)式 a 和 b 想減，建立多項(xiàng)式a-b 。3. 測(cè)試數(shù)據(jù)(1) (2x+5x 8 -3.1x11

2、)+(7-5x 8+11x9)=(-3.1x 11+11x9+2x+7)(2) (6x -3-x+4.4x 2-1.2x 9)-(-6x -3+5.4x 2-x2+7.8x15)=(-7.8x 15-1.2x 9+12x -3-x)(3) (1+x+x 2 +x3+x 4+x5 )+(-x 3-x4)=(1+x+x 2+x 5)(4) (x+x 3)+(-x-x 3)=0(5) (x+x 100)+(x 100+x 200)=(x+2x 100+x 200)(6) (x+x 2+x 3)+0=(x+x 2+x 3)(7) 互換測(cè)試數(shù)據(jù)的前后兩個(gè)多項(xiàng)式。4. 實(shí)現(xiàn)提示用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)

3、式。二、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功能，應(yīng)用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。為此需要一個(gè)抽象數(shù)據(jù)類型：一元多項(xiàng)式。1.抽象數(shù)據(jù)類型一元多項(xiàng)式定義為：ATD Ploynomial數(shù)據(jù)對(duì)象： D=ai|ai Termset, i=1,2,3 ···，m,m 0 Termset 中的每個(gè)元素包含一個(gè)表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系： R1=<ai-1,ai>ai-1,ai D,且 ai-1 中的指數(shù) <ai 中的指數(shù)的值， i=1,2,3 ··· n 基本操作：Insert(p,h)初始條件： h 已存在。操作結(jié)果：插入p

4、項(xiàng)。CreateLinklist(head, m)操作結(jié)果：建立一個(gè)頭指針為head、項(xiàng)數(shù)為m 的一元多項(xiàng)式。DestroyLinklist( p)初始條件：一元多項(xiàng)式p 已存在。操作結(jié)果：銷毀一元多項(xiàng)式p。PrintLinklist( P)初始條件：一元多項(xiàng)式p 已存在。操作結(jié)果：輸出一元多項(xiàng)式p。Compare(a,b)初始條件：項(xiàng)a,b 已存在。操作結(jié)果：比較a,b 中 x 的指數(shù)的大小。AddLinklist(pa,pb)初始條件：一元多項(xiàng)式pa,pb 已存在。操作結(jié)果：完成一元多項(xiàng)式pa,pb 的相加運(yùn)算。SubtractionLinklist(Sa,Sb)初始條件：一元多項(xiàng)式Sa,

5、Sb 已存在。操作結(jié)果：完成一元多項(xiàng)式Sa,Sb 的相減運(yùn)算。 ATD Ploynomial三、詳細(xì)設(shè)計(jì)（源代碼）（使用 C 語(yǔ)言）#include<stdio.h>#include<malloc.h>#define maxlen 10#define large 999typedef struct Linklistomialfloat coef;int expn;struct Linklistomial *next;Linklistomial,*Linklist;/結(jié)點(diǎn)類型，指針類型void Insert(Linklist p,Linklist h)/ h 已存在插入p

6、 項(xiàng)if(p->coef=0)free(p);/ 系數(shù)為 0 的話釋放結(jié)點(diǎn)elseLinklist q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->expn) / 查找插入位置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;free(q2);el

7、se / 指數(shù)為新時(shí)將結(jié)點(diǎn)插入p->next=q2;q1->next=p;Linklist CreateLinklist(Linklist head,int m)/ 建立一個(gè)頭指針為head、項(xiàng)數(shù)為m 的一元多項(xiàng)式int i;Linklist p;p=head=(Linklist)malloc(sizeof(struct Linklistomial);head->next=NULL;for(i=0;i<m;i+)p=(Linklist)malloc(sizeof(struct Linklistomial);/ 建立新結(jié)點(diǎn)以接收數(shù)據(jù) printf(" 請(qǐng)輸入第

8、%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;void DestroyLinklist(Linklist p)/ 銷毀多項(xiàng)式pLinklist D1,D2;D1=p;while(D1)D2=D1->next;free(D1);D1=D2;void PrintLinklist(Linklist P)/ 輸出一元多項(xiàng)式pLinklist q=P->next;int flag=1; /

9、項(xiàng)數(shù)計(jì)數(shù)器if(!q) / 若多項(xiàng)式為空，輸出0putchar('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 的普通情況printf("%g",q->coef);if(q->expn=1) putchar('X');else if(q->

10、expn) printf("X%d",q->expn);elseif(q->coef=1)if(!q->expn)putchar('1');else if(q->expn=1)putchar('X');elseprintf("X%d",q->expn);if(q->coef=-1)if(!q->expn)printf("-1");else if(q->expn=1)printf("-X");elseprintf("-X%d&q

11、uot;,q->expn);q=q->next;flag+;printf("n");int Compare(Linklist a,Linklist b)/ 比較 a,b 中 x 的指數(shù)的大小if(a&&b)if(!b|a->expn>b->expn)return 1;else if(!a|a->expn<b->expn)return -1;elsereturn 0;else if(!a&&b)/a多項(xiàng)式已空，但b 多項(xiàng)式非空return -1;else/b 多項(xiàng)式已空，但return 1;a 多

12、項(xiàng)式非空Linklist AddLinklist(Linklist pa,Linklist pb)/ 求解并建立多項(xiàng)式a+b，返回其頭指針Linklist qa=pa->next;Linklist qb=pb->next;Linklist headc,hc,qc;hc=(Linklist)malloc(sizeof(struct Linklistomial);/ 建立頭結(jié)點(diǎn) hc->next=NULL;headc=hc;while(qa|qb)qc=(Linklist)malloc(sizeof(struct Linklistomial);switch(Compare(qa,

13、qb)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;case -1:qc->coef=qb->coef;qc->expn=qb->expn;qb=qb->next;break;if(qc->coef!=0)qc->next=hc->next

14、;hc->next=qc;hc=qc;elsefree(qc);/ 當(dāng)相加系數(shù)為0 時(shí)，釋放該結(jié)點(diǎn)return headc;Linklist SubtractionLinklist(Linklist Sa,Linklist Sb)/ 求解并建立多項(xiàng)式a-b，返回其頭指針Linklist Cb=Sb->next;while(Cb)Cb->coef=(-1)*Cb->coef;Cb=Cb->next;return AddLinklist(Sa,Sb);int main()int m,n,a=1;char flag;Linklist pa=0,pb=0,pc;print

15、f("歡迎使用一元多項(xiàng)式加法器nn");/ 輸出菜單printf("*n");printf("*一元多項(xiàng)式簡(jiǎn)單運(yùn)算器*n");printf("*n");printf("*A: 輸入多項(xiàng)式 aB:輸入多項(xiàng)式 b*n");printf("*n");printf("*C: 輸出多項(xiàng)式 aD:輸出多項(xiàng)式 b*n");printf("*n");printf("*E: 輸出 a+bF: 輸出 a-b*n");printf(&qu

16、ot;*n");printf("*G: 使用完畢！*n");printf("*n");while(a)printf("n請(qǐng)選擇操作： ");scanf(" %c",&flag);/空格符號(hào)一定要注意switch(flag)case'A':case'a':printf(" 下面進(jìn)行多項(xiàng)式a 的輸入： n");printf(" 請(qǐng)輸入 a 的項(xiàng)數(shù) :");scanf("%d",&m);pa=Create

17、Linklist(pa,m);/ 建立多項(xiàng)式abreak;case'B':case'b':printf(" 下面進(jìn)行多項(xiàng)式b 的輸入： n");printf(" 請(qǐng)輸入 b 的項(xiàng)數(shù) :");scanf("%d",&n);pb=CreateLinklist(pb,n);/ 建立多項(xiàng)式bbreak;case'C':case'c':printf("n多項(xiàng)式a=");PrintLinklist(pa);break;case'D':case'd':printf("n多項(xiàng)式b=");PrintLinklist(pb);break;case'E':case'e':pc=AddLinklist(pa,pb);printf("na+b=");PrintLinklist(pc);break;case'F':case&