#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
typedef int Elemtype;
typedef int Status;
typedef struct PNode//定义多项式
{
float coef;//系数cofficient
Elemtype expn;//指数exponent
struct PNode* next;//地址域
}PNode, * Polynomial;
Status InitPolyn(Polynomial& P);//初始化多项式
Status CreatePolyn(Polynomial& P, int i);//创建多项式
Status AddPolyn(Polynomial& Pa, Polynomial& Pb);//多项式的加法运算
Status PrintPolyn(Polynomial P);//在单链表中打印元素
int main(void)
{
int a, b;
a = b = 0;
Polynomial Pa, Pb;
InitPolyn(Pa);
InitPolyn(Pb);
cout << "创建链表Pa的长度为:";
cin >> a;
CreatePolyn(Pa,a);
cout << "创建链表Pb的长度为:";
cin >> b;
CreatePolyn(Pb, b);
AddPolyn(Pa, Pb);
PrintPolyn(Pa);
return 0;
}
Status InitPolyn(Polynomial& P)//初始化一个只有头结点的单链表
{
P = new PNode;
P->next = NULL;
return OK;
}
Status CreatePolyn(Polynomial& P, int i)
{
PNode* p, * pre, * q;
cout << "\n输入多项式的相关数据为(系数和指数):";
for (int t = 0; t < i; t++)
{
p = new PNode;//生成一个新节点*p
cin >> p->coef >> p->expn;//输入当前项指数expn和系数coef
pre = P;//pre用于保存q的前驱节点,初始时指向头节点,用于找到第一个大于输入项指数的节点的前驱
q = P->next;//q初始化,指向首元节点
while (q && (q->expn < p->expn))//比较指数,找到第一个大于输入项指数的项*q
{
pre = q;
q = q->next;
}
p->next = q;//赋值生成节点*p的指针域 将输入项p插入*q和其前驱节点pre之间
pre->next = p;
}
return OK;
}
Status AddPolyn(Polynomial& Pa, Polynomial& Pb)
{
PNode* p1, * p2, * p3, * r;
p1 = Pa->next, p2 = Pb->next, p3 = Pa;
while (p1 && p2)//p1,p2都不为空
{
if (p1->expn == p2->expn)//p1指向的指数等于p2指向的指数
{
float sum = 0;
sum = p1->coef + p2->coef;//sum表示两个系数之和
if (sum != 0)
{
p1->coef = sum;
p3->next = p1;
p3 = p1;
p1 = p1->next;
r = p2;
p2 = p2->next;
delete r;
}
else
{
r = p1;
p1 = p1->next;
delete r;
r = p2;
p2 = p2->next;
delete r;
}
}
else
{
if (p1->expn < p2->expn)
{
p3->next = p1;
p3 = p1;
p1 = p1->next;
}
else
{
p3->next = p2;
p3 = p2;
p2 = p2->next;
}
}
}
p3->next = p1 ? p1 : p2;//将非空表的剩余段插入到pc
delete Pb;//释放Lb的头结点
return OK;
}
Status PrintPolyn(Polynomial P)
{
PNode* p;
p = P->next;
if (p == NULL)
{
cout << "\n表不存在。";
return ERROR;
}
while (p != NULL)
{
cout << "\n系数为:";
cout << p->coef << " ";
cout << "\n指数为:";
cout << p->expn << " ";
p = p->next;
}
return OK;
}