《多项式相乘c实现》由会员分享,可在线阅读,更多相关《多项式相乘c实现(12页珍藏版)》请在金锄头文库上搜索。
1、西安郵電大学数据结构设计报告题 目: 多项式相乘院系名称: 计算机学院 专业名称: 软件工程班 级: 学生姓名: 学号(8位): 指导教师: 设计起止时间:一. 设计目的以动态单链表为存储结构,使用排序等操作实现多项式的乘法运算二. 设计内容用一个单链表来表示一个一元多项式;在创建多项式的过程中,可以按指数的任意顺序输入,并且可在同一多项式中输入指数相同的多个项;在进行乘法操作之前,输出参与操作的两个多项式。要求输出的多项式按指数升序排列,同指数的多项合并,项数的正负号显示合理。 对已排序且合并了同指数项的两个多项式实现乘法操作,并输出结果;结果多项式要求以动态链表为存储结构,复用原多项式的结
2、点空间;输出结果多项式要求按指数升序排列,同指数的多项要合并,项数的正负号要求显示合理。三概要设计主函数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)根据幂次的高低排序的同时并合同类项,幂次相同的系数相加存入前项,释放合并
3、项中后者空间,若系数相加和为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= =
4、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(
5、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
6、=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) /判断待插入项指数是否大于当
7、前项的指数;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(指
8、数);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=new
9、node;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(
10、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