多项式相乘C实现

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

2、升序排列，同指数 的多项要合并，项数的正负号要求显示合理。三. 概要设计1功能模块图;2 各个模块详细的功能描述。多项式链表升序排序函数Polylist P olysort ( Polylist head)根据幕次的高低排序的同时并合同类项，幕次相同的系数相加存入前项，释放合并项中后者空 间，若系数相加和为0则释放两项空间。多项式创建函数Polylist creat()多项式相乘函数Polylist Polymul( Polylist LA, P olylist LB)输出函数void pnnt(Po lylist head)分三种情况：系数输出、符号输出、指数输出四. 详细设计1.各功能函数

3、的数据流程图结束2-重点设计及编码(1)多项式链表升序排序函数Polylist Polysort(Polylist head)(Polynode *first, *move, *p, *q;/first 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+zzmove-coef; free(move);if(p-coef=0)移动指针move被移动项指针p, q

4、临时指针/判断链表是否为空；/直接插入排序(链表排序)/判断待插入项指数是否与首项相等；/系数相加；/释放空间；/若系数相加和为0： q-next=p-next;free(p) ; /释放空间；else辻(p-expmove-exp) /判断待插入项指数是否大于第一个项的指数；c head-nextzzmove;move-next=p;else if (p-next=NULL)/判断下一项是否为空；p-next=move; move-next=NULL;else/待插入项指数插入位置在首末项之间；q二p; p=p-next; while (1)/移动临时变量指针P, qif (p-expmov

5、e-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=zp; break;1辻(p-next=NULL)(、判断下一项是否为空;p-/next=move;move-next=XULL; break;q二P； p=p-next;/移动临时变量指针P, q :p=head-next;

6、 q二head; move=first;return head;/使P, q指针重新指到初始化位置;/返回头结点;(2 )多项式创建函数Polylist creat()Polynode *head, *p, *newnode;/head：头指针newnode:新结点指针p：临时指针变量int c, e;/ceof (系数)和 exp (指数)；head= (Polynode *)malloc (sizeof (Polynode) ;/ 开辟一个新结点，并使之成为头结点； p=head;printf (z，nt请输入多项式中元素的系数和指数：n);scanf (%d %d, &c, &e);wh

7、ile(c | e)/ceof (系数)和 exp (指数)不全为 0;if (c=0)scanf (，z%d %d，z, &c, &e) ; continue;/若 c 为 0,不开辟新结点;newnode= (Polynode *)malloc (sizeof (Polynode) ;/ 开辟一个新结点; newnode-coef=c;newnode-exp=e; p-next=newnode;p二newnode;scanf (，z%d %d, &c, &e) ;/输入新结点的系数和指数;1p-next=NULL; head=Polysort(head);序排序；/为最后的结点的next赋

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

9、!=NULL)newnode=(Polynode *)malloc(sizeof(Polynode);/ 开辟一个新结点； t-next=newnode;/p指针移动；/q指针复位为LB-next ；/为最后的结点的next赋空；/调用Polysort排序函数对多项式链表进行返回头结点;t=t-next;t-coef二p-coef*q-coef; t-exp=p-exp+q-exp; q二q-next;:p=p-next; q=LB-next;/项之系数为LA, LB两项系数之积；/项之指数为LA, LB两项指数之和;t-next=NULL;head二Polysort (head);降序 排序

10、；return head; (4)输出函数void print(Polylist head)(Polynode *p;p=head-next;辻(p二二NULL)printf CO);elsewhile(p!=NULL)(/系数输出if(p-coef=-l) printfC-O； else if(p-coef!=1) printf(%d, p-coef )；符号输出辻(p-exp!=0&p-exp!二1)prin tf(XA);else if (p-exp=l) printf CX);/指数输出if (p-exp=0& (p-coef=-l p-coefl) printf Clz，);if(p

11、-expexp);else if(p-exp!=1&p-exp!=0) printfp-exp);p=p-next;辻(p!二NULL&p-coef0)printf(+)； prin tfCW);五. 测试数据及运行结果1.正常测试数据和运行结果诗输入多顶武中兀索的系数和指数:1 -1-2 3& 1罔e两多项式相乘结果LCi2.异常测试数据及运行结果如输入的字符不是数字，则无法处理，如：a2程序无法继续运行六. 调试情况，设计技巧及体会1改进方案多项式相成这个程序缺少对异常的处理，如果用户输入一些异常的字符程序将无法继续运行，我至导致死机。 改进：加入异常处理，将各种用户可能的输入都包含在内。

12、2 体会心得体会：此程序是使用链表完成的，一直以来比较习惯用顺序表，通过这个程序加深了对 链表的理解。程序的排 序部分较为复杂，根据幕次的高低排序的同时并合了同类项，幕次相同的系数相加存入前项，释放合并项中后者空间，若系数相加和为0则释放两项空间。其实想这段算法时很容易， 真正实现却是相当不容易，可能是平时写的代码太少，真正把思想转换成代码困难还是比较大。七.参考文献C语言程序设计王曙燕主编科学出版社数据结构c语言描述耿国华高等教育出版社数据结构严蔚敏清华大学出版社八.附录：# includeO# includeO#includetypedef struct Polynode（int coef

13、;/ 系数 intexp;/ 指数 structPolynode *next;Polynode, Polylist;/多项式链表升序排序Polylist Polysort(Polylist head)Polynode *first, *move, *p, *q；/first临时指针变量移动指针变量move被移动项指针变量p, qq二head; p=head-next;if(p二二NULL) return head; / first=p-next; p-next二NULL; move二first; while(move!=NULL) first=firstnext;if(p-exp=move-e

14、xp) / :判断链表是否为空;p-coef+=move-coef; free(move);直接插入排序（链表排序）if(p-coef=0) / 判断待插入项指数是否与首项相等;系数相加；释放空间；若系数相加和为0；释放空间;判断待插入项指数是否大于第一个项的指数;q-next=p-next; free(p) ;zelse if (pexpmove-exp) / head-next:z:move;movenext二p;p-next=move; move-next=NULL;else/待插入项指数插入位置在首末项之间;q 二p;/p二p-next;/while(1)(if (p-exp=move

15、-exp) /p-coef+=move-coef;/ free (move);if(p-coef=0) q-next=p-next;/free(p);)break;if (p-expmove-exp) /移动临时变量指针P, q判断待插入项指数是否与首项相等;系数相加；/释放空间；若系数相加和为0；释放 /空间；判断待插入项指数是否大于当前项的指数q-next二move; move-next=p; break;)i. f (p-next =NULL) /判断下一项是否为空;p-next二move; move-next=NULL; break;)q=p;p=p-next;移动临时变量指针P, q

16、 :p=head-next; q=head; move=first;1 return head;使P, q指针重新指到初始化位置;返回头结点;/多项式创建(头插法)Polylist creat()Polynode *head, *p, *newnode; /head 量 :头指针 newnode:新结点指针 p :临时指针变/ceo f系数）intc, e;head=(Polynode *)malloc(sizeof (Polynode);/占八八,p二head;printf(/znt请输入多项式中元素的系数和指数scanf (%d %d, &c, &e);while(c |e)和exp （指

17、数）；开辟一个新结点，并使之成为头结：）/ceo f（系数）和exp （指数）不全为0;if(c=0)/若C为0,不开辟新结点；开辟一个新结点;scanf (，z%d %d，&c, &e) ; continue; newnode= (Polynode *)malloc (sizeof (Polynode) )z;/ newnode-coef=c; newnode-exp二e;p-next二newnode;p=newnode; scanf(“d %d, &c, &e);/输入新结点的系数和指数；p-next=NULL; head二Polysort(head);进行降序排序；return head

18、;为最后的结点的next赋空；/调用Polysort排序函数对多项式链表/ 多项式相乘 Polylist Polymul (Polyl4stLA, Polylist LB) next; q=LB-next;head=(Polynode *)malloc(sizeof(Polynode);/的头结点；t二head;while(p!=NULL):头指针 newnode:新结点指针 p, q, t :开辟一个新结点，并使之成为新链表wh 订 e(qUNULL)newnode=(Polynode *)malloc(sizeof(Polynode);/ tnext=newnode; t=tnext;t-coef二p-coef*q-coef; t-exp二p-exp+q-exp;q二q_next;/项之系数为项之指数为LA, LB两项系数之积;LA, LB两项指数之和;p=p-next;q=LB-next;/p指针移动；q指针复位为LBnext :t-next=NULL;head=Polysort(head);/为最后的结点的next赋空；调用进行降序排序；/Polysort排序函数对多项式链表return head;/返回头结点；/输出函数void print (Polyli