一元稀疏多项式求解问题
中文摘要
链表(Linked List)和顺序表(Sequential List)是程序语言中使用内存常用的方法，链表存储结构主要的不同在内存位置上不须相邻，顺序表是将线性表中的结点按其逻辑顺序依次存放在内存中的一组连续的存储单元中。故容易对链表做插入或删除的操作，对顺序表进行取长度，查找等相对容易。多项式的加，减，乘法等求解问题的运算正好实用链表，通过多项式指数值间的判断，进行系数间的加减乘法运算。
关键字:链表 ;顺序存储结构 ;多项式加、减、乘法;
1
序 言
链表(Linked List)，顺序表(Sequential List)和数组是程序语言中使用内存常用的方法，它们都为“有序列表”，就像火车一般，一个车厢接着一个车厢有序地连在一起。但数组结构必须在程序编译前就定好数组元素的大小，因此，常须事先预估数据量的多少，且在删除或增加元素后，在其后的元素都必须跟着移动，而降低了执行的效率，链表结构正好可以完全改善数组结构的缺点，而顺序表要连续的内存空间，其主要的不同点在于内存位置不须相邻，所以每项数都有一个连接栏，可以存放下一个数据的地址，这样便可形成列表结构。使用链表存储的目的及效果，在于“容易”对此结构作插入或删除的操作。而我们必须决定组成链表的结构类型，动态数据结构至少包含两种不同的字段声明，其中一个字段是指向同一个结构类型的结构指针，另外一个则是存放数据的基本数据类型。一元稀疏多项式的求解问题同样对于链表存储结构也适用，使算法简单化，更容易被人所理解，链表存储结构也在其他很多地方被用到。
2
目 录
中文摘要 ........................................................ 1
言 ........................................................ 2 序
目 录 ........................................................ 3 正 文 ........................................................ 4
1.采用类c语言定义相关的数据类型 ............................ 4
各模块的伪码算法 .......................................... 4 2.
2.1两个多项式的输入 ..................................... 4
2.2多项式进行降序排列 ................................... 5
2.3合并同类项 ........................................... 6
3.各函数间调用关系图 ........................................ 6
4.程序编码 .................................................. 7
5.调试分析 ................................................. 23
5.1调试中遇到的问题及对问题的解决方法 .................. 23
5.2算法的时间复杂度 .................................... 23
6.测试结果 ................................................. 23
6.1两个多项式的输入 .................................... 23
6.2进行加法运算 ........................................ 24
6.3进行减法运算 ........................................ 24
6.4乘法运算 ............................................ 25
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
总结
初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf
....................................................... 26 参考文献 ....................................................... 27
致 谢 ....................................................... 28
3
正 文
1.采用类c语言定义相关的数据类型
定义一元多项式链表:
typedef struct DXS
{ //定义一个多项式的结构体
double c,e; //c,e分别为系数和指数
int flag; //标记
struct DXS *next;
}DXS;
2.各模块的伪码算法
2.1两个多项式的输入
la=pa=new DXS; //为多项式A,B结点分配空间，并指向头指针
lb=pb=new DXS;
cout<<"请输入多项式A的项数(多项式为0，则算一项):";
cin>>n1;
na=n1; //保存第一条多项式的项数
cout<<"请输入A的数据(请按升序输入:第一项系数，第一项指数，第二项系数，第二项指数.....若为0，则输入0 0):"<
>pa->c>>pa->e;
p=pa;
pa=new DXS;
p->next=pa;
}
cout<>n2;
nb=n2; //保存第二条多项式的项数
cout<<"请输入B的数据(请按升序输入:第一项系数，第一项指数，
第二项系数，第二项指数.....若为0，则输入0 0):"<>pb->c>>pb->e;
q=pb;
pb=new DXS;
q->next=pb;
}
2.2多项式进行降序排列
void down(DXS *l1,DXS *l2,int b) //多项式指数降序排列函数 {
double f,g;
for(int c=b;c>1;c--)
{
for(int d=1;d e next->e)
{
f=l1->e;
l1->e=l1->next->e;
l1->next->e=f;
g=l1->c;
l1->c=l1->next->c;
l1->next->c=g;
}
5
l1=l1->next;
}
l1=l2;
}
}
2.3合并同类项
int arrange(DXS *s,DXS *head,int &b) //
检测
工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训
多项式中有没有相同项,
若有,则合并为一项
{
for(int c=b;c>1;c--)
{
if((s->e==s->next->e))
{
s->next->c = s->c + s->next->c;
if(s->next->c==0)
b--;
b--;
s->c=0;
}
s=s->next;
}
return b;
}
3.各函数间调用关系图
6
main( )
Polyn(L1,
L2)
CreatPolyDispPolyCreatPolyDispPoly
n(pa) n(pa) n(pb) n(pb) 4.程序编码
#include
using namespace std;
typedef struct DXS
{ //定义一个多项式的结构体
double c,e; //c,e分别为系数和指数
int flag; //标记
struct DXS *next;
}DXS;
void out(DXS *l,DXS *head,int a) //输出函数，参数为结点、头指针、多项式项数
{
if(a==0) //如果项数为0，则多项式为0
7
cout<<0;
for(int m=1;m <=a;m++)
{
if(l->e==1)
{
if(l==head) //分析第一个结点
{
if( l->flag==-1) //输出几个特殊的系数
{
l=l->next;
}
if(l->c==0)
{
cout<c;l=l ->next;
}
else if(l->e==0)
{
cout<c;l=l->next;
}
else if(l->c==1)
{
cout<<"x";
l=l->next;
}
else if(l->c==-1)
{
cout<<"-x";
8
l=l->next;
}
else
{
cout<c<<"x";l=l->next;
}
}
else //分析第一个之后的结点
{
if( l->flag==-1) //输出几个特殊结点
{
l=l->next;
}
if(l->c==0)
{
l=l->next;
}
else if(l->e==0)
{
if(l->c>0)
{
cout<<"+"<c;l=l->next;
}
else
{
cout<c;l=l->next;
}
}
9
else if(l->c==1)
{
cout<<"+x^";
l=l->next;
}
>c==-1) else if(l-
{
cout<<"-x";
l=l->next;
}
else if(l->c>0)
{
cout<<"+"<c<<"x";
l=l->next;
}
else if(l->c <0)
{
cout<c<<"x";
l=l->next;
}
}
}
else
{
if(l==head) //分析第一个结点
{
if( l->flag==-1) //输出几个特殊的系数
{
10
l=l->next;
}
if(l->c==0)
{
cout<c;l=l->next;
}
else if(l->e==0)
{
cout<c;
l=l->next;
}
else if(l->c==1)
{
cout<<"x^"<e;
l=l- >next;
}
else if(l->c==-1)
{
cout<<"-x^"<e;
l=l->next;
}
else
{
cout<c<<"x^"<e;
l=l->next;
}
}
else //分析第一个之后的结点
11
{
if( l->flag==-1) //输出几个特殊结点
{
l=l->next;
}
>c==0) if(l-
{
l=l->next;
}
else if(l->e==0)
{
if(l->c>0)
{
cout<<"+"<c;
l=l->next;
}
else
{
cout<c;
l=l->next;
}
}
else if(l->c==1)
{
cout<<"+x^"<e;
l=l->next;
}
else if(l->c==-1)
12
{
cout<<"-x^"<e;
l=l->next;
}
else if(l->c>0)
{
cout<<"+"<c<<"x^"<e;
l=l->next;
}
else if(l->c <0)
{
cout<c<<"x^"<e;
l=l->next;
}
}
}
}
}
void down(DXS *l1,DXS *l2,int b) //多项式指数降序排列函数 {
double f,g;
for(int c=b;c>1;c--)
{
for(int d=1;d e next->e)
{
f=l1->e;
13
l1->e=l1->next->e;
l1->next->e=f;
g=l1->c;
l1->c=l1->next->c;
l1->next->c=g;
}
l1=l1->next;
}
l1=l2;
}
}
void up(DXS *l1,DXS *l2,int b) //多项式指数升序排列函数
{
double f,g;
for(int c=b;c>1;c--)
{
for(int d=1;d e>l1->next->e)
{
f=l1->e;
l1->e=l1->next->e;
l1->next->e=f;
g=l1->c;
l1->c=l1->next->c;
l1->next->c=g;
}
l1=l1->next;
14
}
l1=l2;
}
}
int arrange(DXS *s,DXS *head,int &b) //检测多项式中有没有相
同项,若有,则合并为一项
{
for(int c=b;c>1;c--)
{
if((s->e==s->next->e))
{
s->next->c = s->c + s->next->c;
if(s->next->c==0)
b--;
b--;
s->c=0;
}
s=s->next;
}
return b;
}
int main()
{
DXS *pa,*pb,*pc; //定义三个多项式的结点
DXS *la,*lb,*lc; //定义三个多项式的头指针
DXS *p,*q,*s;
int n1,n2,n3,na,nb,nc; //多项式项数
int i,j=0;
15
char Q,Y;
la=pa=new DXS; //为多项式A,B结点分配空间，并指向头指针
lb=pb=new DXS;
cout<<"请输入多项式A的项数(多项式为0，则算一项):";
cin>>n1;
na=n1; //保存第一条多项式的项数
cout<<"请输入A的数据(请按升序输入:第一项系数，第一项指数，
第二项系数，第二项指数.....若为0，则输入0 0):"<>pa->c>>pa->e;
p=pa;
pa=new DXS;
p->next=pa;
}
cout<>n2;
nb=n2; //保存第二条多项式的项数
cout<<"请输入B的数据(请按升序输入:第一项系数，第一项指数，
第二项系数，第二项指数.....若为0，则输入0 0):"<>pb->c>>pb->e;
q=pb;
pb=new DXS;
q->next=pb;
}
16
pa=la; //重新指向头指针
pb=lb;
cout<>Q;
cout<<"希望降序还是升序排列(S:升序/J:降序):";
cin>>Y;
cout<c=(-1)*pb->c;
pb=pb->next;
}
pb=lb;
}
case'+':
{
lc=pc=new DXS;//为多项式C结点分配空间，并指向头指针
if(n1==1&&la->c==0) //关于有多项式为0的处理
n1--;
else if(n2==1&&lb->c==0)
n2--;
while(n1>0&&n2>0) //两个不为0的多项式的运算，结
果放到C中
{
if(pa->e>pb->e)
{
pc->c=pb->c;
pc->e=pb->e;
pb=pb->next;
pc->flag=0;
s=pc;
pc=new DXS; //重新分配结点空间
s->next=pc;
j++;
n2--;
}
18
else if(pa->e e)
{
pc->c=pa->c;
pc->e=pa->e;
pa=pa->next;
>flag=0; pc-
s=pc;
pc=new DXS;
s->next=pc;
j++;
n1--;
}
else if(pa->e==pb->e)
{
if(pa->c+pb- >c!=0)
{
pc->c=pa->c+pb->c;
pc->e=pa->e;
pa=pa->next;
pb=pb->next;
pc->flag=0;
s=pc;
pc=new DXS;
s->next=pc;
j++;
n1--;
n2--;
}
19
if(pa->c+pb->c==0)
{
pa=pa->next;
pb=pb->next;
n1--;
n2--;
}
}
}
while(n1>0) //把较长的多项式的其余部分放到C中
{
pc->c=pa->c;
pc->e=pa->e;
pa=pa->next;
pc->flag=0;
s=pc;
pc=new DXS;
s->next=pc;
j++;
n1--;
}
while(n2>0)
{
pc->c=pb->c;
pc->e=pb->e;
pb=pb->next;
pc->flag=0;
s=pc;
20
pc=new DXS;
s->next=pc;
j++;
n2--;
}
break;
}
case'*':
{
lc=pc=new DXS;//为多项式C结点分配空间，并指向头指针
if(n1==1&&la->c==0) //关于有多项式为0的处理
n1--;
else if(n2==1&&lb->c==0)
n2--;
while(n1>0)
{
pb=lb;
n2=nb;
while(n2>0)
{
pc->c=pa->c*pb->c;pc->e=pa->e+pb->e;
pb=pb->next;
pc->flag=0;
s=pc;
pc=new DXS;
s->next=pc;
j++;
n2--;
21
}
pa=pa->next;
n1--;
}
break;
}
default: cout<<"输入有误";
}
nc=n3=j; //结果多项式的项数
cout<
本文档为【一元稀疏多项式求解问题】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483