多项式相乘C实现

1、页眉内容西安邮电大学数据结构设计报告题目：多项式相乘院系名称：计算机学院专业名称：软件工程班级:学生姓名：学号（8位）：指导教师：设计起止时间：.设计目的以动态单链表为存储结构，使用排序等操作实现多项式的乘法运算二.设计内容用一个单链表来表示一个一元多项式；在创建多项式的过程中，可以按指数的任意顺序输入，并且可在同一多项式中输 入指数相同的多个项；在进行乘法操作之前，输出参与操作的两个多项式。要求输出的多项式按指数升 序排列，同指数的多项合并，项数的正负号显示合理。对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；结果多项式要求以动态链表为存储结构，复用原多项式的结点空间；输出结果

2、多项式要求按指数升序排列， 同指数的多项要合并，项数的正负号要求 显示合理。三概要设计1 功能模块图；多项式链表升序排序函数PolylistPolysort(Polylisthead)根据幕次的高低排序的同时并合同类项，幕次相同的系数相加存入前项，释放合 并项中后者空间，若系数相加和为0则释放两项空间。多项式创建函数Polylistcreat()多项式相乘函数PolylistPolymul(PolylistLA,PolylistLB)输出函数voidpri nt(Polylisthead)分三种情况：系数输出、符号输出、指数输出四详细设计1.各功能函数的数据流程图Polys*rt()开head

3、->iext=mvemove->ne>p=q>n ext=p->n ext;While(1)retur nheadp=head->n ext;q=he ad;move=first;2.重点设计及束编码(1)多项式链表升序排序函数PolylistPolysort(Polylisthead) Poly no de*first,*move,*p,*q;/first移动指针move被移动项指针p,q临时指针 q=head;p=head->n ext;if(p=NULL)returnhead;/ 判断链表是否为空；first=p->n ext;p->

4、 next=NULL;move=first;while(move!=NULL)直接插入排序(链表排序)first=first- >n ext;if(p->exp=move->exp)/判断待插入项指数是否与首项相等；p->coef+=move->coef; 系数相加；free(move);释放空间；if(p->coef=0)/若系数相加和为0；q->n ext=p->n ext;free(p); /释放空间；elseif(p->exp>move->exp)判断待插入项指数是否大于第一个项的指数;head->n ext=mo

5、ve;move->n ext=p;elseif(p->next=NULL)判断下一项是否为空；p->n ext=move;move->n ext=NULL;待插入项指数插入位置在首末项之间；移动临时变量指针p,qp=p->n ext;while(1)if(p->exp=move->exp)/判断待插入项指数是否与首项相等；elseq=p;p->coef+=move->coef; 系数相加；free(move);/ 释放空间；if(p->coef=0)q->next=p->next;/若系数相加和为0; free(p);释放

6、空间；break; if(p->exp>move->exp)/判断待插入项指数是否大于当前项的指 数；q->n ext=move;move->n ext=p;break;if(p->next=NULL)判断下一项是否为空；I i 1p->n ext=move; move->n ext=NULL; break; q=p;/移动临时变量指针p,q；p=p->n ext;p=head->next;/使p,q指针重新指到初始化位置；q=head;move=first;i .： -returnhead;/返回头结点；(2) 多项式创建函数Pol

