多项式相乘.docx
- 文档编号:13136058
- 上传时间:2023-06-11
- 格式:DOCX
- 页数:25
- 大小:64.84KB
多项式相乘.docx
《多项式相乘.docx》由会员分享,可在线阅读,更多相关《多项式相乘.docx(25页珍藏版)》请在冰点文库上搜索。
多项式相乘
西安郵電學院
数据结构课程设计报告
题目:
多项式相乘
院系名称:
计算机学院
专业名称:
软件工程
班级:
学生姓名:
学号(8位):
指导教师:
设计起止时间:
一.设计目的
设计多项式相乘这个题目,要求主要用链表实现。
在用链表实现的过程中,可以进一步了解掌握链表的创建,链表中多项式的合并,链表的查找,链表的排序,链表的插入,删除等功能。
链表在数据结构中相当的重要,不管是哪一种数据类型都可用链表来实现。
所以设计多项式相乘的目的及掌握链表的使用。
二.设计内容
以动态单链表为存储结构,使用排序等操作实现多项式的乘法运算
3.概要设计
开始
1.功能模块图;
主函数
创建多项式LA
多项式合并同类项函数Polyget
创建多项式LB
多项式升幂排序函数Polysort
多项式相乘函数Polymul(LA,LB)
输出函数print
多项式合并同类项函数Polyget
多项式升幂排序函数Polysort
结束
输出函数print
2.各个模块详细的功能描述。
1.多项式链表创建Polylistcreat();
通过终端输入多项式的系数coef和指数exp(以0,0结束),分别建立LA,LB两个有头结点,coef和exp两个数据域的多项式链表,并返回head;
2.同指数多项合并PolylistPolyget(Polylisth);
对相同x次幂的的项进行合并,并且对0系数的项,进行处理;
3.多项式进行升序排序PolylistPolysort(Polylisth);
将输入是指数无序的多项式,按照降序次幂进行排序;
3.多项式相乘函数PolylistPolymul(PolylistLA,PolylistLB);
通过对LA、LB中项系数相乘,将LA中的每一个结点分别乘与LB中的每一个节点,将LA与每一个LB中的结点相乘的内容存到新结点中,并插入LA的那个结点之前,乘完后将LA的此结点删除掉。
4.输出函数voidprint(Polylisthead);
输出链表LC,考虑到对1,-1,0等作为系数指数的情况,做了相应的处理,同时对负指数加上了括号,使结果更加明晰。
4.详细设计
1、输入第一个多项式,第二个多项式。
遇到(0,0)结束多项式的输入,在输入过程中,系数为零,则不为其申请空间。
认为此项不存在。
2、把输入的第一个第二个多项式以多项式的形式输出。
查看是否满足通常书写要求。
对系数正负,为1,-1进行处理,对指数为0,1进行处理。
对多项式第一项和非第一项进行处理。
3、分别对两个多项式进行合并,在合并的过程中p指向当前项,则q为p的下一项开始查找与当前项相同的项,找到则合并多项式,及把后一项删除掉,查找到链表结尾后,判断当前项,及查找相同幂的这一项是否为零,若为零,则删除。
然后再从下一项开始查找幂相同的项,进行合并。
4、将两个合并后的多项式分别输出,查看合并过程是否正确。
5、对多项式进行排序。
因为输出的时候要求按照升序进行输出。
排序过程选用选择排序法,若当前项小于其后的项,则把当前项与其后项整体交换,然后再把其next域交换回去。
6、将两个排序后的多项式分别进行输出。
查看是否按照升序输出。
7、将两个多项式进行相乘。
相乘过程采用服用原节点的思路。
将第一个多项式的每一项与第二个多项式的第一项相乘的结果放在第一个多项式相乘的当前位上,第一个多项式与第二个多项式除第一项相乘的结果都申请空间链接到第一个多项式的后面。
8、将相乘后的结果以多项式的形式输出。
9、将相乘结果合并多项式,然后输出。
10、将相乘结果排序后,按照升序输出。
查看结果是否正确。
1.功能函数的调用关系图
主函数
创建多项式LA
多项式合并同类项函数Polyget
多项式升幂排序函数Polysort
输出函数print
创建多项式LB
多项式合并同类项函数Polyget
多项式升幂排序函数Polysort
输出函数print
多项式相乘函数Polymul(LA,LB)
多项式合并同类项函数Polyget
多项式升幂排序函数Polysort
输出函数print
结束
2.各功能函数的数据流程图
输入多项式流程图:
开始
输入系数,幂
1
N
退出循环(0,0)
Y
Y
N
系数为0
Y
N
链接到链表尾部
输入
结束
合并多项式流程图:
开始
初始化,p=poly,q=p->next
P=p->next;p!
=NULL
N
q=q->next,q!
=NULL
Y
N
幂相同
Y
N
合并,删除q一项
Y
P系数为0
N
Y
合并,删除后p这一项
结束
多项式输出流程图:
开始
初始化,p=poly
P=p->next;p!
=NULL
N
Y
多项式第一项
N
系数不为1,-1指数不为0,1
Y
Y
指数为0
N
Y
指数为1
N
Y
系数为1
N
Y
输出
系数大于1
系数等于1
系数等于-1
输出
结束
排序流程图:
开始
初始化p=poly,q=p;
P=p->next;p!
=NULL,q=p
N
q=q->next;p!
=NULL
Y
N
p->exp>q->exp
Y
N
Y
交换
结束
两多项式相乘流程图:
结束
初始化,i=polya,s=polyb
其中有一个多项式为空
Y
N
找到第一个多项式最后一项m
i=i->next,i!
=m->next,j=s
N
j=j->next,j!
=NULL
Y
N
Y
a的每一项与b的第一项相乘
N
Polya的每一项与polyb的第一项相乘结果放回polya的当前项
Y
相乘结果存放重新申请的空间,链接到polya的尾部
重新申请空间,
结束
3.重点设计及编码
//同指数多项合并
PolylistPolyget(Polylisth)
{
intsum;
Polynode*p,*q,*m,*pre;
if(h==NULL)
returnh;
p=h->next;
pre=p;
q=p->next;
while(p!
=NULL)
{
while(q!
=NULL)
{
if(p->exp==q->exp)
{
sum=p->coef+q->coef;
if(sum!
=0)
{
m=q;
p->coef=sum;
}
if(q->next!
=NULL)
{
pre->next=q->next;
q=pre->next;
free(m);
}
elseif(q->next==NULL)
{
pre->next=NULL;
q=NULL;
free(m);
}
}
else
{
pre=pre->next;
q=q->next;
}
}
p=p->next;
if(p!
=NULL)
{
pre=p;
q=p->next;
}
}
if(h->next==NULL)
{
printf("该多项式为0!
\n");
returnh;
}
returnh;
}
//多项式进行升幂排序
PolylistPolysort(Polylisth)
{
Polynode*p,*r,*t,*s;
p=h->next->next;
h->next->next=NULL;
while(p!
=NULL)
{
t=p->next;
r=h;
s=h->next;
if(s->exp>p->exp)
{
p->next=s;
r->next=p;
}
else
{
for(;s&&s->exp
;
p->next=s;
r->next=p;
}
p=t;
}
returnh;
//多项式相乘函数
PolylistPolymul(PolylistLA,PolylistLB)
{
Polynode*p,*q,*t,*r,*newnode;
t=LA;
p=LA->next;
q=LB->next;
while(p!
=NULL)
{
r=p;
while(q!
=NULL)
{
newnode=(Polynode*)malloc(sizeof(Polynode));
newnode->coef=p->coef*q->coef;
newnode->exp=p->exp+q->exp;
t->next=newnode;
newnode->next=p;
t=t->next;
q=q->next;
}
q=LB->next;
p=p->next;
newnode->next=newnode->next->next;
free(r);
}
returnLA;
}
5.测试数据及运行结果
1.正常测试数据和运行结果
要求提供3组正常测试数据和运行结果
(1)测试数据LA:
(1-1)(36)(42)LB:
(32)
运行结果:
(2)测试数据LA:
(5-2)(23)(43)
LB:
(11)(31)
运行结果:
(3)测试数据LA:
(26)(-1-2)
LB:
(37)(21)
运行结果:
2.异常测试数据及运行结果
要求提供2组异常测试数据和运行结果
(1)测试数据LA:
(23)(10)
LB:
(10)
运行结果:
(2)测试数据LA:
(00)
运行结果:
6.调试情况,设计技巧及体会
1.改进方案
在本次课程设计多项式相乘程序中,因为输入的指数是任意的,所以对输入的多项式进行整理。
对多项式进行同类项合并然后按指数的升幂排序,排序部分的算思想是将要排序的链表分成两部分,第一部分是头结点和第一个结点构成的有序链表,另一部分是剩下的结点构成的无序表,然后把无序表中的结点依次插入到有序表中。
多项式进行乘法时,用两层循环,将LA中的每一个结点分别乘与LB中的每一个节点,将LA与每一个LB中的结点相乘的内容存到新结点中,并插入LA的那个结点之前,乘完后将LA的此结点删除掉。
然后将此多项式并合并同类项,指数按升幂排序,最后输出结果。
但是在合并同类项的时候还有一些繁琐,在输出部分,还有一些不完美,考虑的情况还有些欠缺,下来后我会对程序做进一步的改进,争取解决所有存在的问题。
2.体会
此次课程设计多项式相乘,我学会了很多东西,尤其对链表的运用更加的熟练,在以后的学习中要亲自动脑,自己动手。
经过这次实践,我们应该明白了实践的重要性,还有在写算法的时候要多画,多想,勤动脑,争取写出最精简的算法,在以后的学习中,我会更加努力,学好数据结构,多练多想。
七.参考文献
《C语言程序设计》谭浩强清华大学出版社
《C语言程序设计》王曙燕等科学出版社
《数据结构——使用C语言》陈一华等电子科技大学出版社
《数据结构题集》严蔚敏,吴伟民清华大学出版社
八.附录:
源代码(电子版)
#include
#include
typedefstructPolynode
{
intcoef;
intexp;
structPolynode*next;
}Polynode,*Polylist;
//用尾插法建立一元多项式的链表
PolylistCreat()
{
Polynode*head,*p,*s;
intc,e;
head=(Polynode*)malloc(sizeof(Polynode));
head->next=NULL;
p=head;
printf("请输入多项式中元素的系数和指数:
\n");
scanf("%d%d",&c,&e);
if(c==0)
printf("输入有误!
\n");
while(c!
=0)
{
s=(Polynode*)malloc(sizeof(Polynode));
s->coef=c;
s->exp=e;
p->next=s;
p=s;
scanf("%d%d",&c,&e);
}
p->next=NULL;
return(head);
}
//同指数多项合并
PolylistPolyget(Polylisth)
{
intsum;
Polynode*p,*q,*m,*pre;
if(h==NULL)
returnh;
p=h->next;
pre=p;
q=p->next;
while(p!
=NULL)
{
while(q!
=NULL)
{
if(p->exp==q->exp)
{
sum=p->coef+q->coef;
if(sum!
=0)
{
m=q;
p->coef=sum;
}
if(q->next!
=NULL)
{
pre->next=q->next;
q=pre->next;
free(m);
}
elseif(q->next==NULL)
{
pre->next=NULL;
q=NULL;
free(m);
}
}
else
{
pre=pre->next;
q=q->next;
}
}
p=p->next;
if(p!
=NULL)
{
pre=p;
q=p->next;
}
}
if(h->next==NULL)
{
printf("该多项式为0!
\n");
returnh;
}
returnh;
}
//多项式进行升幂排序
PolylistPolysort(Polylisth)
{
Polynode*p,*r,*t,*s;
p=h->next->next;
h->next->next=NULL;
while(p!
=NULL)
{
t=p->next;
r=h;
s=h->next;
if(s->exp>p->exp)
{
p->next=s;
r->next=p;
}
else
{
for(;s&&s->exp
;
p->next=s;
r->next=p;
}
p=t;
}
returnh;
}
//多项式相乘函数
PolylistPolymul(PolylistLA,PolylistLB)
{
Polynode*p,*q,*t,*r,*newnode;
t=LA;
p=LA->next;
q=LB->next;
while(p!
=NULL)
{
r=p;
while(q!
=NULL)
{
newnode=(Polynode*)malloc(sizeof(Polynode));
newnode->coef=p->coef*q->coef;
newnode->exp=p->exp+q->exp;
t->next=newnode;
newnode->next=p;
t=t->next;
q=q->next;
}
q=LB->next;
p=p->next;
newnode->next=newnode->next->next;
free(r);
}
returnLA;
}
//输出函数
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)
printf("%d",p->coef);
//符号输出格式定义
if(p->exp!
=0&&p->exp!
=1)
printf("X^");
elseif(p->exp==1)
printf("X");
//指数输出格式的定义
if(p->exp==0&&(p->coef==-1||p->coef==1))
printf("1");
if(p->exp<0)
printf("(%d)",p->exp);
elseif(p->exp!
=1&&p->exp!
=0)
printf("%d",p->exp);
p=p->next;
if(p!
=NULL&&p->coef>0)
printf("+");
}
printf("\n");
}
voidmain()
{
PolylistLA,LB;
printf("请输入一元多项式LA:
\n");
LA=Creat();
printf("输出多项式LA(同指数多项合并,并按指数升序排列):
\n");
Polyget(LA);
Polysort(LA);
print(LA);
printf("\n请输入一元多项式LB:
\n");
LB=Creat();
printf("输出多项式LB(同指数多项合并,并按指数升序排列):
\n");
Polyget(LB);
Polysort(LB);
print(LB);
printf("\nLA与LB的乘积为:
\n");
LA=Polymul(LA,LB);
Polyget(LA);
Polysort(LA);
print(LA);
}
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 多项式 相乘
![提示](https://static.bingdoc.com/images/bang_tan.gif)