【浙江大学】数据结构
多项式的和与积
#include<iostream>
using namespace std;
typedef struct PolyNode
{
int coef; //常数
int expon; //系数
struct PolyNode* next; //指向下一节点的指针
}* Polynomial;
Polynomial CreatePolynomial(Polynomial P, int num); //创建多项式
int Compare(int expon1, int expon2); //比较系数大小
Polynomial PolynomialAdd(Polynomial P1, Polynomial P2); // 多项式相加
Polynomial PolynomialMulti(Polynomial P1, Polynomial P2); //多项式相乘
void AttachPolynomial(int coef, int expon, Polynomial* rear); //多项式链接(注意：指针的指针)
void Output(Polynomial P); //输出多项式
int main(void)
{
Polynomial P1 = NULL, P2 = NULL, Export = NULL;
int x1, x2;
cout << "第一项项数：";
cin >> x1;
P1 = CreatePolynomial(P1, x1);
Output(P1);
cout << "第二项项数：";
cin >> x2;
P2 = CreatePolynomial(P2, x2);
Output(P2);
cout << "多项式的和：";
Export = PolynomialAdd(P1, P2);
Output(Export);
cout << "多项式的积：";
Export = PolynomialMulti(P1, P2);
Output(Export);
return 0;
}
Polynomial CreatePolynomial(Polynomial P, int num)
{
// P = (Polynomial)malloc(sizeof(PolyNode));
Polynomial Q;
P = new PolyNode;
P->next = NULL;
Q = P;
Polynomial temp;
int i;
for (i = 0; i < num; i++) //链接
{
temp = new PolyNode;
cout << "输入常数：";
cin >> temp->coef;
cout << "输入系数：";
cin >> temp->expon;
/*Q->next = temp;
Q = temp;
temp->next = NULL;*/
AttachPolynomial(temp->coef, temp->expon, &Q);
}
return P;
}
int Compare(int expon1, int expon2)
{
if (expon1 > expon2)
return 1;
else if (expon1 < expon2)
return -1;
else
return 0;
}
Polynomial PolynomialAdd(Polynomial P1, Polynomial P2)
{
Polynomial front, rear;
int sum;
P1 = P1->next;
P2 = P2->next;
rear = new PolyNode;
front = rear; //front记录多项式头节点的位置
while (P1 && P2)
{
switch (Compare(P1->expon, P2->expon))
{
case 1:
AttachPolynomial(P1->coef, P1->expon, &rear);
P1 = P1->next;
break;
case -1:
AttachPolynomial(P2->coef, P2->expon, &rear);
P2 = P2->next;
break;
case 0:
sum = P1->coef + P2->coef;
if (sum != 0)
AttachPolynomial(sum, P1->expon, &rear);
P1 = P1->next;
P2 = P2->next;
break;
}
}
while (P1 != NULL) //拼接剩余项
{
AttachPolynomial(P1->coef, P1->expon, &rear);
P1 = P1->next;
}
while (P2 != NULL)
{
AttachPolynomial(P2->coef, P2->expon, &rear);
P2 = P2->next;
}
rear->next = NULL;
return front;
}
Polynomial PolynomialMulti(Polynomial P1, Polynomial P2)
{
Polynomial front = new PolyNode, rear, temp, TP1, TP2;
int tcoef, texpon;
front->next = NULL;
rear = front;
TP1 = P1;
TP2 = P2;
TP1 = TP1->next;
TP2 = TP2->next;
while (TP2) //先计算出一项的结果，然后再按降序插入
{
AttachPolynomial(TP1->coef * TP2->coef, TP1->expon + TP2->expon, &rear);
TP2 = TP2->next;
}
//Output(front);
TP1 = TP1->next;
while (TP1)
{
rear = front; //指针返回
TP2 = P2->next; //第二项返回
while (TP2)
{
tcoef = TP1->coef * TP2->coef;
texpon = TP1->expon + TP2->expon;
while (rear->next && rear->next->expon > texpon) //比较的是rear的下一项，这样正好可以找到满足的前一项
rear = rear->next;
if (rear->next && rear->next->expon == texpon) //指数相等情况
{
if (rear->next->coef + tcoef) //判断是否等于0，不为零直接加，为0删除
rear->next->coef += tcoef;
else
{
temp = rear->next;
rear->next = temp->next;
delete temp;
}
}
else //小于情况需要往中间插入结点，另外写，无法调用attach函数,
{
temp = new PolyNode;
temp->coef = tcoef;
temp->expon = texpon;
temp->next = NULL;
temp->next = rear->next;
rear->next = temp;
rear = rear->next;
}
TP2 = TP2->next;
}
TP1 = TP1->next;
}
return front;
}
void AttachPolynomial(int coef, int expon, Polynomial* rear)
{
Polynomial P = new PolyNode;
P->next = NULL;
P->coef = coef;
P->expon = expon;
(* rear)->next = P;
*rear = P;
(* rear)->next = NULL;
}
void Output(Polynomial P)
{
P = P->next;
while (P)
{
cout << P->coef << "x" << P->expon;
if (P->next)
{
if (P->next->coef > 0)
{
cout << "+";
}
}
P = P->next;
}
cout << endl;
}