7、ylistcreat()Poly no de*head,*p,* newno de; /head 头指针 newno de 新结点指针 p：临时指 针变量intc,e;/ceof (系数)和 exp (指数)；head=(Poly no de*)malloc(sizeof(Poly no de);/开辟一个新结点，并使之成为头 结点；p=head;printf("nt请输入多项式中元素的系数和指数:n");scan f("%d%d",&c,&e);while(c|e)/ceof (系数)和 exp (指数)不全为 0；if(c=0)sca

8、nf("%d%d",&c,&e);continue;若 c 为 0，不开辟新结点；newn ode=(Poly node*)malloc(sizeof(Poly node);/开辟一个新结点； newno de->coef=c; newno de->exp=e; p->n ext=newno de;p=newno de;scanf("%d%d",&c,&e);/输入新结点的系数和指数；p->next=NULL;为最后的结点的next赋空；head=Polysort(head);/调用Polysort

9、排序函数对多项式链表进行降序排序；returnhead; /返回头结点；(3) 多项式相乘函数PolylistPolymul(PolylistLA,PolylistLB) Poly no de*head,*p,*q,*t,* newno de;/head:头指针 newno de新 结点指针 p,q,t: 临时指针变量；p=LA- >n ext;q=LB->n ext;head=(Poly no de*)malloc(sizeof(Poly no de);/开辟一个新结点，并使之成为新链表的头结点；t=head;while(p!=NULL)while(q!=NULL) newn o

10、de=(Poly no de*)malloc(sizeof(Poly no de);/开辟一个新结点； t->n ext=newno de;t=t- >n ext; t->coef=p->coef*q->coef;项之系数为LA,LB两项系数之积； t->exp=p->exp+q->exp;项之指数为LA,LB两项指数之和； q=q->n ext;p=p->next;/p 指针移动；q=LB->next;/q 指针复位为 LB->next ；t->next=NULL;为最后的结点的next赋空；head=Polyso

11、rt(head);/调用Polysort排序函数对多项式链表进行降序排序；returnhead;/返 回头结点；(4) 输出函数voidpri nt(Polylisthead)Polyno de*p;p=head->n ext;if(p=NULL)prin tf("0");elsewhile(p!=NULL)系数输出if(p->coef=-1)prin tf("-");elseif(p->coef!=1)prin tf("%d",p->coef);/符号输出if(p->exp!=0&&p-

12、>exp!=1)prin tf("XA");elseif(p->exp=1)prin tf("X");/指数输出if(p->exp=0&&( p->coef=-1|p->coef=1)prin tf("1");if(p->exp<0)prin tf("(%d)",p->exp);elseif(p->exp!=1 &&p->exp!=0)prin tf("%d",p->exp);p=p->n e

13、xt;if(p!=NULL&&p->coef>0)prin tf("+");prin tf("n");五测试数据及运行结果1 正常测试数据和运行结果2 异常测试数据及运行结果如输入的字符不是数字，则无法处理，女口： a2程序无法继续运行六调试情况，设计技巧及体会1 改进方案多项式相成这个程序缺少对异常的处理，如果用户输入一些异常的字符程序将无 法继续运行，甚至导致死机。改进：加入异常处理，将各种用户可能的输入都包含在内。2体会心得体会：此程序是使用链表完成的，一直以来比较习惯用顺序表，通过这个程 序加深了对链表的理解。程序的排

14、序部分较为复杂，根据幕次的高低排序的同时 并合了同类项，幕次相同的系数相加存入前项，释放合并项中后者空间，若系数 相加和为0则释放两项空间。其实想这段算法时很容易，真正实现却是相当不容 易，可能是平时写的代码太少，真正把思想转换成代码困难还是比较大。七参考文献C语言程序设计王曙燕主编科学出版社数据结构 C语言描述耿国华高等教育出版社数据结构严蔚敏清华大学出版社八.附录：#in clude<stdio.h>#in clude<stdlib.h>#in clude<malloc.h>typedefstructPo lynodein tcoef;/系数in tex

15、p;/指数structPo lyno de* next;Poly no de,*Polylist;/多项式链表升序排序PolylistPolysort(Polylisthead)Polynode*first,*move,*p,*q;/first移动指针变量move被移动项指针变量 p,q临时指针变量q=head;p=head->n ext;if(p=NULL)returnhead;判断链表是否为空；first=p->n ext;p-> next=NULL; move=first;while(move!=NULL)/直接插入排序(链表排序)first=first->n e

16、xt;if(p->exp=move->exp)/判断待插入项指数是否与首项相等；p->coef+=move->coef;/系数相加；free(move);/ 释放空间；if(p->coef=0)/若系数相加和为 0;q_>n ext=p->n ext;free(p);/释放空间； elseif(p->exp>move->exp)/判断待插入项指数是否大于第一个项的指数；head->n ext=move;move_>n ext=p; elseif(p-> next=NULL)判断下一项是否为空；p->n ext=

17、move;move->n ext=NULL;else/待插入项指数插入位置在首末项之间；q=p;/移动临时变量指针 p,qp=p->n ext;while(1) if(p->exp=move->exp)/判断待插入项指数是否与首项相等；p->coef+=move->coef;/ 系数相加； free(move);/ 释放空间；if(p_>coef=0) q-> next=p-> next;/若系数相加和为 0;free(p);/释放空间； break; if(p->exp>move->exp)判断待插入项指数是否大于当前项

18、的指数；q->n ext=move;move->n ext=p;break;if(p-> next=NULL)判断下一项是否为空；p->n ext=move;move->n ext=NULL;break;q=p;/移动临时变量指针 p,q ；p=p->n ext;p=head->next;/使p,q指针重新指到初始化位置；q=head;move=first;returnhead;/返回头结点；/多项式创建(头插法)Polylistcreat()Polynode*head,*p,*newnode;/head :头指针 newnode:新结点指针 p：临时

19、指针变量intc,e;/ceof(系数)和 exp (指数)；head=(Poly node*)malloc(sizeof(Poly node);/开辟一个新结点，并使之成为头结点；p=head;prin tf("nt请输入多项式中元素的系数和指数:n");scan f("%d%d",&c,& e);while(c|e)/ceof(系数)和 exp (指数)不全为 0 ；if(c=0)scanf("%d%d",&c,&e);continue; /若 c 为 0,不开辟新结点；newno de=(Po l

20、yno de*)malloc(sizeof(Po lyno de);/开辟一个新结点；newno de->coef=c;newno de->exp=e;p->n ext =newno de;p=newno de;scan f("%d%d",&c,& e);/输入新结点的系数和指数；p->next=NULL; 为最后的结点的next赋空；head=Polysort(head);/ 调用Polysort排序函数对多项式链表进行降序排序；returnhead; /返回头结点；/多项式相乘PolylistPolymul(PolylistLA,

21、PolylistLB)Polynode*head,*p,*q,*t,*newnode;/head:头指针 newnode:新结点指针 p,q,t :临时指针变量；p=LA- >n ext;q=LB->n ext;head=(Poly node*)malloc(sizeof(Poly node);/开辟一个新结点，并使之成为新链表的头结点；t=head;while(p!=NULL)while(q!=NULL)newno de=(Po lyno de*)malloc(sizeof(Po lyno de);/开辟一个新结点；t->n ext=newno de;t=t- >n

22、ext;t->coef=p->coef*q->coef;/项之系数为LA,LB两项系数之积；t->exp=p->exp+q->exp;项之指数为LA,LB两项指数之和；q=q_>n ext;p=p->n ext;/p指针移动；q=LB->next;/q指针复位为 LB->next ；t->next=NULL;为最后的结点的 next赋空；head=Polysort(head);/ 调用Polysort排序函数对多项式链表进行降序排序；returnhead;/ 返回头结点；/输出函数voidpri nt(Polylisthead)Polyno de*p;p=head->n ext;if(p=NULL)prin tf("0");elsewhile(p!=NULL)/系数输出if(p->coef=-1)prin tf("-");elseif(