多项式相乘C实现

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

2、果多项式要求按指数升序排列，同指数的多项要合并，项数的正负号要求显示合理。概要设计1 功能模块图;主函数main()调用 Polysort排)序创建多项式 LA=creat()调用print输出式La,LB 相乘 LC=Pol调用(PALB$排 序创建多项式 LB=creat()调用print输出LB调用Polort排序调用print输出LC2 各个模块详细的功能描述。多项式链表升序排序函数Polylist Polysort(Polylist head)根据幕次的高低排序的同时并合同类项，幕次相同的系数相加存入前项，释放合 并项中后者空间，若系数相加和为 0则释放两项空间。多项式创建函数Pol

3、ylist creat()多项式相乘函数Polylist Polymul(Polylist LA,Polylist LB)输出函数void prin t(Polylist head)分三种情况：系数输出、符号输出、指数输出四详细设计1.各功能函数的数据流程图Polysort(开始Yp-oef= 0q-n ext=p-n ext; free(p);Np-e=move-expp_oef+=mve_oefNp_ex=move_expp-iext=NULLyhea-iext=mve move-extp;hed-iext=mve move-extp;hhea-工NULLfirst=-iext; p-rt

4、=NULL; nove=fS;While(1)2 重点设计及编码retur n head结束p=head-n ext; q=head; move=first;(1)多项式链表升序排序函数Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first q=head;移动指针move被移动项指针p,q临时指针p=head-n ext;if(p=NULL) retur n head; first=p-n ext;p- next=NULL; move=first; while(move!=NULL)first=first- n e

5、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);/释放空间；else if(p-expmove-exp) /判断待插入项指数是否大于第一个项的指数; head-n ext=move; move-n ext=p;else if(p-next=NULL)/判断下一项是否为空；p-next=move; move-next=NULL; else/待插入项指数

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

7、NULL; break; q=p; p=p-next;/移动临时变量指针 p,q ； p=head-next; q=head; move=first;return head; ( 2 )多项式创建函数Polylist creat()Polynode *head,*p,*newnode;int c,e;/使 p,q 指针重新指到初始化位置；/返回头结点；/head：头指针newnode:新结点指针 p:临时指针变量 /ceof （系数）和exp （指数）;head=(Polynode *)malloc(sizeof(Polynode);/ 开辟一个新结点，并使之成为头结点；p=head;prin

8、tf(nt 请输入多项式中元素的系数和指数 :n);scanf(%d %d,&c,&e);while(c|e)/ceof (系数)和 exp (指数)不全为 0;if(c=0)scanf(%d %d,&c,&e);continue; /若 c 为 0，不开辟新结点； newnode=(Polynode *)malloc(sizeof(Polynode);/ 开辟一个新结点； newnode-coef=c;newnode-exp=e; p-next=newnode; p=newnode;scanf(%d %d,&c,&e);/ 输入新结点的系数和指数；p-next=NULL; / 为最后的结点的

9、 next 赋空； head=Polysort(head);/ 调用 Polysort 排序函数对多项式链表进行降序排序；return head;/返回头结点；(3)多项式相乘函数Polylist Polymul(Polylist LA,Polylist LB)Polynode *head,*p,*q,*t,*newnode; /head ：头指针 newnode: 新结点指针 p,q,t ：临时指针 变量；p=LA-next;q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/ 开辟一个新结点， 并使之成为新链表的头结 点；八、，t=hea

10、d;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/ 开辟一个新结点；t-next=newnode; t=t-next; t-coef=p-coef*q-coef; t-exp=p-exp+q-exp; q=q-next;p=p-next;q=LB-next;t-next=NULL;head=Polysort(head);降序排序；return head;(4)输出函数void print(Polylist head)Polynode *p;p=head-next;if(p=NULL)printf

11、(0);elsewhile(p!=NULL)/项之系数为 LA,LB 两项系数之积；/项之指数为 LA,LB 两项指数之和；/p 指针移动；/q 指针复位为 LB-next ；/ 为最后的结点的 next 赋空；/ 调用 Polysort 排序函数对多项式链表进行/返回头结点；/系数输出if(p-coef=-1)printf(-);else if(p-coef!=1) printf(%d,p-coef);/符号输出 if(p-exp!=0&p-exp!=1) prin tf(XA);else if(p-exp=1)printf(X);/指数输出 if(p-exp=0&(p-coef=-1|p-

12、coef=1) printf(1);if(p-expexp);else if(p-exp!=1&p-exp!=0)printf(%d,p-exp);p=p-next;if(p!=NULL&p-coef0)printf(+);printf(n);五测试数据及运行结果1正常测试数据和运行结果2异常测试数据及运行结果如输入的字符不是数字，则无法处理，如：a2程序无法继续运行六调试情况，设计技巧及体会1改进方案多项式相成这个程序缺少对异常的处理，如果用户输入一些异常的字符程序将无法继续运 行，甚至导致死机。改进：加入异常处理，将各种用户可能的输入都包含在内。2体会心得体会： 此程序是使用链表完成的，

13、一直以来比较习惯用顺序表， 通过这个程序加深了对 链表的理解。 程序的排序部分较为复杂， 根据幂次的高低排序的同时并合了同类项， 幂次相 同的系数相加存入前项， 释放合并项中后者空间， 若系数相加和为 0 则释放两项空间。 其实 想这段算法时很容易， 真正实现却是相当不容易， 可能是平时写的代码太少， 真正把思想转 换成代码困难还是比较大。移动指针变量 move 被移动项指针变量判断链表是否为空；直接插入排序（链表排序）判断待插入项指数是否与首项相等；系数相加；/ 释放空间； 若系数相加和为 0；释放空间；判断待插入项指数是否大于第一个项的指数；判断下一项是否为空；p,q七参考文献C 语言程序

14、设计 王曙燕主编 科学出版社 数据结构 C 语言描述 耿国华 高等教育出版社 数据结构 严蔚敏 清华大学出版社八附录：#include #include#include typedef struct Polynodeint coef;/ 系数int exp;/ 指数 struct Polynode *next; Polynode,*Polylist;/ 多项式链表升序排序Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first 临时指针变量q=head;p=head-next; if(p=NULL) return h

15、ead; / first=p-next;p-next=NULL; move=first;while(move!=NULL) /first=first-next; if(p-exp=move-exp) / p-coef+=move-coef; / free(move); if(p-coef=0) / q-next=p-next; free(p); / else if(p-expmove-exp) /head-next=move; move-next=p;else if(p-next=NULL) /p-next=move;move-next=NULL;else/ 待插入项指数插入位置在首末项之间；

16、q=p; p=p-next; while(1)/移动临时变量指针 p,qif(p-exp=move-exp) / p-coef+=move-coef;/ free(move);if(p-coef=0)q-next=p-next;/ free(p);break; if(p-expmove-exp) /q-next=move; move-next=p; break;if(p-next=NULL) /p-next=move; move-next=NULL; break; q=p; p=p-next;/判断待插入项指数是否与首项相等；/系数相加；释放空间；若系数相加和为 0； 释放空间；判断待插入项指

17、数是否大于当前项的指数；判断下一项是否为空；移动临时变量指针 p,q ； p=head-next; q=head; move=first;return head;/ 多项式创建 (头插法 ) Polylist creat()/使 p,q 指针重新指到初始化位置；/返回头结点；Polynode *head,*p,*newnode; /head：头指针 newnode: 新结点指针 p ：临时指针变int c,e;/ceof（系数）和exp （指数）;开辟一个新结点，并使之成为头结head=(Polynode *)malloc(sizeof(Polynode);/点；八、，p=head;为最后的结

18、点的 next 赋空;调用 Polysort 排序函数对多项式链表返回头结点;：头指针 newnode: 新结点指针 p,q,t开辟一个新结点， 并使之成为新链表t-next=newnode;t=t-next;t-coef=p-coef*q-coef;t-exp=p-exp+q-exp; q=q-next;/项之系数为 LA,LB 两项系数之积; 项之指数为 LA,LB 两项指数之和;p=p-next;/pq=LB-next;/qt-next=NULL;/head=Polysort(head);/进行降序排序;return head;/ 输出函数void print(Polylist head

19、)指针移动;指针复位为 LB-next ;为最后的结点的 next 赋空; 调用 Polysort 排序函数对多项式链表 返回头结点;printf(nt 请输入多项式中元素的系数和指数 :n); scanf(%d %d,&c,&e);while(c|e)/ceof(系数)和 exp (指数)不全为 0;if(c=0)scanf(%d %d,&c,&e);continue;/ 若 c 为 0，不开辟新结点;newnode=(Polynode *)malloc(sizeof(Polynode);/开辟一个新结点;newnode-coef=c;newnode-exp=e; p-next=newnode;p=newnode;scanf(%d %d,&c,&e);/ 输入新结点的系数和指数;p-next=NULL;/head=Polysort(head);/进行降序排序;return head;/ 多项式相乘Polylist Polymul(Polylist LA,Polylist LB)Polynode *head,*p,*q,*t,*newnode; /head 临时指针变量;p=LA-next;q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/ 的头结点;t=head;while(p!=NULL)while(q!=