一元多项加法运算的实现
【问题描述】
设计一个程序，求解一元多项加法。
【基本要求】
如：A(x)=15+6x+9x7+3x18 B(x)=4x+5x6+16x7 求 A+B
【数据结构描述】
单链表的抽象数据类型定义：
ADT List{
数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}
数据关系：R1={<ai-1,ai>| ai-1, ai∈D,i=2,…,n}
基本操作：
InitList（﹠L）
操作结果：构造一个空的线性表
CreatPolyn(&L)
操作结果：构造一个以单链表存储的多项试
DispPolyn(L)
操作结果：显示多项试
Polyn(&pa,&pb)
操作结果：显示两个多项式相加的结果
} ADT List
【主要算法流程描述】
源程序代码
#include "stdio.h"
#include"malloc.h"
typedef struct LNode //定义单链表
{
int xishu; //系数
int zhishu; //指数
struct LNode *next;
}LNode,*LinkList;
void InitList(LinkList &L) //定义一个空表
{
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
return;
}
void CreatPolyn(LinkList &L) //用单链表定义一个多项式
{
int m;
LinkList q,p;
InitList(L);
q=L;
printf("输入项数:");
scanf("%d",&m);
printf("按降幂输入系数和指数:\n");
for(int i=0;i<m;i++)
{
p=(LinkList)malloc(sizeof(LNode)); //生成新结点
scanf("%d%d",&p->xishu,&p->zhishu);
p->next=NULL;
q->next=p;
q=p;
}
return;
}
void DispPolyn(LinkList L) //显示输入的多项式
{ LinkList p;
p=L->next;
printf("一元多项式为: \n" ) ;
while(p)
{
if(p->xishu>0) //如果系数大于0则加上+号
printf("+%dX^%d" ,p->xishu,p->zhishu);
else
printf("%d X^%d" ,p->xishu,p->zhishu);
p=p->next;
}
printf("\n");
return ;
}
void Polyn(LinkList &pa,LinkList &pb)
{
LNode *p,*q,*pre,*temp;
int t;
float sum=0;
CreatPolyn(pa);
DispPolyn(pa);
CreatPolyn(pb);
DispPolyn(pb);
p=pa->next; //p指向pa头结点
q=pb->next; //q指向qa头结点
pre=pa; //用来记录合成的多项式
while(p!=NULL&&q!=NULL) //当两个多项式都为完时
{
if(p->zhishu<q->zhishu) //如果q大于p的指数把q项存入
{
pre->next=q;
pre=pre->next;
q=q->next;
}
else if(p->zhishu==q->zhishu) //如果q等于p的指数把q项q项和存入
{
sum=p->xishu+q->xishu;
if(sum!=0)//如果和不为0
{
p->xishu=sum;
pre->next=p;
pre=pre->next;
p=p->next;
temp=q;
q=q->next;
free(temp);//释放temp
}
else //如果和为0
{
temp=p->next;
free(p);//释放p
p=temp;
temp=q->next;
free(q); //释放q
q=temp;
}
}
else //如果p大于q的指数把p项存入
{
pre->next=p;
pre=pre->next;
p=p->next;
}
}
if(p!=NULL) //如果p为完q完，则p接入
pre->next=p;
else //如果q为完p完，则q接入
pre->next=q;
printf("计算结果为");
DispPolyn(pa);
printf("\n");
}
void main()
{
LNode *L1,*L2;
Polyn(L1,L2);
}
【使用说明】
输入第一个多项式的项数，然后按降幂顺序输入系数和幂数，用空格间隔，再按照前面的方法输入第二个多项式，便可以得到相加的结果。
例如：
输入项数：2
按降幂输入系数和指数:
3 2
3 1
一元多项式为：
+3x^2+3x^1
输入项数：1
按降幂输入系数和指数:
4 2
一元多项式为：
4x^2
计算结果为一元多项式为：
+7x^2+3x^1
【调试分析说明】
这是用单链表解决多项式相加的问题，单链表一直是我的弱点，对单链表的使用我一直不能准确的把握，所以这个程序对我来说是个难点，调试过程中遇到了很多问题，比如函数调用不能实现，函数功能有漏洞等等。
【算法的改进设想】
这个程序的代码并不是太多，所以相对来说还是比较完整的程序，当然，还可以继续改进，比如多项式的输入是按降幂输入，可以考虑其他的多项式输入方法。
【总结】
单链表的使用我一直不能准确的把握，所以这个程序对我来说是个难点，所谓“明知山有虎，偏向虎山行”，通过做这个程序，我收获了不少东西。不管感觉问题有多复杂，我们都不应该放弃，坚持下去，自己总会有意想不到的收获！710