多项式相乘C实现.doc

西安郵電大学数据结构设计报告题 目： 多项式相乘院系名称： 计算机学院 专业名称： 软件工程班 级： 学生姓名： 学号（8位）： 指导教师： 设计起止时间：一. 设计目的以动态单链表为存储结构，使用排序等操作实现多项式的乘法运算二. 设计内容用一个单链表来表示一个一元多项式；在创建多项式的过程中，可以按指数的任意顺序输入，并且可在同一多项式中输入指数相同的多个项；在进行乘法操作之前，输出参与操作的两个多项式。要求输出的多项式按指数升序排列，同指数的多项合并，项数的正负号显示合理。 对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；结果多项式要求以动态链表为存储结构，复用原多项式的结点空间；输出结果多项式要求按指数升序排列，同指数的多项要合并，项数的正负号要求显示合理。三概要设计主函数main()1功能模块图；创建多项式LB=creat()创建多项式LA=creat()调用Polysort( )排序调用print()输出LB调用Polysort( )排序调用print()输出LA对多项式LA,LB相乘LC=Polymul(LA,LB)调用Polysort( )排序 调用print()输出LC2各个模块详细的功能描述。多项式链表升序排序函数Polylist Polysort(Polylist head)根据幂次的高低排序的同时并合同类项，幂次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为0则释放两项空间。多项式创建函数Polylist creat()多项式相乘函数Polylist Polymul(Polylist LA,Polylist LB)输出函数void print(Polylist head)分三种情况：系数输出、符号输出、指数输出四详细设计1.各功能函数的数据流程图Polysort()开始head=NULL？first=p-next; p-next=NULL; move=first; Yp-exp= =move-expp-exp= =move-exp N N yp-coef+=move-coef; free(move);p-next= =NULL yhead-next=move; move-next=p; p-coef= =0 yhead-next=move; move-next=p; q=p;p=p-next;q-next=p-next;free(p); yWhile(1)p=head-next; q=head;move=first;return head结束2重点设计及编码（1）多项式链表升序排序函数Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first移动指针 move 被移动项指针p,q临时指针q=head; p=head-next;if(p=NULL) return head; /判断链表是否为空；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) /若系数相加和为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 /待插入项指数插入位置在首末项之间； q=p; /移动临时变量指针p,qp=p-next;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-expmove-exp) /判断待插入项指数是否大于当前项的指数；q-next=move;move-next=p;break;if(p-next=NULL) /判断下一项是否为空；p-next=move;move-next=NULL;break;q=p; /移动临时变量指针p,q；p=p-next;p=head-next; /使p,q指针重新指到初始化位置；q=head;move=first;return head; /返回头结点；（2）多项式创建函数Polylist creat()Polynode *head,*p,*newnode;/head：头指针 newnode:新结点指针 p：临时指针变量int c,e; /ceof（系数）和exp（指数）；head=(Polynode *)malloc(sizeof(Polynode);/开辟一个新结点，并使之成为头结点；p=head;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; /为最后的结点的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=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/开辟一个新结点；t-next=newnode;t=t-next;t-coef=p-coef*q-coef; /项之系数为LA,LB两项系数之积；t-exp=p-exp+q-exp; /项之指数为LA,LB两项指数之和；q=q-next;p=p-next; /p指针移动；q=LB-next; /q指针复位为LB-next；t-next=NULL; /为最后的结点的next赋空；head=Polysort(head); /调用Polysort排序函数对多项式链表进行降序排序；return head; /返回头结点；（4）输出函数void print(Polylist head)Polynode *p;p=head-next;if(p=NULL) printf(0);else while(p!=NULL) /系数输出if(p-coef=-1) printf(-);else if(p-coef!=1) printf(%d,p-coef);/符号输出if(p-exp!=0&p-exp!=1) printf(X);else if(p-exp=1) printf(X);/指数输出if(p-exp=0&(p-coef=-1|p-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异常测试数据及运行结果如输入的字符不是数字，则无法处理，如：a 2 程序无法继续运行六调试情况，设计技巧及体会1改进方案多项式相成这个程序缺少对异常的处理，如果用户输入一些异常的字符程序将无法继续运行，甚至导致死机。改进：加入异常处理，将各种用户可能的输入都包含在内。2体会心得体会：此程序是使用链表完成的，一直以来比较习惯用顺序表，通过这个程序加深了对链表的理解。程序的排序部分较为复杂，根据幂次的高低排序的同时并合了同类项，幂次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为0则释放两项空间。其实想这段算法时很容易，真正实现却是相当不容易，可能是平时写的代码太少，真正把思想转换成代码困难还是比较大。七参考文献C语言程序设计 王曙燕主编 科学出版社数据结构C语言描述 耿国华 高等教育出版社数据结构 严蔚敏 清华大学出版社八附录：#include#include#includetypedef struct Polynodeint coef;/系数int exp;/指数struct Polynode *next;Polynode,*Polylist;/多项式链表升序排序Polylist Polysort(Polylist head)Polynode *first,*move,*p,*q; /first移动指针变量 move 被移动项指针变量p,q临时指针变量q=head; p=head-next;if(p=NULL) return head; /判断链表是否为空；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) /若系数相加和为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 /待插入项指数插入位置在首末项之间； q=p; /移动临时变量指针p,qp=p-next;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-expmove-exp) /判断待插入项指数是否大于当前项的指数；q-next=move;move-next=p;break;if(p-next=NULL) /判断下一项是否为空；p-next=move;move-next=NULL;break;q=p; /移动临时变量指针p,q；p=p-next;p=head-next; /使p,q指针重新指到初始化位置；q=head;move=first;return head; /返回头结点；/多项式创建(头插法)Polylist creat()Polynode *head,*p,*newnode;/head：头指针 newnode:新结点指针 p：临时指针变量int c,e; /ceof（系数）和exp（指数）；head=(Polynode *)malloc(sizeof(Polynode);/开辟一个新结点，并使之成为头结点；p=head;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; /为最后的结点的next赋空；head=Polysort(head); /调用Polysort排序函数对多项式链表进行降序排序；return head; /返回头结点；/多项式相乘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=head;while(p!=NULL)while(q!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/开辟一个新结点；t-next=newnode;t=t-next;t-coef=p-coef*q-coef; /项之系数为LA,LB两项系数之积；t-exp=p-exp+q-exp; /项之指数为LA,LB两项指数之和；q=q-next;p=p-next; /p指针移动；q=LB-next; /q指针复位为LB-next；t-next=NULL; /为最后的结点的next赋空；head=Polysort(head); /调用Polysort排序函数对多项式链表进行降序排序；return head; /返回头结点；/输出函数void print(Polylist head)Polynode *p;p=head-next;if(p=NULL) printf(0);else while(p!=NULL) /系数输出if(p-coef=-1) printf(-);else if(p-coef!=1) printf(%d,p-coef);/符号输出if(p-exp!=0&p-exp!=1) printf(X);else if(p-exp=1) printf(X);/指数输出if(p-exp=0&(p-coef=-1|p-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);void main()Polylist LA,LB,LC; printf(ttt请输入一元多项式 A：n);printf(t请输入一元多项式 A：n);LA=creat(); /创建多项式LA；print(LA); /输出多项式LA；printf(t请输入一元多项式 B：n);LB=creat(); /创建多项式LB；print(LB); /输出多项式LB；LC=Polymul(LA,LB); /对多项式LA,LB相乘；printf(两多项式相乘结果LC：);print(LC); /输出多项式LC；欢迎您的光临，Word文档下载后可修改编辑.双击可删除页眉页脚.谢谢！希望您提出您宝贵的意见，你的意见是我进步的动力。赠语； 1、如果我们做与不做都会有人笑，如果做不好与做得好还会有人笑，那么我们索性就做得更好，来给人笑吧！ 2、现在你不玩命的学，以后命玩你。3、我不知道年少轻狂，我只知道胜者为王。4、不要做金钱、权利的奴隶；应学会做“金钱、权利”的主人。5、什么时候离光明最近？那就是你觉得黑暗太黑的时候。6、最值得欣赏的风景，是自己奋斗的足迹。7、压力不是有人比你努力，而是那些比你牛几倍的人依然比你努力。