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

1、專業(yè)資料實(shí)習(xí)1、一元稀疏多項式計算器一、 需求分析1 .問題描述設(shè)計一個一元稀疏多項式簡單計算器。2 .基本要求一元稀疏多項式簡單計算器的基本功能是：(1)輸入并建立多項式。(2)輸出多項式，輸出形式為整數(shù)序列：n, c i, e i, c 2, e 2, -,c n, e n ,其中n是多項式的項數(shù)，。£，分別是第i項的系數(shù)和指數(shù)，序列按指數(shù)降序排列。(3)多項式a和b想加，建立多項式 a+b 。(4)多項式a和b想減，建立多項式 a-b 。3 .測試數(shù)據(jù)(1) (2x+5x8-3.1x 11)+(7-5x 8+11x9)=(-3.1x 11+11x9+2x+7)(2) (6x-3

2、-x+4.4x2-1.2x9)-(-6x-3+5.4x2-x2+7.8x15)=(-7.8x15-1.2x9+12x3-x)(3) (1+x+x2+x3+x4+x5)+(-x 3-x4)=(1+x+x 2+x5)(4) (x+x3)+(-x-x 3)=0(5) (x+x 100)+(x 100+x200)=(x+2x 100+x200)(6) (x+x2+x3)+0=(x+x 2+x3)(7) 互換測試數(shù)據(jù)的前后兩個多項式。4.實(shí)現(xiàn)提示用帶表頭結(jié)點(diǎn)的單鏈表存儲多項式。二、概要設(shè)計為實(shí)現(xiàn)上述程序功能，應(yīng)用帶頭結(jié)點(diǎn)的單鏈表存儲多項式。為此需要一個抽象數(shù)據(jù)類 型：一元多項式。1 .抽象數(shù)據(jù)類型一元多

3、項式定義為：ATD Ploynomial數(shù)據(jù)對象：D=ai|ai C Termset, i=1,2,3, m,m> 0 Termset中的每個元素包含一個表示系數(shù)的實(shí)數(shù)和表示指數(shù)的整數(shù)數(shù)據(jù)關(guān)系：R1=<ai-1,ai>ai-1,ai C D,且ai-1中的指數(shù)<ai中的指數(shù)的值，i=1,2,3 n基本操作：Insert(p,h)初始條件：h已存在。操作結(jié)果：插入p項。CreateLinklist(head, m)操作結(jié)果：建立一個頭指針為head、項數(shù)為m的一元多項式。DestroyLinklist( p)初始條件：一元多項式p已存在。操作結(jié)果：銷毀一元多項式p。Pri

4、ntLinklist( P)初始條件：一元多項式p已存在。操作結(jié)果：輸出一元多項式p。Compare(a,b)初始條件：項a,b已存在。操作結(jié)果：比較a,b中x的指數(shù)的大小。AddLinklist(pa,pb)初始條件：一元多項式pa,pb已存在。操作結(jié)果：完成一元多項式pa,pb的相加運(yùn)算。SubtractionLinklist(Sa,Sb)初始條件：一元多項式Sa,Sb已存在。操作結(jié)果：完成一元多項式Sa,Sb的相減運(yùn)算。 ATD Ploynomial三、詳細(xì)設(shè)計(源代碼)(使用C語言)#include<stdio.h>#include<malloc.h>#defi

5、ne 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項if(p->coef=0)free(p);/ 系數(shù)為0的話釋放結(jié)點(diǎn) else Linklist q1,q2;q1=h;q2=h->next;while(q2&&p->expn<q2->ex

6、pn) /查找插入位置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); else /指數(shù)為新時將結(jié)點(diǎn)插入p->next=q2;q1->next=p; Linklist CreateLinklist(Linklist head,int m)/建立一個頭指針為head、項數(shù)為m的一元多項式int i;Linkli

