算法與數(shù)據(jù)結(jié)構(gòu)實驗報告實驗一-完成多項式的相加運算

實驗一：完成多項式的相加運算（驗證性、4學(xué)時）一、實驗?zāi)康耐瓿啥囗検降南嗉?、相乘運算。（1）掌握線性表的插入、刪除、查找等基本操作設(shè)計與實現(xiàn)（2）學(xué)習(xí)利用線性表提供的接口去求解實際問題（3）熟悉線性表的的存儲方法二、實驗內(nèi)容設(shè)計一個一元多項式的簡單計算程序，其基本功能有：（1）輸入并建立多項式；（2）輸出多項式；（3）多項式的相加運算。利用單鏈表實現(xiàn)。三、算法描述及實驗步驟1描述1、創(chuàng)建兩個單鏈表A、B，分別調(diào)用CreatePolyn（）；2、輸出多項式，分別調(diào)用PrintPolyn（）；3、多項式相加運算AddPolyn（）。2算法流程圖546inputA-B546inputA-BinputA-BinputA-Bend3代碼(注釋)#include<stdio.h>#include<malloc.h>#include<math.h>typedefstructPolynomial{floatcoef;//系數(shù)變量intexp;//指數(shù)變量structPolynomial*next;//定義next指針}*Polyn,Polynomial;//Polyn為結(jié)點指針類型voidInsert(Polynp,Polynh)//插入新的結(jié)點p{if(p->coef==0)free(p);//系數(shù)為0的話釋放結(jié)點else{Polynq1,q2;q1=h;q2=h->next;while(q2&&p->exp<q2->exp)//查找插入位置{q1=q2;q2=q2->next;}if(q2&&p->exp==q2->exp)//將指數(shù)相同相合并{q2->coef+=p->coef;free(p);if(!q2->coef)//系數(shù)為0的話釋放結(jié)點{q1->next=q2->next;free(q2);}}else//指數(shù)為新時將結(jié)點插入{p->next=q2;q1->next=p;}}}//Insertintf(floatx)//判斷輸入是否為整形{floata;a=x-(longint)x;if(a==0&&x==fabs(x))return1;elsereturn0;}PolynCreatePolyn(Polynhead,intm)//建立一個頭指針為head、項數(shù)為m的一元多項式{inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新結(jié)點以接收數(shù)據(jù)printf("pleaseinputNO.%dcoefandexp:",i+1);scanf("%f%d",&p->coef,&p->exp);while(!f(p->coef)&&!f(p->exp)){printf("輸入有錯，請重新輸入:");scanf("%f%d",&p->coef,&p->exp);}Insert(p,head);//調(diào)用Insert函數(shù)插入結(jié)點}returnhead;}//CreatePolynvoidDestroyPolyn(Polynp)//銷毀多項式p{Polynq1,q2;q1=p->next;q2=q1->next;while(q1->next){free(q1);q1=q2;//指針后移q2=q2->next;}}voidPrintPolyn(PolynP)//輸出多項式{Polynq=P->next;intflag=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的普通情況{printf("%g",q->coef);if(q->exp==1)putchar('X');elseif(q->exp)printf("X^%d",q->exp);}else{if(q->coef==1){if(!q->exp)putchar('1');elseif(q->exp==1)putchar('X');elseprintf("X^%d",q->exp);}if(q->coef==-1){if(!q->exp)printf("-1");elseif(q->exp==1)printf("-X");elseprintf("-X^%d",q->exp);}}q=q->next;flag++;}//whileprintf("\n");}//PrintPolynintcompare(Polyna,Polynb){if(a&&b){if(!b||a->exp>b->exp)return1;elseif(!a||a->exp<b->exp)return-1;elsereturn0;}elseif(!a&&b)return-1;//A多項式已空，但B多項式非空elsereturn1;//B多項式已空，但A多項式非空}//comparePolynAddPolyn(Polynpa,Polynpb)//求解并建立多項式A+B，返回其頭指針{Polynqa=pa->next;Polynqb=pb->next;Polynheadc,hc,qc;hc=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點hc->next=NULL;headc=hc;while(qa||qb){qc=(Polyn)malloc(sizeof(structPolynomial));switch(compare(qa,qb))//功能選擇{case1:{qc->coef=qa->coef;qc->exp=qa->exp;qa=qa->next;break;}case0:{qc->coef=qa->coef+qb->coef;qc->exp=qa->exp;qa=qa->next;qb=qb->next;break;}case-1:{qc->coef=qb->coef;qc->exp=qb->exp;qb=qb->next;break;}}//switchif(qc->coef!=0){qc->next=hc->next;hc->next=qc;hc=qc;}elsefree(qc);//當(dāng)相加系數(shù)為0時，釋放該結(jié)點}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多項式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;}//SubtractPolynPolynMultiplyPolyn(Polynpa,Polynpb){//求解并建立多項式A*B，返回其頭指針Polynhf,pf;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點hf->next=NULL;for(;qa;qa=qa->next){for(qb=pb->next;qb;qb=qb->next){pf=(Polyn)malloc(sizeof(structPolynomial));pf->coef=qa->coef*qb->coef;pf->exp=qa->exp+qb->exp;Insert(pf,hf);//調(diào)用Insert函數(shù)以合并指數(shù)相同的項}}returnhf;}//MultiplyPolynvoidDevicePolyn(Polynpa,Polynpb){//求解并建立多項式A/B，返回其頭指針Polynhf,pf,af,temp1,temp2,q;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點,存儲商hf->next=NULL;pf=(Polyn)malloc(sizeof(structPolynomial));//建立頭結(jié)點，存儲余數(shù)pf->next=NULL;temp1=(Polyn)malloc(sizeof(structPolynomial));temp1->next=NULL;temp2=(Polyn)malloc(sizeof(structPolynomial));temp2->next=NULL;temp1=AddPolyn(temp1,pa);while(qa!=NULL&&qa->exp>=qb->exp){temp2->next=(Polyn)malloc(sizeof(structPolynomial));temp2->next->coef=(qa->coef)/(qb->coef);temp2->next->exp=(qa->exp)-(qb->exp);Insert(temp2->next,hf);pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2));qa=pa->next;temp2->next=NULL;}pf=SubtractPolyn(temp1,MultiplyPolyn(hf,pb));pb=temp1;printf("thequotientis:");PrintPolyn(hf);printf("theremainderis:");PrintPolyn(pf);}//DevicePolynintmain(){intm,n,flag=0;floatx;Polynpa=0,pb=0,pc,pd,pe,pf;//定義各式的頭指針，pa與pb在使用前付初值NULLprintf("pleaseinputAnumber:");scanf("%d",&m);pa=CreatePolyn(pa,m);//建立多項式Aprintf("pleaseinputBnumber:");scanf("%d",&n);pb=CreatePolyn(pb,n);//建立多項式B//輸出菜單printf("**********************************************\n");printf("choise：\n\t1.OutputAandB\n\t2.CreatePolynA+B\n");printf("\t3.CreatePolynA-B\n\t4.CreatePolynA*B\n");printf("\t5.CreatePolynA/B\n\t6.Return\n**********************************************\n");for(;;flag=0){printf("choise");scanf("%d",&flag);if(flag==1){printf("多項式A：");PrintPolyn(pa);printf("多項式B：");PrintPolyn(pb);continue;}if(flag==2){pc=AddPolyn(pa,pb);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){pf=MultiplyPolyn(pa,pb);printf("多項式a*b：");PrintPolyn(pf);DestroyPolyn(pf);continue;}if(flag==5){DevicePolyn(pa,pb);continue;}if(flag==6)break;if(flag<1||flag>6)printf("Error!!!\n");continue;}//forDestroyPolyn(pa);DestroyPo