利用线性表实现一个一元多项式 Polynomial f(x) = a0 + a1x + a2x 2 + a3x 3 + … + anx n 提示： Polynomial 的结点结构如下： struct term { 北 float coef; //系数 int expn; //指数 }; 可以使用链表实现，也可以使用顺序表实现。 要求： ➢ 能够实现一元多项式的输入和输出 ➢ 能够进行一元多项式相加 ➢ 能够进行一元多项式相减 ➢ 能够计算一元多项式在 x 处的值 ➢ 能够计算一元多项式的导数 ➢ 能够进行一元多项式相乘 ➢ 编写测试 main()函数测试线性表的正确性

链表实现：

#include<iostream>
using namespace std;

struct term {
float coef; //系数
int expn; //指数
term *next; //下一个结点的指针
};

//创建一个系数为0，指数为0的头结点
term *createHead() {
term *head = new term;
head->coef = 0;
head->expn = 0;
head->next = NULL;
return head;
}

//添加一个结点到多项式中
void addTerm(term *head, float coef, int expn) {
term *node = new term;
node->coef = coef;
node->expn = expn;
node->next = NULL;

term *p = head->next;
//如果当前结点的指数小于前一个结点的指数，则把结点插入到前一个结点之前
while (p!= NULL && p->expn > expn) {
if (p->next == NULL || p->next->expn < expn) {
node->next = p->next;
p->next = node;
return;
}
p = p->next;
}
//如果相同指数则相加，如果是第一个结点则直接添加
if (p != NULL && p->expn == expn) {
p->coef += coef;
if (p->coef == 0) {
term *q = head;
while (q->next != NULL && q->next != p) {
q = q->next;
}
q->next = p->next;
delete p;
}
}
else {
node->next = head->next;
head->next = node;
}
}

//输出多项式
void print(term *head) {
term *p = head->next;
while (p!= NULL) {
cout << p->coef << "x^" << p->expn << " ";
p = p->next;
}
cout << endl;
}

//相加多项式
void add(term *head1, term *head2, term *res) {
term *p = head1->next;
term *q = head2->next;
while (p!= NULL && q!= NULL) {
if (p->expn < q->expn) {
addTerm(res, q->coef, q->expn);
q = q->next;
}
else if (p->expn > q->expn) {
addTerm(res, p->coef, p->expn);
p = p->next;
}
else {
addTerm(res, p->coef + q->coef, p->expn);
p = p->next;
q = q->next;
}
}
while (p!= NULL) {
addTerm(res, p->coef, p->expn);
p = p->next;
}
while (q!= NULL) {
addTerm(res, q->coef, q->expn);
q = q->next;
}
}

//相减多项式
void sub(term *head1, term *head2, term *res) {
term *p = head1->next;
term *q = head2->next;
while (p!= NULL && q!= NULL) {
if (p->expn < q->expn) {
addTerm(res, -q->coef, q->expn);
q = q->next;
}
else if (p->expn > q->expn) {
addTerm(res, p->coef, p->expn);
p = p->next;
}
else {
addTerm(res, p->coef - q->coef, p->expn);
p = p->next;
q = q->next;
}
}
while (p!= NULL) {
addTerm(res, p->coef, p->expn);
p = p->next;
}
while (q!= NULL) {
addTerm(res, -q->coef, q->expn);
q = q->next;
}
}

//计算多项式在x处的值
float calc(term *head, float x) {
term *p = head->next;
float res = 0;
while (p!= NULL) {
res += p->coef * pow(x, p->expn);
p = p->next;
}
return res;
}

//计算多项式的导数
void derivative(term *head, term *res) {
term *p = head->next;
while (p!= NULL) {
if (p->expn > 0) {
addTerm(res, p->coef * p->expn, p->expn - 1);
}
p = p->next;
}
}

//相乘多项式
void mul(term *head1, term *head2, term *res) {
term *p = head1->next;
term *q = head2->next;
while (p!= NULL) {
while (q!= NULL) {
int expn = p->expn + q->expn;
float coef = p->coef * q->coef;
addTerm(res, coef, expn);
q = q->next;
}
q = head2->next;
p = p->next;
}
}

int main() {
//创建多项式1
term *head1 = createHead();
addTerm(head1, 3, 3);
addTerm(head1, 2, 1);
addTerm(head1, 1, 0);
cout << "f(x) = ";
print(head1);

//创建多项式2
term *head2 = createHead();
addTerm(head2, 7, 4);
addTerm(head2, 2, 2);
addTerm(head2, 3, 0);
cout << "g(x) = ";
print(head2);

//相加多项式
term *head3 = createHead();
add(head1, head2, head3);
cout << "f(x) + g(x) = ";
print(head3);

//相减多项式
term *head4 = createHead();
sub(head1, head2, head4);
cout << "f(x) - g(x) = ";
print(head4);

//计算多项式在x处的值
float x = 2;
cout << "f(" << x << ") = " << calc(head1, x) << endl;

//计算多项式的导数
term *head5 = createHead();
derivative(head1, head5);
cout << "f'(x) = ";
print(head5);

//相乘多项式
term *head6 = createHead();
mul(head1, head2, head6);
cout << "f(x) * g(x) = ";
print(head6);
}