搜搜考试网C++设计：一元多项式相加
来源：学生作业帮 编辑：搜搜考试网作业帮 分类：综合作业 时间：2024/05/26 17:12:04
C++设计：一元多项式相加
1.
已知 A ( x ) = a 0 + a 1 x + a 2 x 2 + …… + a n x n 和 B ( x ) = b 0 + b 1 x + b 2 x 2 + …… + b m x m ,并且在 A ( x ) 和 B ( x ) 中指数相差很多,求 A ( x ) = A ( x ) + B ( x ) .
2.基本要求
⑴ 设计存储结构表示一元多项式； ⑵ 设计算法实现一元多项式相加； ⑶ 分析算法的时间复杂度和空间复杂度.
3.设计思想
一元多项式求和 实质上是合并同类项的过程,其运算规则为：⑴ 若两项的指数相等,则系数相加； ⑵ 若两项的指数不等,则将两项加在结果中.
一元多项式 A ( x ) =a 0 +a 1 x+a 2 x 2 + …… +a n x n 由 n +1 个系数唯一确定,因此,可以用一个线性表 ( a 0 ,a 1 ,a 2 ,……,a n ) 来表示,每一项的指数 i 隐含在其系数 a i 的序号里.但是,当多项式的指数很高且变化很大时,在表示多项式的线性表中就会存在很多零元素.一个较好的存储方法是只存非零元素,但是需要在存储非零元素系数的同时存储相应的指数.这样,一个一元多项式的每一个非零项可由系数和指数唯一表示.
由于两个一元多项式相加后,会改变多项式的系数和指数,因此采用顺序表不合适.采用单链表存储,则每一个非零项对应单链表中的一个结点,且单链表应按指数递增有序排列.结点结构如图 2 - 2 所示.
其中,coef ：系数域,存放非零项的系数； exp ：指数域,存放非零项的指数； next ：指针域,存放指向下一结点的指针.
将两个一元多项式用两个单链表存储后,如何实现二者相加呢?设两个工作指针 p 和 q ,分别指向两个单链表的开始结点.通过对结点 p 的指数域和结点 q 的指数域进行比较进行同类项合并,则出现下列三种情况：⑴ 若 p -> exp exp ,则结点 p 应为结果中的一个结点； ⑵ 若 p -> exp>q -> exp ,则结点 q 应为结果中的一个结点,将 q 插入到第一个链表中结点 p 之前； ⑶ 若 p -> exp=q -> exp ,则结点 p 与结点 q 为同类项,将 q 的系数加到 p 的系数上.若相加结果不为 0 ,则结点 p 应为结果中的一个结点,同时删除结点 q ；若相加结果为 0 ,则表明结果中无此项,删除结点 p 和结点 q ； 算法用伪代码描述如下：
1.
已知 A ( x ) = a 0 + a 1 x + a 2 x 2 + …… + a n x n 和 B ( x ) = b 0 + b 1 x + b 2 x 2 + …… + b m x m ,并且在 A ( x ) 和 B ( x ) 中指数相差很多,求 A ( x ) = A ( x ) + B ( x ) .
2.基本要求
⑴ 设计存储结构表示一元多项式； ⑵ 设计算法实现一元多项式相加； ⑶ 分析算法的时间复杂度和空间复杂度.
3.设计思想
一元多项式求和 实质上是合并同类项的过程,其运算规则为：⑴ 若两项的指数相等,则系数相加； ⑵ 若两项的指数不等,则将两项加在结果中.
一元多项式 A ( x ) =a 0 +a 1 x+a 2 x 2 + …… +a n x n 由 n +1 个系数唯一确定,因此,可以用一个线性表 ( a 0 ,a 1 ,a 2 ,……,a n ) 来表示,每一项的指数 i 隐含在其系数 a i 的序号里.但是,当多项式的指数很高且变化很大时,在表示多项式的线性表中就会存在很多零元素.一个较好的存储方法是只存非零元素,但是需要在存储非零元素系数的同时存储相应的指数.这样,一个一元多项式的每一个非零项可由系数和指数唯一表示.
由于两个一元多项式相加后,会改变多项式的系数和指数,因此采用顺序表不合适.采用单链表存储,则每一个非零项对应单链表中的一个结点,且单链表应按指数递增有序排列.结点结构如图 2 - 2 所示.
其中,coef ：系数域,存放非零项的系数； exp ：指数域,存放非零项的指数； next ：指针域,存放指向下一结点的指针.
将两个一元多项式用两个单链表存储后,如何实现二者相加呢?设两个工作指针 p 和 q ,分别指向两个单链表的开始结点.通过对结点 p 的指数域和结点 q 的指数域进行比较进行同类项合并,则出现下列三种情况：⑴ 若 p -> exp exp ,则结点 p 应为结果中的一个结点； ⑵ 若 p -> exp>q -> exp ,则结点 q 应为结果中的一个结点,将 q 插入到第一个链表中结点 p 之前； ⑶ 若 p -> exp=q -> exp ,则结点 p 与结点 q 为同类项,将 q 的系数加到 p 的系数上.若相加结果不为 0 ,则结点 p 应为结果中的一个结点,同时删除结点 q ；若相加结果为 0 ,则表明结果中无此项,删除结点 p 和结点 q ； 算法用伪代码描述如下：
#include
#include
#define len sizeof(LNode)
typedef struct Lnode //结点结构声明
{ int nf; // 多项式系数
\x09int ne; //多项式幂指数
\x09struct LNode *next;
}LNode;
typedef LNode *Pol;
LNode *creat(void) //创建多项式函数
{ LNode *head,*q;
LNode *n;
head=q=n=(LNode *)malloc(len);
q->next=NULL;
do{n=(LNode *)malloc(len);
cin>>n->ne>>n->nf;
q->next=n;
q=n;}while(n->nf!=0||n->ne!=0);
q->next=NULL;
return head;}
LNode *output(LNode *head) //输出多项式的函数
{LNode *p;
p=head->next;int n=0;
if(p->nf==0&&p->ne==0) {coutne==0) {coutnf+p2->nf;p2=p2->next;}
else {pr->next=p2;p2=p2->next; pr=pr->next;pr->next=p1;}
if(p1->ne==0&&p2->next==NULL) break;}
p1->next=p2;
return p0;
}
void main()//主函数
{char y;
for(;;){Pol p1,p2,p3;
cout
再问： 直接把C++文件发到邮箱1424302624@qq.com，直接回复不给分
再答： 已发
#include
#define len sizeof(LNode)
typedef struct Lnode //结点结构声明
{ int nf; // 多项式系数
\x09int ne; //多项式幂指数
\x09struct LNode *next;
}LNode;
typedef LNode *Pol;
LNode *creat(void) //创建多项式函数
{ LNode *head,*q;
LNode *n;
head=q=n=(LNode *)malloc(len);
q->next=NULL;
do{n=(LNode *)malloc(len);
cin>>n->ne>>n->nf;
q->next=n;
q=n;}while(n->nf!=0||n->ne!=0);
q->next=NULL;
return head;}
LNode *output(LNode *head) //输出多项式的函数
{LNode *p;
p=head->next;int n=0;
if(p->nf==0&&p->ne==0) {coutne==0) {coutnf+p2->nf;p2=p2->next;}
else {pr->next=p2;p2=p2->next; pr=pr->next;pr->next=p1;}
if(p1->ne==0&&p2->next==NULL) break;}
p1->next=p2;
return p0;
}
void main()//主函数
{char y;
for(;;){Pol p1,p2,p3;
cout
再问： 直接把C++文件发到邮箱1424302624@qq.com，直接回复不给分
再答： 已发
C++设计：一元多项式相加
数据结构一元多项式相加
两个一元多项式相加
单链表实现一元多项式相加
数据结构（C语言）用单链表存储一元多项式,并实现两个多项式的相加运算
设计一个一元多项式简单的计算器(C语言)
基本内容：设计一个一元稀疏多项式简单计算器.输入并建立多项式、按指数降序输出多项式、多项式相加、多
数据结构（C语言） 如何分别用顺序和链式 实现一元多项式的相加?
如何用C语言实现两个一元多项式的相加和相乘?
一元多项式的表示及相加
在C语言实现的一元多项式的相加操作中,怎样同时实现合并一个多项式中的同类项?
一元多项式的简单计算设计一个一元的简单计算器基本要求：1、输入并建立多项式2、输出多项式3、两个多箱式相加,建立并输出和