算法与数据结构实验报告实验一-完成多项式的相加运算

实验一：完成多项式的相加运算（验证性、4学时）一、实验目的完成多项式的相加、相乘运算。（1）掌握线性表的插入、删除、查找等基本操作设计与实现（2）学习利用线性表提供的接口去求解实际问题（3）熟悉线性表的的存储方法二、实验内容设计一个一元多项式的简单计算程序，其基本功能有：（1）输入并建立多项式；（2）输出多项式；（3）多项式的相加运算。利用单链表实现。三、算法描述及实验步骤1描述1、创建两个单链表A、B，分别调用CreatePolyn（）；2、输出多项式，分别调用PrintPolyn（）；3、多项式相加运算AddPolyn（）。2算法流程图546inputA-B546inputA-BinputA-BinputA-Bend3代码(注释)#include<stdio.h>#include<malloc.h>#include<math.h>typedefstructPolynomial{floatcoef;//系数变量intexp;//指数变量structPolynomial*next;//定义next指针}*Polyn,Polynomial;//Polyn为结点指针类型voidInsert(Polynp,Polynh)//插入新的结点p{if(p->coef==0)free(p);//系数为0的话释放结点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)//将指数相同相合并{q2->coef+=p->coef;free(p);if(!q2->coef)//系数为0的话释放结点{q1->next=q2->next;free(q2);}}else//指数为新时将结点插入{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、项数为m的一元多项式{inti;Polynp;p=head=(Polyn)malloc(sizeof(structPolynomial));head->next=NULL;for(i=0;i<m;i++){p=(Polyn)malloc(sizeof(structPolynomial));//建立新结点以接收数据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);//调用Insert函数插入结点}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;//项数计数器if(!q)//若多项式为空，输出0{putchar('0');printf("\n");return;}while(q){if(q->coef>0&&flag!=1)putchar('+');//系数大于0且不是第一项if(q->coef!=1&&q->coef!=-1)//系数非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));//建立头结点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);//当相加系数为0时，释放该结点}//whilereturnheadc;}//AddPolynPolynSubtractPolyn(Polynpa,Polynpb){//求解并建立多项式A-B，返回其头指针Polynh=pb;Polynp=pb->next;Polynpd;while(p){//将pb的系数取反p->coef*=-1;p=p->next;}pd=AddPolyn(pa,h);for(p=h->next;p;p=p->next)//恢复pb的系数p->coef*=-1;returnpd;}//SubtractPolynPolynMultiplyPolyn(Polynpa,Polynpb){//求解并建立多项式A*B，返回其头指针Polynhf,pf;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点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);//调用Insert函数以合并指数相同的项}}returnhf;}//MultiplyPolynvoidDevicePolyn(Polynpa,Polynpb){//求解并建立多项式A/B，返回其头指针Polynhf,pf,af,temp1,temp2,q;Polynqa=pa->next;Polynqb=pb->next;hf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点,存储商hf->next=NULL;pf=(Polyn)malloc(sizeof(structPolynomial));//建立头结点，存储余数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