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

一元多項(xiàng)式的計(jì)算需求分析建立一元多項(xiàng)式并按照指數(shù)降序排列輸出多項(xiàng)式，將一元多項(xiàng)式輸入并存儲(chǔ)在內(nèi)存中，能夠完成兩個(gè)多項(xiàng)式的加減運(yùn)算并輸出結(jié)果概要設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)：一元多項(xiàng)式的表示在計(jì)算機(jī)內(nèi)可以用鏈表來(lái)表示，為了節(jié)省存儲(chǔ)空間，只存儲(chǔ)多項(xiàng)式中系數(shù)非零的項(xiàng)。鏈表中的每一個(gè)結(jié)點(diǎn)存放多項(xiàng)式的一個(gè)系數(shù)非零項(xiàng)，它包含三個(gè)域，分別存放該項(xiàng)的系數(shù)、指數(shù)以及指向下一個(gè)多項(xiàng)式項(xiàng)結(jié)點(diǎn)的指針。創(chuàng)立一元多項(xiàng)式鏈表，對(duì)一元多項(xiàng)式的運(yùn)算中會(huì)出現(xiàn)的各種可能情況進(jìn)行分析，實(shí)現(xiàn)一元多項(xiàng)式的相加、相減操作。根本算法：1、輸入輸出〔1〕功能：將要進(jìn)行運(yùn)算的多項(xiàng)式輸入輸出?！?〕數(shù)據(jù)流入：要輸入的多項(xiàng)式的系數(shù)與指數(shù)?！?〕數(shù)據(jù)流出：合并同類(lèi)項(xiàng)后的多項(xiàng)式。〔4〕程序流程圖：多項(xiàng)式輸入流程圖如圖1所示。〔5〕測(cè)試要點(diǎn)：輸入的多項(xiàng)式是否正確，假設(shè)輸入錯(cuò)誤那么重新輸入圖表圖表SEQ圖表\*ARABIC1開(kāi)始申請(qǐng)結(jié)點(diǎn)空間開(kāi)始申請(qǐng)結(jié)點(diǎn)空間+++++++++++++++++++++++++++++++++++++++++++++++++++++++num輸入多項(xiàng)式的項(xiàng)數(shù)指針數(shù)組temp[i]中〔i=1~num〕輸入多項(xiàng)式各項(xiàng)的系數(shù)x,指數(shù)y輸出已輸入的多項(xiàng)式合并同類(lèi)項(xiàng)結(jié)束否是是否輸入正確2、多項(xiàng)式的加法〔1〕功能：將兩多項(xiàng)式相加?！?〕數(shù)據(jù)流入：輸入函數(shù)?！?〕數(shù)據(jù)流出：多項(xiàng)式相加后的結(jié)果?！?〕程序流程圖：多項(xiàng)式的加法流程圖如圖2所示?！?〕測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空那么提示重新輸入，否那么，進(jìn)行運(yùn)算。圖表SEQ圖表\*ARABIC2開(kāi)始開(kāi)始定義存儲(chǔ)結(jié)果的空鏈r是否輸出存儲(chǔ)多項(xiàng)式的和的鏈r結(jié)束是否同指數(shù)項(xiàng)系數(shù)相加后存入r中直接把p中各項(xiàng)存入r中直接把q中各項(xiàng)存入r存儲(chǔ)多項(xiàng)式2的空鏈Q(jìng)是否為空存儲(chǔ)多項(xiàng)式1的空鏈P是否為空合并同類(lèi)項(xiàng)3、多項(xiàng)式的減法〔1〕功能：將兩多項(xiàng)式相減?！?〕數(shù)據(jù)流入：調(diào)用輸入函數(shù)。〔3〕數(shù)據(jù)流出：多項(xiàng)式相減后的結(jié)果?！?〕程序流程圖：多項(xiàng)式的減法流程圖如圖3所示。〔5〕測(cè)試要點(diǎn)：兩多項(xiàng)式是否為空，為空那么提示重新輸入，否那么，進(jìn)行運(yùn)算。圖表SEQ圖表\*ARABIC圖表SEQ圖表\*ARABIC3開(kāi)始定義存儲(chǔ)結(jié)果的空鏈r是否輸出存儲(chǔ)多項(xiàng)式的和的鏈r結(jié)束是否同指數(shù)項(xiàng)系數(shù)相加后存入r中把p中各項(xiàng)系數(shù)改變符號(hào)后存入r中直接把q中各項(xiàng)存入r存儲(chǔ)多項(xiàng)式2的空鏈Q(jìng)是否為空存儲(chǔ)多項(xiàng)式1的空鏈P是否為空合并同類(lèi)項(xiàng)詳細(xì)設(shè)計(jì)#include<stdio.h>#include<malloc.h>typedefstructPolynomial{floatcoef;intexpn;structPolynomial*next;}*Polyn,Polynomial;//Polyn為結(jié)點(diǎn)指針類(lèi)型voidInsert(Polynp,Polynh){if(p->coef==0)free(p);//系數(shù)為0的話釋放結(jié)點(diǎn)else{Polynq1,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);}}else{//指數(shù)為新時(shí)將結(jié)點(diǎn)插入p->next=q2;q1->next=p;}}}//InsertPolynCreatePolyn(Polynhead,intm){//建立一個(gè)頭指針為head、項(xiàng)數(shù)為m的一元多項(xiàng)式inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新結(jié)點(diǎn)以接收數(shù)據(jù)printf("請(qǐng)輸入第%d項(xiàng)的系數(shù)與指數(shù):",i+1);scanf("%f%d",&p->coef,&p->expn);Insert(p,head);//調(diào)用Insert函數(shù)插入結(jié)點(diǎn)}returnhead;}//CreatePolynvoidDestroyPolyn(Polynp){//銷(xiāo)毀多項(xiàng)式pPolynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指針后移q2=q2->next;}}voidPrintPolyn(PolynP){Polynq=P->next;intflag=1;//項(xiàng)數(shù)計(jì)數(shù)器if(!q){//假設(shè)多項(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');elseif(q->expn)printf("X^%d",q->expn);}else{if(q->coef==1){if(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);}if(q->coef==-1){if(!q->expn)printf("-1");elseif(q->expn==1)printf("-X");elseprintf("-X^%d",q->expn);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynintcompare(Polyna,Polynb){if(a&&b){if(!b||a->expn>b->expn)return1;elseif(!a||a->expn<b->expn)return-1;elsereturn0;}elseif(!a&&b)return-1;//a多項(xiàng)式已空，但b多項(xiàng)式非空elsereturn1;//b多項(xiàng)式已空，但a多項(xiàng)式非空}//comparePolynAddPolyn(Polynpa,Polynpb){//求解并建立多項(xiàng)式a+b，返回其頭指針Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點(diǎn)hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb)){case1:{qc->coef=qa->coef;qc->expn=qa->expn;qa=qa->next;break;}case0:{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;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//當(dāng)相加系數(shù)為0時(shí)，釋放該結(jié)點(diǎn)}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項(xiàng)式a+b，返回其頭指針Polynh=pb;Polynp=pb->next;Polynpd;while(p){//將pb的系數(shù)取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢復(fù)pb的系數(shù)p->coef*=-1;returnpd;}//SubtractPolynintmain(){intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULLprintf("請(qǐng)輸入a的項(xiàng)數(shù):");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多項(xiàng)式aprintf("請(qǐng)輸入b的項(xiàng)數(shù):");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多項(xiàng)式a//輸出菜單printf("**********************************************\n");printf("操作提示：\n\t1.輸出多項(xiàng)式a和b\n\t2.建立多項(xiàng)式a+b\n\t3.建立多項(xiàng)式a-b\n");printf("\t4.退出\n**********************************************\n");for(;;flag=0){printf("執(zhí)行操作：");scanf("%d",&flag);if(flag==1){printf("多項(xiàng)式a：");PrintPolyn(pa);printf("多項(xiàng)式b：");PrintPolyn(pb);continue;}if(flag==2){pc=AddPolyn(pa,pb);printf("多項(xiàng)式a+b：");PrintPolyn(pc);DestroyPolyn(pc);continue;}if(flag==3){pd=SubtractPolyn(pa,pb);printf("多項(xiàng)式a-b：");PrintPolyn(pd);DestroyPolyn(pd);continue;}if(flag==4)break;if(flag<1||flag>4)printf("Error!!!\n");continue;}//forDestroyPolyn(pa);DestroyPolyn(pb);return0;}調(diào)試結(jié)果測(cè)試的數(shù)據(jù)及結(jié)果算法的時(shí)間復(fù)雜度及改良算法的時(shí)間復(fù)雜度：一元多