c语言一元多项式的相加

1. 问题描述 设计一个程序实现两个一元稀疏多项式的表示及基本操作（建立、销毁、输出、加法、减法等操作）。 2. 算法设计 根据一元多项式相加的运算规则：对于两个一元多项式中所有指数相同的项，对应指数相加（减），若其和（差）不为零，则构成“和（差）多项式”中的一项；对于两个一元多 项式中所有指数不相同的项，则分别写到“和（差）多项式”中去。因为多项式指数最高项以及项数是不确定的，因此采用线性链表的存储结构便于实现一元多项式的运算。 （假定用户输入的一元多项式系数从小到大）本程序在构建两个链表完后复制这两个链表，用户输入一个一元多项式完毕后，即会在屏幕上打印出相应的一元多项 式，输入两个一元多项式完毕后，屏幕上会显示响应的功能选择（任意一个功能只能用一次），用户输入1或2分别完成加法或减法操作，输入3退出程序。 3. 算法实现 系统的运行环境： DevC++ 源代码： #include<stdio.h> #include<stdlib.h> //相加前提 //假定用户输入从小到大 typedef struct polynomial{ int coef;//系数 int expn;//指数 struct polynomial *next; }polynomial; polynomial* Copypolynomial(polynomial* h); void InsFirstsubtract(polynomial *head,polynomial *p,polynomial *q); void InsFirstadd(polynomial *head,polynomial *p,polynomial *q); void Insertpolynomial(polynomial* head1,polynomial* s); void Destroypolynomial(polynomial* head); void Deletepolynomial(polynomial *head,polynomial *p); void Union1(polynomial *h1,polynomial *h2); void Union(polynomial *h1,polynomial *h2); void subtractpolynomial(polynomial *head1,polynomial *head2); void addpolynomial(polynomial *head1,polynomial *head2); int ListEmpty(polynomial *head); void Displaypolynomial(polynomial* h1); void SetCurElem(polynomial *p,int sum); int cmp( polynomial *p,polynomial *q); polynomial* Createpolynomial() { int i=0,j=0,c=0,e=0; polynomial *p,*head; head=(polynomial*)malloc(sizeof(polynomial)); p=head; scanf("%d",&i); for(j=1;j<=i;j++) { // 给个头指针 这个非常重要 表创建正确是第一步 //printf("请分别输入系数和指数，中间用逗号隔开"); p->next=(polynomial*)malloc(sizeof(polynomial)); p=p->next;//指针没有赋值好 printf("系数和指数（中间用空格隔开）:"); scanf("%d %d",&c,&e);//这个中间只能是空格不能是逗号 逗号第二个数据输入不进去 p->coef=c; p->expn=e; p->next=(polynomial*)malloc(sizeof(polynomial)); } p->next=NULL; return head; } polynomial* Copypolynomial(polynomial* h) { polynomial *p,*head; polynomial *q=h->next; head=(polynomial*)malloc(sizeof(polynomial)); p=head;; while(q!=NULL) { // 给个头指针 这个非常重要 表创建正确是第一步 //printf("请分别输入系数和指数，中间用逗号隔开"); p->next=(polynomial*)malloc(sizeof(polynomial)); p=p->next;//指针没有赋值好 p->coef=q->coef; p->expn=q->expn; q=q->next; } p->next=NULL; return head; } void InsFirstsubtract(polynomial *head,polynomial *p,polynomial *q){ polynomial *s=head; while(s->next!=p) { s=s->next; } q->coef=(q->coef)*-1; q->next=s->next; s->next=q; //错误代码 引起重视 /*之前 r=s->next; r==(polynomial*)malloc(sizeof(polynomial));; r->coef=q->coef; r->expn=q->expn; r->next=p;*/ } void InsFirstadd(polynomial *head,polynomial *p,polynomial *q){ polynomial *s=head; while(s->next!=p) { s=s->next; } q->next=s->next; s->next=q; //错误代码 引起重视 /*之前 r=s->next; r==(polynomial*)malloc(sizeof(polynomial));; r->coef=q->coef; r->expn=q->expn; r->next=p;*/ } void SetCurElem(polynomial *p,int sum) { p->coef=sum; } int cmp(polynomial *p,polynomial *q) { int a=p->expn; int b=q->expn; if(a<b) return -1; else if(a==b) return 0; else return 1; } void subtractpolynomial(polynomial *head1,polynomial *head2){ polynomial *p=head1->next; polynomial *q=head2->next; polynomial *t=NULL; int sum=0; while(p!=NULL&&q!=NULL){ switch(cmp(p,q)){ //A链指数小，那就让A链后移 //加了个pre=p case -1:p=p->next; break; case 0: sum=(p->coef)+((q->coef)*-1); if(sum!=0) { //y=q; SetCurElem(p,sum); p=p->next; q=q->next; //Deletepolynomial(head2,y); } else { t=p; p=p->next; Deletepolynomial(head1,t); //t=q; q=q->next; //Deletepolynomial(head1,t); } break; //A链指数大，那就让B链插入到A链当前节点之前，B链后移并释放B链当前节点 case 1: //在此必须首先让一个遍历指针记住B表待插入节点的下一个节点 t=q; q=q->next; //Deletepolynomial(head2,t); InsFirstsubtract(head1,p,t); break; default: break; } } //这里一定要注意 如果后面有，要让B表后面的系数是负数 if(!ListEmpty(head2)){ Union1(head1,q); //尾插法 //Destroypolynomial(head2); } } void addpolynomial(polynomial *head1,polynomial *head2){ polynomial *p=head1->next; polynomial *q=head2->next; polynomial *t=NULL,*s=NULL; int sum=0; while(p!=NULL&&q!=NULL){ switch(cmp(p,q)){ //A链指数小，那就让A链后移 //加了个pre=p case -1:p=p->next;break; case 0: sum=(p->coef)+(q->coef); if(sum!=0) { //y=q; SetCurElem(p,sum); p=p->next; q=q->next; //Deletepolynomial(head2,y); } else { t=p; p=p->next; Deletepolynomial(head1,t); // t=q; q=q->next; //Deletepolynomial(head2,t); } break; //A链指数大，那就让B链插入到A链当前节点之前，B链后移并释放B链当前节点 case 1: //在此必须首先让一个遍历指针记住B表待插入节点的下一个节点 //Deletepolynomial(head2,t); t=q; q=q->next; //特别注意前插的指针记下来，然后出现在参数列表中 InsFirstadd(head1,p,t); break; default: break; } } if(!ListEmpty(head2)){ Union(head1,q); //尾插法 //Destroypolynomial(head2); } } void Union(polynomial *h1,polynomial *h2) { polynomial *p=h1->next,*q=h2; while(q!=NULL) { Insertpolynomial(h1,q); q=q->next; } } void Union1(polynomial *h1,polynomial *h2) { polynomial *p=h1->next,*q=h2; while(q!=NULL) { q->coef=-1*(q->coef); Insertpolynomial(h1,q); q=q->next; } } void Insertpolynomial(polynomial* head1,polynomial* s){ polynomial *q=head1->next,*p=head1->next;//连续定义两个指针变量是这样定义的 注意 while(q->next!=NULL) q=q->next; q->next=(polynomial*)malloc(sizeof(polynomial));//这里注意需要个指针变量 否则next太多了 p=q->next; p->coef=s->coef; p->expn=s->expn; p->next=NULL; } int ListEmpty(polynomial *head){ if(head!=NULL) return 0; } void Deletepolynomial(polynomial* head,polynomial* p){ polynomial *q=head,*s=p; while(q->next!=s) { q=q->next; } q->next=s->next; free(s); } void Destroypolynomial(polynomial* head){ polynomial *p,*q; p=head; while(p!=NULL) { q=p->next; free(p); p=q; } head=NULL; } void Displaypolynomial(polynomial* h1) { if(h1->next!=NULL) { polynomial *p=h1->next; printf("%dX^%d",p->coef,p->expn); p=p->next; while(p!=NULL)//判断条件错误 { if(p->coef>0) {printf("+"); } else{} printf("%dX^%d",p->coef,p->expn); p=p->next; } } else{ printf("两式子相减已为零,无法输出!!"); } } /*int PolynomialLength(polynomial* head) { polynomial *p=head; int o=0; while(p->next!=NULL){ o++; p=p->next; //这里少个指针移动 } return o; }*/ int main(){ int y; int flag; polynomial *h1=NULL,*h2=NULL,*h3=NULL,*h4=NULL; printf("请输入第一个多项式的节点个数"); h1=Createpolynomial(); printf("多项式A为："); Displaypolynomial(h1); h3=Copypolynomial(h1); printf("\n"); printf("请输入第二个多项式的节点个数"); h2=Createpolynomial(); printf("多项式B为："); Displaypolynomial(h2); h4=Copypolynomial(h2); printf("\n"); for(;;) /*实现反复输入选择*/{ printf("┏━━━━━━━━━━━━━━━━━━┓\n"); printf("┃请选择您要进行的操作： ┃\n"); printf("┃ 1.输出多项式A+B ┃\n"); printf("┃ 2.输出多项式A-B ┃\n"); printf("┃ 3.退出 ┃\n"); printf("┗━━━━━━━━━━━━━━━━━━┛\n"); fflush(stdin); scanf("%d",&flag); if(flag==1) { printf("多项式A+B为:"); addpolynomial(h1,h2); Displaypolynomial(h1); printf("\n"); } else if(flag==2){ printf("多项式A-B为:"); subtractpolynomial(h3,h4); Displaypolynomial(h3); printf("\n"); } else if(flag==3){ printf("\n"); printf("━━━━━━━感谢使用 ━━━━━━━━\n"); break; } else { printf("━━━━输入错误.请重新输入！━━━━━\n"); } } return 0; } 4. 心得体会 充分体会到设计一个程序一定要细致，再细致，在C的指针这里指针如果不小心，就非常容易乱指，要在每次调用函数时用指针特别注意，一个完美的程序是需要不断的用心 当作自己的孩子一样去构造它，要考虑的方面很多，例如效率，与用户交互效果好，当前阶段最重要的还是要多敲代码，多练习，发现问题，解决问题的一个过程，本次的实验 让我认识到要想设计一个好的程序，不仅要有好的技术基础，更要站在用户使用的角度上去想问题，让用户喜欢。以后的路还很长，持之以恒，永不满足！ 5. 参考文献 数据结构（C语言版）严蔚敏