7、st p;p=head=(Linklist)malloc(sizeof(struct Linklistomial); head->next=NULL;for(i=0;i<m;i+)建立新結(jié)點(diǎn)以接收數(shù)據(jù)p=(Linklist)malloc(sizeof(struct Linklistomial);/printf("請輸入第幽的系數(shù)與指數(shù):",i+1);scanf("%f %d",&p->coef,&p->expn);Insert(p,head); /調(diào)用Insert 函數(shù)插入結(jié)點(diǎn) return head; void

8、DestroyLinklist(Linklist p)/銷毀多項式pLinklist D1,D2;D1=p;while(D1)D2=D1->next;free(D1);D1=D2; void PrintLinklist(Linklist P)/輸出一元多項式pLinklist q=P->next;int flag=1; / 項數(shù)計數(shù)器if(!q) /若多項式為空，輸出 0putchar('O');printf("n");return;while(q)系數(shù)大于0且不是第一項if(q->coef>0&&flag!=1) p

9、utchar('+'); if(q->coef!=1&&q->coef!=-1) / 系數(shù)非1或-1的普通情況printf("%g",q->coef);if(q->expn=1) putchar('X');else if(q->expn) printf("XA%d",q->expn);elseif(q->coef=1)if(!q->expn)putchar('l');else if(q->expn=1) putchar('X

10、9;);elseprintf("XA%d",q->expn);if(q->coef=-1)if(!q->expn)printf("-1");else if(q->expn=1) printf("-X");elseprintf("-XA%d",q->expn);q=q->next;flag+；printf("n");int Compare(Linklist a,Linklist b)/比較a,b中x的指數(shù)的大小if(a&&b)if(!b|a-&g

11、t;expn>b->expn)return 1;else if(!a|a->expn<b->expn)return -1;elsereturn 0;else if(!a&&b)/a 多項式已空，但 b多項式非空 return -1;else/b多項式已空，但 a多項式非空return 1;Linklist AddLinklist(Linklist pa,Linklist pb)/求解并建立多項式a+b,返回其頭指針Linklist qa=pa->next;Linklist qb=pb->next;Linklist headc,hc,qc

12、;hc=(Linklist)malloc(sizeof(struct Linklistomial);/ hc->next=NULL;headc=hc;while(qa|qb)qc=(Linklist)malloc(sizeof(struct Linklistomial); switch(Compare(qa,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-&g

13、t;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;hc->next=qc;hc=qc;elsefree(qc);/當(dāng)相加系數(shù)為0時，釋放該結(jié)點(diǎn)return headc;Linklist SubtractionLinklist(Linklist Sa,Linklist Sb)/求解并建立多項式 a-b ,返回其頭指針L

14、inklist 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;printf(" printf(" printf(" printf(" printf("*n");printf("歡迎使用一元多項式加法器*n，);一元多項式簡單運(yùn)算器*n");A:輸入多項式a*n"

15、;);nn");/ 輸出菜單*n");B:輸入多項式bprintf("*C：輸出多項式aD:輸出多項式b*n");printf("*n");printf("*E:輸出a+bF:輸出a-b*n");printf("*n");printf("* G:使用完畢！*n");printf("*=")；while(a)printf("n請選擇操作：");scanf(" %c”,&flag);/空格符號一定要注意switch(fla

16、g)case'A':case'a':printf("下面進(jìn)行多項式 a的輸入：n");printf("請輸入a的項數(shù):")；scanf("%d",&m);pa=CreateLinklist(pa,m);建立多項式 abreak; case'B':case'b':printf("下面進(jìn)行多項式 b的輸入：n");printf("請輸入b的項數(shù):")；scanf("%d",&n);pb=CreateL

17、inklist(pb,n);建立多項式 bbreak; case'C':case'c':多項式a=");多項式b="); printf("n PrintLinklist(pa); break; case'D': case'd': printf("n PrintLinklist(pb);break;case'E':case'e':pc=AddLinklist(pa,pb);printf("n a+b=");PrintLinklist(pc);

18、break;case'F':case'f:pc=SubtractionLinklist(pa,pb);printf("n a-b=");PrintLinklist(pc);break;case'G':case'g':DestroyLinklist(pa);DestroyLinklist(pb);a=0;printf("n歡迎下次使用！n");break;default:printf("n您的選擇錯誤，請重新選擇！n");return 0;四、調(diào)試分析編譯環(huán)境為CodeBlocks

19、 。word完美格式歡迎耍用一元多項式址法器一元芟項式簡單運(yùn)算器,匚由 nDebugC.exeft=輸入多項式aC-輸出多項式耳E：輸出h+M命使用完畢！B：輸入冬頂式b*D二輸出多項而*量F：輸出af*11的人-,輸11 18.32 5 一勒揀tBWHES-Hr 與與與 數(shù)數(shù)數(shù) 雪:3爹累 暮翦的的 尚拜爆項項 請初S3進(jìn)IA入AA EJ一口 .一Hi."一,. 卜請請請請b A-輸備: ;匕 gman與匕尸 數(shù)數(shù)數(shù) 戶條案系的的選打罌頂項 請將粗改段 迎人人人人 請請請請請詡革操作. C會項式*-3-1*口 +5*3 壯!造圜圣操作，D多項式h=，X ” T菖+7請圜箏操作.心a+b=-3.1XAU +11X"9+ZX+?* F:供3S：C由 nDebugC請選操作：ea+I>=-3.1X11 *11Xa9+4W+7a /.后23 1 2- 4 *而T 4 T" 二«靜敬r'.OT -mnJllJ、二，與與與與數(shù)數(shù)用.瞽的的的項 上耳妥自12 3