《多项式相乘C实现.docx》由会员分享，可在线阅读，更多相关《多项式相乘C实现.docx（9页珍藏版）》请在三一文库上搜索。
1、西安邮电大学数据结构设计报告题目：多项式相乘院系名称：计算机学院专业名称：软件工1班级： 学生姓名：学号（8位）：指导教师：设计起止时间：1 .设计目的以动态单链表为存储结构，使用排序等操作实现多项式的乘法运算2 .设计内容用一个单链表来表示一个一元多项式；在创建多项式的过程中， 可以按指数的任意顺序输入，并且可在同一多项式中输入指数相同的多个项；在进行乘法操作之前， 输出参与操作的两个多项式。 要求输出的多项式按指数升序排列，同指数的多项合并，项数的正负号显示合理。对已排序且合并了同指数项的两个多项式实现乘法操作，并输出结果；结果多项式要求以动态链表为存储结构，复用原多项式的结点空间；输出结
2、果多项式要求按指数升序排列，同指数的多项要合并，项数的正负号要求显示合理。3 .概要设计1 .功能模块图;2 .各个模块详细的功能描述多项式链表升序排序函数PolylistPolysort(Polylisthead)根据幕次的高低排序的同时并合同类项，幕次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为 0则释放两项空间。多项式创建函数Polylistcreat()多项式相乘函数PolylistPolymul(PolylistLA,PolylistLB)输出函数voidprint(Polylisthead)分三种情况：系数输出、符号输出、指数输出四.详细设计1.各功能函数的数据流程
3、图(1)多项式链表升序排序函数 PolylistPolysort(Polylisthead) Polynode*first,*move,*p,*q;/first移动指针 move被移动项指针 p,q临时指针q=head; p=head-next; if(p=NULL)returnhead;/判断链表是否为空；first=p-next; p-next=NULL; move=first; while(move!=NULL)/直接插入排序(链表排序) first=first-next; if(p-exp=move-exp)/判断待插入项指数是否与首项相等； p-coef+=move-coef;系数相
4、加;free(move);/ 释放空间；if(p-coef=0)/ 若系数相加和为0; q-next=p-next; free(p); /释放空间； elseif(p-expmove-exp)/判断待插入项指数是否大于第一个项的指数；head-next=move; move-next=p; elseif(p-next=NULL)/判断下一项是否为空； p-next=move;move-next=NULL;else/待插入项指数插入位置在首末项之间； q=p;/移动临时变量指针 p,qp=p-next; while if(p-exp=move-exp)/判断待插入项指数是否与首项相等；p-coe
5、f+=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;
6、 move=first; returnhead;/ 返回头结点； (2)多项式创建函数 Polylistcreat() Polynode*head,*p,*newnode;/head :头指针newnode:新结点指针 p：临时指针变量intc,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=
7、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 排序函数对多项式链表进行降序排序； returnhead; / 返回头结点； (3)多项式相乘函数
8、 PolylistPolymul(PolylistLA,PolylistLB) 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
9、; 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 排序函数对多项式链表进行降序排序； returnhead;/返回头结点； (4)输出函数 voidprint(Polylisthead) Polynode*p;p=head-next;i
10、f(p=NULL)printf(0);elsewhile(p!=NULL)/系数输出if(p-coef=-1)printf(-);elseif(p-coef!=1)printf(%d,p-coef);/符号输出if(p-exp!=0&p-exp!=1)printf(XA);elseif(p-exp=1)printf(X);/指数输出if(p-exp=0&(p-coef=-1|p-coef=1)printf(1);if(p-expexp);elseif(p-exp!=1&p-exp!=0)printf(%d,p-exp);p=p-next;if(p!=NULL&p-coef0)printf(+)
11、; printf(n);五.测试数据及运行结果1 .正常测试数据和运行结果2 .异常测试数据及运行结果如输入的字符不是数字，则无法处理，如：a2程序无法继续运行六.调试情况，设计技巧及体会1 .改进方案多项式相成这个程序缺少对异常的处理，如果用户输入一些异常的字符程序将无法继续运 行，甚至导致死机。改进：加入异常处理，将各种用户可能的输入都包含在内。2 .体会心得体会：此程序是使用链表完成的，一直以来比较习惯用顺序表，通过这个程序加深了对 链表的理解。程序的排序部分较为复杂，根据哥次的高低排序的同时并合了同类项，哥次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为。则释放两项空间。
12、其实 想这段算法时很容易，真正实现却是相当不容易，可能是平时写的代码太少，真正把思想转换成代码困难还是比较大。七.参考文献C语言程序设计王曙燕主编科学出版社数据结构一一C语言描述耿国华高等教育出版社 数据结构严蔚敏清华大学出版社八.附录：#include#include #include typedefstructPolynode intcoef;/ 系数 intexp;/ 指数 structPolynode*next; Polynode,*Polylist; /多项式链表升序排序 PolylistPolysort(Polylisthead) Polynode*first,*move,*p,*
13、q;/first移动指针变量move被移动项指针变量 p,q临时指针变量 q=head; p=head-next; if(p=NULL)returnhead;/判断链表是否为空；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)
14、；/释放空间;elseif(p-expmove-exp)/判断待插入项指数是否大于第一个项的指数;head-next=move;move-next=p;elseif(p-next=NULL)/判断下一项是否为空;p-next=move;move-next=NULL; else/待插入项指数插入位置在首末项之间;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(
15、p)；break;/若系数相加和为 0;释放空间；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;/移动临时变量指针p,q ;p=head-next; 使p,q指针重新指到初始化位置;q=head;move=first;returnhead;/返回头结点；/多项式创建(头插法)Polylistcreat() Polynode*head,*p,*newnode
16、; /head :头指针 newnode:新结点指针 p：临时指针变量 intc,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(P
17、olynode);/开辟个新结点；newnode-coef=c; newnode-exp=e; p-next=newnode; p=newnode; scanf(%d%d,&c,&e);/输入新结点的系数和指数； p-next=NULL;/为最后的结点的 next赋空； head=Polysort(head);/ 调用Polysort 排序函数对多项式链表进行降序排序； returnhead; / 返回头结点； /多项式相乘 PolylistPolymul(PolylistLA,PolylistLB) Polynode*head,*p,*q,*t,*newnode;head:头指针 newno
18、de:新结点指针 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
19、=q-next; p=p-next;/p 指针移动； q=LB-next;/q 指针复位为 LB-next ; t-next=NULL;/ 为最后的结点的 next赋空； head=Polysort(head);/ 调用Polysort 排序函数对多项式链表进行降序排序；returnhead;/返回头结点;/输出函数voidprint(Polylisthead)Polynode*p;p=head-next;if(p=NULL) printf(0); else while(p!=NULL) /系数输出 if(p-coef=-1) printf(-);elseif(p-coef!=1) print
20、f(%d,p-coef);/符号输出if(p-exp!=0&p-exp!=1) printf(XA);elseif(p-exp=1) printf(X);/指数输出if(p-exp=0&(p-coef=-1|p-coef=1) printf(1);if(p-expexp);elseif(p-exp!=1&p-exp!=0) printf(%d,p-exp);p=p-next;if(p!=NULL&p-coef0) printf(+); printf(n);voidmain()PolylistLA,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;