数据结构课程设计----一元稀疏多项式计算器

#include<stdio.h> #include<stdlib.h> #include<math.h> typedef int Status; #define OK 1; #define ERROR 0; typedef struct polynode //多项式节点定义 { float coe; //项的系数 int exp; //项的指数 struct polynode *next; //指向下一项的指针 }*polynomail,polynode; polynomail CreatPolyn(polynomail p,int m) { //输入m项的系数和指数，建立表示多项式的有序链表 float c; int e,i=1; polynomail h=NULL,s,r; if(m<=0) return ERROR; //输入项数小于0，出错 while(i<=m) { printf("输入第%d项的系数：",i); scanf("%f",&c); printf("输入第%d项的指数：",i); scanf("%d",&e); if(c==0) //若输入系数为0，不建立节点直接跳过 { i++; continue; } if(!h) //头结点不存在则建立第一项 { h=(polynomail)malloc(sizeof(polynode)); if(!h) return ERROR; h->coe=c; h->exp=e; h->next=NULL; } else { r=h; if(e>h->exp) //若输入系数大于链表的第一项，直接插到第一项前 { s=(polynomail)malloc(sizeof(polynode)); if(!s) return ERROR; s->coe=c; s->exp=e; s->next=h; h=s; } else if(h->exp == e) //输入系数等于链表第一项，与第一项的系数相加 { h->coe+=c; if(h->coe==0) { if(h->next) { h=h->next; free(r); } else { free(h); h=NULL; } } } else { while(r->next && r->next->exp > e ) //在链表中找到第一个系数小于等于输入系数的节点 { r=r->next; } if(r->next && r->next->exp == e)//若与找到的节点系数相等则合并 { r->next->coe+=c; if(r->next->coe==0) { polynomail k; k=r->next; r->next=k->next; free(k); } } else //不相等则插到这个节点之前 { s=(polynomail)malloc(sizeof(polynode)); if(!s) return ERROR; s->coe=c; s->exp=e; s->next=r->next; r->next=s; } } } i++; } p=h; return p; } void DestoryPolyn(polynomail p) //销毁多项式 { polynomail q; while(p) { q=p->next; free(p); p=q; } } polynomail AddPolyn(polynomail pa,polynomail pb) { polynomail qa,qb,h; h=qa=pa; if(!pa) return pb; while(pa && pb) { if(pa->exp==pb->exp) //若系数相等则合并 { pa->coe+=pb->coe; qb=pb->next; free(pb); pb=qb; if(pa->coe==0) //若系数为零，则删除这个节点 { if(h==pa) { h=qa=pa->next; free(pa); pa=qa; } else { qa->next=pa->next; free(pa); pa=qa->next; } } } else if(pb->exp > pa->exp) //若pb的系数大于pa的系数，将pb节点插到pa之前 { qb=pb->next; pb->next=pa; if(h==pa) { h=qa=pa=pb; pb=qb; } else { qa->next=pb; qa=pb; pb=qb; } } else //若pb系数小于pa，则移动pa指针 { if(h!=pa) qa=qa->next; pa=pa->next; } } if(pa==NULL) //将pb剩下的项接到pa之后 { if(qa==NULL) //若pa、qa同时为空，则结果为0，返回NULL return h; qa->next=pb; } return h; } polynomail SubPolyn(polynomail pa,polynomail pb) //多项式减法 { polynomail qb; qb=pb; while(qb) //将多项式各项取反，然后做加法 { qb->coe=-qb->coe; qb=qb->next; } return AddPolyn(pa,pb); } void PrintPolyn(polynomail p) //按指数降序输出多项式 { if(!p) { printf("0\n"); } else { /*输出第一项*/ if(p->exp==0) { if(fabs(p->coe)==1.0) printf(p->coe>0?"1 ":"-1 "); else printf(p->coe>0?"%g ":"-%g ",fabs(p->coe)); } else if(p->exp==1) { if(fabs(p->coe)==1.0) printf(p->coe>0?"X ":"-X "); else printf(p->coe>0?"%gX ":"-%gX ",fabs(p->coe)); } else { if(fabs(p->coe)==1.0) printf(p->coe>0?"X^%d ":"-X^%d ",p->exp); else printf(p->coe>0?"%g*X^%d ":"-%g*X^%d ",fabs(p->coe),p->exp); } p=p->next; /*输出其余项*/ while(p) { if(p->exp==0) { if(fabs(p->coe)==1.0) printf(p->coe>0?"+ 1 ":"- 1 "); else printf(p->coe>0?"+ %g ":"- %g ",fabs(p->coe)); } else if(p->exp==1) { if(fabs(p->coe)==1.0) printf(p->coe>0?"+ X ":"- X "); else printf(p->coe>0?"+ %gX ":"- %gX ",fabs(p->coe)); } else { if(fabs(p->coe)==1.0) printf(p->coe>0?"+ X^%d ":"- X^%d ",p->exp); else printf(p->coe>0?"+ %g*X^%d ":"- %g*X^%d ",fabs(p->coe),p->exp); } p=p->next; } printf("\n"); } } float CalculatePolyn(polynomail p,float x) //计算多项式在x处的值 { float s=0; if(!p) return 0; else { while(p) { s+=p->coe * pow(x,p->exp); p=p->next; } } return s; } polynomail DerivatePolyn(polynomail p) //对多项式求导，返回首指针 { polynomail h; if(!p) return NULL; else { h=p; p->coe*=p->exp; p->exp--; if(p->coe==0) { h=p->next; free(p); p=h; if(p) { p->coe*=p->exp; p->exp--; } } while(p->next) { p->next->coe *= p->next->exp; p->next->exp--; if(p->next->coe==0) { polynomail k; k=p->next; p->next=k->next; free(k); } else p=p->next; } } return h; } polynomail MultPolyn(polynomail pa,polynomail pb) //建立pa*pb多项式 { polynomail h=NULL,qa,qb,r,s; float c; int e; qa=pa;qb=pb; while(pa) { while(pb) { c=pa->coe*pb->coe; e=pa->exp+pb->exp; /*下同多项式的创建*/ if(c==0) //若输入系数为0，不建立节点直接跳过 { continue; } if(!h) //头结点不存在则建立第一项 { h=(polynomail)malloc(sizeof(polynode)); if(!h) return ERROR; h->coe=c; h->exp=e; h->next=NULL; } else { r=h; if(e>h->exp) //若输入系数大于链表的第一项，直接插到第一项前 { s=(polynomail)malloc(sizeof(polynode)); if(!s) return ERROR; s->coe=c; s->exp=e; s->next=h; h=s; } else if(h->exp == e) //输入系数等于链表第一项，与第一项的系数相加 { h->coe+=c; if(h->coe==0) { if(h->next) { h=h->next; free(r); } else { free(h); h=NULL; } } } else { while(r->next && r->next->exp > e ) //在链表中找到第一个系数小于等于输入系数的节点 { r=r->next; } if(r->next && r->next->exp == e)//若与找到的节点系数相等则合并 { r->next->coe+=c; if(r->next->coe==0) { polynomail k; k=r->next; r->next=k->next; free(k); } } else //不相等则插到这个节点之前 { s=(polynomail)malloc(sizeof(polynode)); if(!s) return ERROR; s->coe=c; s->exp=e; s->next=r->next; r->next=s; } } } pb=pb->next; } pb=qb; pa=pa->next; } return h; } int main() { polynomail pa,pb,h; int m,n; float s,x; while(1) { printf("**************一元多项式计算器**************\n"); printf("|-----------------功能选择-----------------|\n"); printf("|-------------- 1.多项式加法 --------------|\n"); printf("|-------------- 2.多项式减法 --------------|\n"); printf("|-------------- 3.多项式乘法 --------------|\n"); printf("|-------------- 4.计算多项式在X处的值------|\n"); printf("|-------------- 5.求多项式导数-------------|\n"); printf("|-------------- 0.退出---------------------|\n"); printf("|__________________________________________|\n"); printf("请输入功能的序号："); scanf("%d",&n); switch(n) { case 0: return 0; case 1: { printf("请输入多项式a的项数："); scanf("%d",&m); pa=CreatPolyn(pa,m); printf("多项式a为："); PrintPolyn(pa); printf("\n\n"); printf("请输入多项式b的项数："); scanf("%d",&m); pb=CreatPolyn(pb,m); printf("多项式b为："); PrintPolyn(pb); h=AddPolyn(pa,pb); printf("多项式a+b为："); PrintPolyn(h); printf("\n