【浙江大學(xué)】數(shù)據(jù)結(jié)構(gòu)
多項(xiàng)式的和與積
#include<iostream>
using namespace std;
typedef struct PolyNode
{
int coef;?//常數(shù)
int expon; //系數(shù)
struct PolyNode* next; //指向下一節(jié)點(diǎn)的指針?
}* Polynomial;
Polynomial CreatePolynomial(Polynomial P, int num);?//創(chuàng)建多項(xiàng)式
int Compare(int expon1, int expon2);?//比較系數(shù)大小
Polynomial PolynomialAdd(Polynomial P1, Polynomial P2);?// 多項(xiàng)式相加
Polynomial PolynomialMulti(Polynomial P1, Polynomial P2);?//多項(xiàng)式相乘
void AttachPolynomial(int coef, int expon, Polynomial* rear);?//多項(xiàng)式鏈接(注意：指針的指針)
void Output(Polynomial P);?//輸出多項(xiàng)式?
int main(void)
{
Polynomial P1 = NULL, P2 = NULL, Export = NULL;
int x1, x2;
cout << "第一項(xiàng)項(xiàng)數(shù)：";
cin >> x1;
P1 = CreatePolynomial(P1, x1);
Output(P1);
cout << "第二項(xiàng)項(xiàng)數(shù)：";
cin >> x2;
P2 = CreatePolynomial(P2, x2);
Output(P2);
cout << "多項(xiàng)式的和：";
Export = PolynomialAdd(P1, P2);
Output(Export);
cout << "多項(xiàng)式的積：";
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 << "輸入常數(shù)：";
cin >> temp->coef;
cout << "輸入系數(shù)：";
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記錄多項(xiàng)式頭節(jié)點(diǎn)的位置?
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)?//拼接剩余項(xiàng)?
{
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)?//先計(jì)算出一項(xiàng)的結(jié)果，然后再按降序插入
{
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;?//第二項(xiàng)返回
while (TP2)
{
tcoef = TP1->coef * TP2->coef;
texpon = TP1->expon + TP2->expon;
while (rear->next && rear->next->expon > texpon)?//比較的是rear的下一項(xiàng)，這樣正好可以找到滿足的前一項(xiàng)
rear = rear->next;
if (rear->next && rear->next->expon == texpon)?//指數(shù)相等情況
{
if (rear->next->coef + tcoef)?//判斷是否等于0，不為零直接加，為0刪除
rear->next->coef += tcoef;
else
{
temp = rear->next;
rear->next = temp->next;
delete temp;
}
}
else?//小于情況需要往中間插入結(jié)點(diǎn)，另外寫，無法調(diào)用attach函數(shù),
{
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;
}
