一元多项式计算问题课程设计.docx
《一元多项式计算问题课程设计.docx》由会员分享，可在线阅读，更多相关《一元多项式计算问题课程设计.docx（24页珍藏版）》请在冰点文库上搜索。
一元多项式计算问题课程设计
长沙学院
课程设计说明书
题目
一元多项式计算问题
系（部）
计算机系
专业（班级）
10级软件D班
姓名
向栋良
学号
2010022D08
指导教师
邓旭东
起止日期
2011.9.4-2011.9.8
课程设计任务书
课程名称：
数据结构与算法
设计题目：
一元多项式计算问题
已知技术参数和设计要求：
问题描述：
设计一个稀疏多项式简单计算器
基本要求：
（1）输入并分别建立多项式A和B
（2）输入输出多项式，输出形式为整数序列：
n,c1,e1,c2,e2……，其中n是多项式的项数，ci和ei是第i项的系数和指数，序列按指数降序排列
（3）完成两个多项式的相加、相减，并将结果输出；
测试数据：
（1）A+BA=3x14-8x8+6x2+2B=2x10+4x8+-6x2
（2）A-BA=11x14+3x10+2x8+10x6+5B=2x14+3x8+5x6+7
（3）A+BA=x3+x1B=-x3-x1
（4）A+BA=0B=x7+x5+x3+x1
（5）A-BA=100x100+50x50+20x20+xB=10x100+10x50+10x20+x
选作内容：
（1）.多项式在x=1时的运算结果
（2）求多项式A和B的乘积
设计工作量：
40课时
工作计划：
日期
节次
地点
设计方式
9月4日（周日）
1-4
科1408
讲授内容
9月4日（周日）
5-8
科1608
答疑
9月5日（周一）
1-4
科1408
上机调试
9月5日（周一）
5-8
科1608
答疑
9月6日（周二）
1-4
科1408
上机调试
9月6日（周二）
5-8
科1608
答疑
9月7日（周三）
1-4
科1408
上机调试
9月7日（周三）
5-8
科1608
答疑
9月8日（周四）
1-4
科1608
答疑
9月8日（周四）
5-8
科1408
答辩
指导教师签名：
日期：
教研室主任签名：
日期：
系主任签名：
日期：
长沙学院课程设计鉴定表
姓名
徐皖宁
学号
2010022509
专业
软件工程
班级
软件五班
设计题目
课程设计安排
指导教师
杜红燕
指导教师意见：
评定等级：
教师签名：
日期：
答辩小组意见：
评定等级：
答辩小组长签名：
日期：
教研室意见：
教研室主任签名：
日期：
系（部）意见：
系主任签名：
日期：
说明
课程设计成绩分“优秀”、“良好”、“及格”、“不及格”四类；
摘要
本文是关于一个一元稀疏多项式计算器的问题。
一元稀疏多项式计算内容包括输入并建立多项式，多项式相加，多项式相减，以及其输出多项式。
本程序运用面向对象的设计方法，使用C++语言，利用microsoftvisualC++6.0开发工具，还有数据结构中学到的链式存储架构，存储一元多项式，从而实现程序的基本功能，在程序中定义了各种类型的运算模块，通过主程序的调用来完成它们之间的配合，从而使程序正确运行。
关键词：
数据结构；一元多项式；链表；C++语言
第一章需求分析
1.1输入的形式和输入值的范围：
输入是从键盘输入的，输入的内容为多项式的系数和指数，数为任意的整数，指数为大于等于0的整数
1.2输出的形式
从屏幕输出，显示用户输入的多项式，并显示多项式加减以后的多项式的值。
1.3程序所能达到的功能
a：
输入并建立多项式；
b：
输出多项式，输出形式为整数序列：
n,c1,e1,c2,e2,……,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；
c：
多项式a和b相加，建立多项式a+b；
d：
多项式a和b相减，建立多项式a-b；
e：
多项式的输出形式为类数学表达式。
系数值为1的非零项的输出形式中略去系数1。
而-1x的输出形式为-x。
第二章概要设计
2.1设计思路
A：
数据结构的选用
为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元属；
B：
多项式的输入
采用头插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；为了判断一个多项式是否输入结束，定义一个结束标志，当输入非0时就继续，当输入0时，就结束一个多项式的输入；
C：
2个多项式的加法
它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相加；相加的和不为0的话，用头插法建立一个新的节点。
p的系数小于q的系数的话，就应该复制q接点到多项式中。
p的系数大于q的系数的话，就应该复制p接点到多项式中。
当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。
当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生
D：
2个多项式的减法
它从2个多项式的头部开始，2个多项式的某一项都不为空时，如果指数相等的话，系数就应该相减；相加的和不为0的话，用头插法建立一个新的节点。
p的系数小于q的系数的话，就应该复制q接点到多项式中。
p的系数大于q的系数的话，就应该复制p接点到多项式中，并且建立的接点的系数为原来的相反数；当第2个多项式空，第1个数不为空时，将第一个数剩下的全用新节点产生。
当第1个多项式空，第1个数不为空时，将第2个数剩下的全用新节点产生，并且建立的接点的系数为原来的相反数。
第三章详细设计
3.1、创建一个结点，表示多项式的一项
pnodecreate（char*c,inti,intj）{
if（jinta=0,b=0,flag=0;//a系数,b指数，flag指数正负记录。
if（!
isnum（c[i]））
a=1;
else
while（isnum（c[i]）&&i<=j）{
a=a*10+c[i]-'0';
i++;
}//跳过系数与指数间非数字字符。
while（!
isnum（c[i]）&&i<=j）
{
flag=1;
i++;
}//处理指数。
if（i>j&&flag==1）b=1;
else{
if（c[i-1]=='-'&&c[i-2]=='^'）flag=2;//指数是负数情况记录。
while（isnum（c[i]）&&i<=j）{
b=b*10+c[i]-'0';
i++;
}
}
if（flag==2）b=-b;//指数是负数情况处理。
pnodep;
p=（pnode）malloc（sizeof（node））;
p->x=a;
p->z=b;
returnp;
}//创建一个结点，表示多项式的一项。
把"12X^3"这样字符串转化成一个只有系数、指数、后继的结构体。
3.2、链式存储多项式
pnodecreate_duo（char*c,intm）{
if（c[m]=='\0'）returnNULL;
inti,j;
pnodep,q,*t;
i=m;
if（c[i]=='+'||c[i]=='-'）i++;
j=i;
while（c[j]!
='\0'&&c[j]!
='+'&&（c[j]!
='-'||c[j-1]=='^'））{
j++;
}//移动到多项式字符串的从下标m起第一项末。
if（c[i]!
='0'）
{
p=create（c,i,j-1）;
if（i>0&&c[i-1]=='-'）p->x=-（p->x）;
q=create_duo（c,j）;//处理下一项
if（q==NULL）
p->next=q;
elseif（q&&q->zz）
p->next=q;
elseif（q）{
t=&q;
while（*t!
=NULL）t=&（*t）->next;
*t=（pnode）malloc（sizeof（node））;
*t=p;
（*t）->next=NULL;
p=q;
}
returnp;
}
else
returncreate_duo（c,j）;//系数为0项，不建立，跳过。
}//把一元多项式的字符串用链式存储。
3.3、多项式的计算
pnodeplus（pnodep,pnodeq）{
pnodeP,H,t,m,n;
m=p;
n=q;
H=P=（pnode）malloc（sizeof（node））;
while（m!
=NULL&&n!
=NULL）{
t=（pnode）malloc（sizeof（node））;
if（m->z>n->z）{
t->x=m->x;
t->z=m->z;
m=m->next;
}
else
if（m->z==n->z）{
if（m->x==-（n->x））
{
m=m->next;
n=n->next;
continue;
}//指数相同，系数相反，情况处理。
t->x=m->x+n->x;
t->z=n->z;
m=m->next;
n=n->next;
}
else{
t->x=n->x;
t->z=n->z;
n=n->next;
}
P->next=t;
P=P->next;
}
while（m!
=NULL）{
t=（pnode）malloc（sizeof（node））;
t->x=m->x;
t->z=m->z;
m=m->next;
P->next=t;
P=P->next;
}
while（n!
=NULL）{
t=（pnode）malloc（sizeof（node））;
t->x=n->x;
t->z=n->z;
n=n->next;
P->next=t;
P=P->next;
}
P->next=NULL;
P=H;
H=H->next;
free（P）;
returnH;
}//两个一元多项式的相加。
pnodeminus（pnodep,pnodeq）
{
if（q==NULL）returnp;
pnodet,h,g,q1;
t=q;
h=（pnode）malloc（sizeof（node））;
h->x=-（t->x）;
h->z=t->z;
t=t->next;
q1=h;
g=h;
while（t!
=NULL）{
h=（pnode）malloc（sizeof（node））;
h->x=-（t->x）;
h->z=t->z;
g->next=h;
g=g->next;
t=t->next;
}
g->next=NULL;
if（p==NULL）returnq1;
return（plus（p,q1））;
}//两个一元多项式的差
3.4、释放结点
voidfree_pnode（pnodep）
{
pnodet;
while（p!
=NULL）
{
t=p;
p=p->next;
free（t）;
}
第四章运行界面
4.1、输入界面如图4-1：
图4-1
4.2、显示输出数据如图4-2：
图4-2
4.3、用户选择功能界面如图4-3
图4-3
4.4、各功能运行界面如图4-4：
图4-4
第五章总结
C++语言功能强,使用灵活,可移植性好,目标程序质量好,它既有高级语言的优点,又具有低级语言的许多特点,既可以用来编写系统软件,又可以编写应用软件
通过这次课程设计我觉得我们学习《数据结构》的方法存在一定的弊端,《数据结构》的效果直接影响到我们对其它专业课的学习和今后业务的成长。
我觉得我们对于《数据结构》的学习不仅包括理论部分的学习，还要让我们勤动手，多实践。
最后我要衷心的感谢所有给予我帮助和指导的老师和同学,没有他们的帮助我的程序也不会完成得这么顺利!
参考文献
[1]王挺．C++程序设计．北京：
清华大学出版社，2005.1．
[2]严蔚敏．数据结构：
C语言版．北京：
清华大学出版社，2007．
附录:
源代码;
#include
#include
#include
#defineN999
typedefstructnode{
intx,z;//x系数，z指数
structnode*next;
}*pnode;
intisnum（charc）
{
if（c>='0'&&c<='9'）return1;
elsereturn0;
}//判断用
pnodecreate（char*c,inti,intj）{
if（jinta=0,b=0,flag=0;//a系数,b指数，flag指数正负记录。
if（!
isnum（c[i]））
a=1;
else
while（isnum（c[i]）&&i<=j）{
a=a*10+c[i]-'0';
i++;
}//跳过系数与指数间非数字字符。
while（!
isnum（c[i]）&&i<=j）
{
flag=1;
i++;
}//处理指数。
if（i>j&&flag==1）b=1;
else{
if（c[i-1]=='-'&&c[i-2]=='^'）flag=2;//指数是负数情况记录。
while（isnum（c[i]）&&i<=j）{
b=b*10+c[i]-'0';
i++;
}
}
if（flag==2）b=-b;//指数是负数情况处理。
pnodep;
p=（pnode）malloc（sizeof（node））;
p->x=a;
p->z=b;
returnp;
}//创建一个结点，表示多项式的一项。
把"12X^3"这样字符串转化成一个只有系数、指数、后继的结构体。
pnodecreate_duo（char*c,intm）{
if（c[m]=='\0'）returnNULL;
inti,j;
pnodep,q,*t;
i=m;
if（c[i]=='+'||c[i]=='-'）i++;
j=i;
while（c[j]!
='\0'&&c[j]!
='+'&&（c[j]!
='-'||c[j-1]=='^'））{
j++;
}//移动到多项式字符串的从下标m起第一项末。
if（c[i]!
='0'）
{
p=create（c,i,j-1）;
if（i>0&&c[i-1]=='-'）p->x=-（p->x）;
q=create_duo（c,j）;//处理下一项
if（q==NULL）
p->next=q;
elseif（q&&q->zz）
p->next=q;
elseif（q）{
t=&q;
while（*t!
=NULL）t=&（*t）->next;
*t=（pnode）malloc（sizeof（node））;
*t=p;
（*t）->next=NULL;
p=q;
}
returnp;
}
else
returncreate_duo（c,j）;//系数为0项，不建立，跳过。
}//把一元多项式的字符串用链式存储。
pnodeplus（pnodep,pnodeq）{
pnodeP,H,t,m,n;
m=p;
n=q;
H=P=（pnode）malloc（sizeof（node））;
while（m!
=NULL&&n!
=NULL）{
t=（pnode）malloc（sizeof（node））;
if（m->z>n->z）{
t->x=m->x;
t->z=m->z;
m=m->next;
}
else
if（m->z==n->z）{
if（m->x==-（n->x））
{
m=m->next;
n=n->next;
continue;
}//指数相同，系数相反，情况处理。
t->x=m->x+n->x;
t->z=n->z;
m=m->next;
n=n->next;
}
else{
t->x=n->x;
t->z=n->z;
n=n->next;
}
P->next=t;
P=P->next;
}
while（m!
=NULL）{
t=（pnode）malloc（sizeof（node））;
t->x=m->x;
t->z=m->z;
m=m->next;
P->next=t;
P=P->next;
}
while（n!
=NULL）{
t=（pnode）malloc（sizeof（node））;
t->x=n->x;
t->z=n->z;
n=n->next;
P->next=t;
P=P->next;
}
P->next=NULL;
P=H;
H=H->next;
free（P）;
returnH;
}//两个一元多项式的相加。
pnodeminus（pnodep,pnodeq）
{
if（q==NULL）returnp;
pnodet,h,g,q1;
t=q;
h=（pnode）malloc（sizeof（node））;
h->x=-（t->x）;
h->z=t->z;
t=t->next;
q1=h;
g=h;
while（t!
=NULL）{
h=（pnode）malloc（sizeof（node））;
h->x=-（t->x）;
h->z=t->z;
g->next=h;
g=g->next;
t=t->next;
}
g->next=NULL;
if（p==NULL）returnq1;
return（plus（p,q1））;
}//两个一元多项式的差。
voidprint（pnodep）{
if（p==NULL）{
cout<<"0"<return;
}
while（p!
=NULL）{
if（p->x==-1&&p->z!
=0）cout<<"-";
elseif（p->x!
=1||p->z==0）
cout<x;
if（p->z）
{
cout<<"X";
if（p->z!
=1）
cout<<"^"<z;
}
p=p->next;
if（p!
=NULL&&p->x>0）cout<<"+";
}
cout<}//输出链式存储多项式。
voidmain（）
{
cout<<"********************************"<cout<<"****一元多项式的计算（和差积）****"<cout<<"********************************"<charch1[N];//="30X^45-X-9";
charch2[N];//="-4X^3-2X+1";
intn=1;
pnodep1,p2;
cout<<"输入第一个多项式，项按升序或降序排列（形式如.22X^31+X^22+X-1）:
\n";
cin>>ch1;
inti=0;
while（ch1[i]）{
if（ch1[i]<='*'||ch1[i]==','||（ch1[i]>='.'&&ch1[i]<='/'）||（ch1[i]>=':
'&&ch1[i]<='W'）||ch1[i]=='Y'||ch1[i]=='Z'||（ch1[i]>='_'&&ch1[i]<='w'）||ch1[i]>='y'）{
cout<<"删除错误字符"<intj=i;
while（ch1[j]）{
ch1[j]=ch1[j+1];
j++;
}
i--;
}i++;
}//删除错误字符
p1=create_duo（ch1,0）;
cout<<"输入第二个多项式，项按升序或降序排列（形式如.22X^31+X^24+X-1）:
\n";
cin>>ch2;
i=0;
while（ch2[i]）{
if（ch2[i]<='*'||ch2[i]==','||（ch2[i]>='.'&&ch2[i]<='/'）||（ch2[i]>=':
'&&ch2[i]<='W'）||ch2[i]=='Y'||ch2[i]=='Z'||（ch2[i]>='_'&&ch2[i]<='w'）||ch2[i]>='y'）{
cout<<"删除错误字符"<intj=i;
while（ch2[j]）{
ch2[j]=ch2[j+1];
j++;
}i--;
}i++;
}//删除错误字符
p2=create_duo（ch2,0）;
cout<<"多项式p1：
";
print（p1）;
cout<<"多项式p2：
";
print（p2）;
cout<<"******************************************"<cout<<"*********用户选择************"<cout<<"*********************"<cout<<"*********1.两多项式和************"<cout<<"*********************"<cout<<"*********2.两多项式差************"<cout<<"*********************"<cout<<"*********0.退出************"<cout<<"*********************"<cout<<"******************************************"<while（n）
{cout<<"请输入你的选择：
"
升级会员 