數(shù)據(jù)結構與算法課程設計說明書-一元多項式的加法.減法的實現(xiàn)

PAGEPAGE2數(shù)據(jù)結構與算法課程設計說明書

設計題目：一元多項式的加法.減法的實現(xiàn)需求分析功能：首先建立一個有序鏈表，輸入一個多項式，進行降冪排列。接著判斷進行加減乘哪種運算，再輸入一個多項式進行運算.2概要設計a．建立多項式鏈表輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表P。依次輸入m個非零項，生成結點并插入鏈表。再在界面上輸入n個非零項的系數(shù)和指數(shù)structterm*CreatPolyn(structterm*P,intm){//輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表Pinti; structterm*h=P=(structterm*)malloc(sizeof(structterm)),*q;if(m<=0)returnNULL;P->coef=0.0;printf("依次輸入%d個非零項\n",m);for(i=1;i<=m;++i){//依次輸入m個非零項scanf("%f%d",&P->coef,&P->expn);if(P->coef)q=P;P=P->next=(structterm*)malloc(sizeof(structterm));}q->next=NULL;free(P);returnh;}//CreatPolynb．多項式加法利用兩個多項式的結點構成“和多項式”，Pa=Pa+Pb.structterm*APolyn(structterm*Pa,structterm*Pb){//多項式加法：Pa=Pa＋Pb，利用兩個多項式的結點構成"和多項式"。structterm*h,*qa=Pa,*qb=Pb,*p,*q;floatsum;h=p=(structterm*)malloc(sizeof(structterm));p->next=NULL;while(qa&&qb){//Pa和Pb均非空switch(Compare(qa,qb)){case-1://多項式PA中當前結點的指數(shù)值小p->next=qb;p=qb;qb=qb->next;break;case0://兩者的指數(shù)值相等sum=qa->coef+qb->coef;if(sum!=0.0){//修改多項式PA中當前結點的系數(shù)值p->next=qa;qa->coef=sum;p=qa;qa=qa->next;}else{//刪除多項式PA中當前結點q=qa;qa=qa->next;free(q);}q=qb;qb=qb->next;free(q);break;case1://多項式PB中當前結點的指數(shù)值小p->next=qa;p=qa;qa=qa->next;break;}//switch}//whileif(Pa)p->next=qa;//鏈接Pa中剩余結點if(Pb)p->next=qb;//鏈接Pb中剩余結點q=h;h=h->next;free(q);returnh;}//APolync．多項式減法Pa=Pa-Pb，利用兩個多項式的結點構成"差多項式"。structterm*BPolyn(structterm*Pa,structterm*Pb){//多項式減法：Pa=Pa-Pb，利用兩個多項式的結點構成"差多項式"。structterm*p=Pb;while(p){p->coef*=-1;p=p->next;}returnAPolyn(Pa,Pb);}//BPolynd．多項式乘法多項式乘法：Pa=Pa*Pb，利用兩個多項式的結點構成"積多項式"。tructterm*CPolyn(structterm*Pa,structterm*Pb){//多項式乘法：Pa=Pa*Pb，利用兩個多項式的結點構成"積多項式"。structterm*pa=Pa,*p,*q,*r,*s,*t;r=p=(structterm*)malloc(sizeof(structterm));if(!Pb)returnNULL;while(pa){p->coef=pa->coef;p->expn=pa->expn;q=p;p=p->next=(structterm*)malloc(sizeof(structterm));pa=pa->next;}q->next=NULL;free(p);pa=Pa;t=s=(structterm*)malloc(sizeof(structterm));while(pa){q=s;s=s->next=(structterm*)malloc(sizeof(structterm));pa=pa->next;}q->next=NULL;free(s);pa=Pa;while(pa){pa->coef*=Pb->coef;pa->expn+=Pb->expn;pa=pa->next;}Pb=Pb->next;while(Pb){p=r;s=t;while(p){s->coef=p->coef*Pb->coef;s->expn=p->expn+Pb->expn;p=p->next;s=s->next;}Pa=APolyn(Pa,t);Pb=Pb->next;}returnPa;}//CPolyne．主函數(shù)建立主函數(shù)界面，實現(xiàn)加、減、乘主要功能。界面運算由輸入第一個一元多項式開始，逐步實現(xiàn)多項式計算。voidmain(){structterm*M,*N;chars[2];inti,n;puts("一元多項式計算:\n輸入一一元多項式的項數(shù)");scanf("%d",&n);M=CreatPolyn(M,n);M=selsort(M);PrintfPoly(M);p:puts("\n1:加\n2:減\n3:乘\n4:退出");getchar();q:gets(s);if(s[1]!='\0'||!isdigit(*s)){puts("輸入有誤,請重新輸入!");gotoq;}i=*s-48;switch(i){case1:M=A(M,N);gotop;;case2:M=B(M,N);gotop;;case3:M=C(M,N);gotop;case4:break;default:puts("輸入有誤,請重新輸入!");gotoq;}}3詳細設計#include<stdlib.h>#include<stdio.h>#include<ctype.h>typedefstructterm{//項的表示，多項式的項作為LinkList的數(shù)據(jù)元素floatcoef;//系數(shù)intexpn;//指數(shù)structterm*next;}term;structterm*CreatPolyn(structterm*P,intm){//輸入m項的系數(shù)和指數(shù)，建立表示一元多項式的有序鏈表Pinti;structterm*h=P=(structterm*)malloc(sizeof(structterm)),*q;if(m<=0)returnNULL;P->coef=0.0;printf("依次輸入%d個非零項\n",m);for(i=1;i<=m;++i){//依次輸入m個非零項scanf("%f%d",&P->coef,&P->expn);if(P->coef)q=P;P=P->next=(structterm*)malloc(sizeof(structterm));}q->next=NULL;free(P);returnh;}//CreatPolynstructterm*selsort(structterm*h){structterm*g,*p,*q;floatf;inti,fini=1;if(!h)returnNULL;for(g=h;g->next&&fini;g=g->next){fini=0;for(p=h,q=h->next;q;p=p->next,q=q->next)if(p->expn<q->expn){f=p->coef;i=p->expn;p->coef=q->coef;p->expn=q->expn;q->coef=f;q->expn=i;fini=1;}}for(g=h,p=g->next;p;)if(g->expn==p->expn){g->coef+=p->coef;g->next=p->next;q=p;p=p->next;free(q);}elseif(g->next){g=g->next;p=p->next;}returnh;}PrintfPoly(structterm*P){structterm*q=P;if(!q){putchar('0');return;}if(q->coef!=1){printf("%g",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn);}elseif(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);q=q->next;while(q){if(q->coef>0)putchar('+');if(q->coef!=1){printf("%g",q->coef);if(q->expn==1)putchar('X');elseif(q->expn)printf("X^%d",q->expn);}elseif(!q->expn)putchar('1');elseif(q->expn==1)putchar('X');elseprintf("X^%d",q->expn);q=q->next;}}Compare(structterm*a,structterm*b){if(a->expn<b->expn)return-1;if(a->expn>b->expn)return1;return0;}structterm*APolyn(structterm*Pa,structterm*Pb){//多項式加法：Pa=Pa＋Pb，利用兩個多項式的結點構成"和多項式"。structterm*h,*qa=Pa,*qb=Pb,*p,*q;floatsum;h=p=(structterm*)malloc(sizeof(structterm));p->next=NULL;while(qa&&qb){//Pa和Pb均非空switch(Compare(qa,qb)){case-1://多項式PA中當前結點的指數(shù)值小p->next=qb;p=qb;qb=qb->next;break;case0://兩者的指數(shù)值相等sum=qa->coef+qb->coef;if(sum!=0.0){//修改多項式PA中當前結點的系數(shù)值p->next=qa;qa->coef=sum;p=qa;qa=qa->next;}else{//刪除多項式PA中當前結點q=qa;qa=qa->next;free(q);}q=qb;qb=qb->next;free(q);break;case1://多項式PB中當前結點的指數(shù)值小p->next=qa;p=qa;qa=qa->next;break;}//switch}//whileif(Pa)p->next=qa;//鏈接Pa中剩余結點if(Pb)p->next=qb;//鏈接Pb中剩余結點q=h;h=h->next;free(q);returnh;}//APolynstructterm*A(structterm*Pa,structterm*Pb){intn;puts("再輸入一一元多項式的項數(shù)");scanf("%d",&n);Pb=CreatPolyn(Pb,n);Pb=selsort(Pb);PrintfPoly(Pa);if(Pb&&Pb->coef>0)printf("+");PrintfPoly(Pb);Pa=APolyn(Pa,Pb);printf("=");Pa=selsort(Pa);PrintfPoly(Pa);returnPa;}structterm*BPolyn(structterm*Pa,structterm*Pb){//多項式減法：Pa=Pa-Pb，利用兩個多項式的結點構成"差多項式"。structterm*p=Pb;while(p){p->coef*=-1;p=p->next;}returnAPolyn(Pa,Pb);}//BPolynstructterm*B(structterm*Pa,structterm*Pb){intn;puts("再輸入一一元多項式的項數(shù)");scanf("%d",&n);Pb=CreatPolyn(Pb,n);Pb=selsort(Pb);PrintfPoly(Pa);printf("-");putchar('(');PrintfPoly(Pb);putchar(')');Pa=BPolyn(Pa,Pb);printf("=");Pa=selsort(Pa);PrintfPoly(Pa);returnPa;}structterm*CPolyn(structterm*Pa,structterm*Pb){//多項式乘法：Pa=Pa*Pb，利用兩個多項式的結點構成"積多項式"。structterm*pa=Pa,*p,*q,*r,*s,*t;r=p=(structterm*)malloc(sizeof(structterm));if(!Pb)returnNULL;while(pa){p->coef=pa->coef;p->expn=pa->expn;q=p;p=p->next=(structterm*)malloc(sizeof(structterm));pa=pa->next;}q->next=NULL;free(p);pa=Pa;t=s=(structterm*)malloc(sizeof(structterm));while(pa){q=s;s=s->next=(structterm*)malloc(sizeof(structterm));pa=pa->next;}q->next=NULL;free(s);pa=Pa;while(pa){pa->coef*=Pb->coef;pa->expn+=Pb->expn;pa=pa->next;}Pb=Pb->next;while(Pb){p=r;s=t;while(p){s->coef=p->coef*Pb->coef;s->expn=p->expn+Pb->expn;p=p->next;s=s->next;}Pa=APolyn(Pa,t);Pb=Pb->next;}returnPa;}//CPolynstructterm*C(structterm*Pa,structterm*Pb){intn;puts("再輸入一一元多項式的項數(shù)");s