使用链表实现多项式求值完整代码 数据结构
时间: 2023-08-05 18:17:35 浏览: 50
下面是使用链表实现多项式求值的完整代码,包含数据结构的定义和相关函数的实现:
```cpp
#include <iostream>
#include <cmath>
using namespace std;
// 定义多项式项结构体
struct PolyNode {
int coef; // 系数
int exp; // 指数
PolyNode* next; // 指向下一个节点的指针
};
// 定义多项式类
class Polynomial {
public:
Polynomial(); // 构造函数
~Polynomial(); // 析构函数
void insertTerm(int coef, int exp); // 插入一项
void printPolynomial(); // 输出多项式
double evaluate(double x); // 求多项式在 x 处的值
private:
PolyNode* head; // 多项式链表的头指针
};
// 构造函数
Polynomial::Polynomial() {
head = new PolyNode;
head->next = NULL;
}
// 析构函数
Polynomial::~Polynomial() {
PolyNode* p = head;
while (p) {
PolyNode* q = p;
p = p->next;
delete q;
}
}
// 插入一项
void Polynomial::insertTerm(int coef, int exp) {
PolyNode* p = head;
while (p->next && p->next->exp > exp) {
p = p->next;
}
if (p->next && p->next->exp == exp) {
p->next->coef += coef;
if (p->next->coef == 0) {
PolyNode* q = p->next;
p->next = q->next;
delete q;
}
} else {
PolyNode* q = new PolyNode;
q->coef = coef;
q->exp = exp;
q->next = p->next;
p->next = q;
}
}
// 输出多项式
void Polynomial::printPolynomial() {
PolyNode* p = head->next;
if (!p) {
cout << "0" << endl;
return;
}
while (p) {
cout << p->coef << "x^" << p->exp;
p = p->next;
if (p) {
cout << " + ";
}
}
cout << endl;
}
// 求多项式在 x 处的值
double Polynomial::evaluate(double x) {
double sum = 0;
PolyNode* p = head->next;
while (p) {
sum += p->coef * pow(x, p->exp);
p = p->next;
}
return sum;
}
int main() {
Polynomial p;
p.insertTerm(2, 3);
p.insertTerm(-1, 2);
p.insertTerm(3, 1);
p.insertTerm(4, 0);
p.printPolynomial();
cout << "p(2) = " << p.evaluate(2) << endl;
return 0;
}
```
这个程序中,多项式项使用 `PolyNode` 结构体来表示,包含系数 `coef` 和指数 `exp` 两个成员变量,以及指向下一个节点的指针 `next`。多项式类 `Polynomial` 包含一个头指针 `head`,指向多项式链表的头节点。类中实现了插入一项、输出多项式以及求多项式在某个值 x 处的值等操作。在 `main` 函数中,我们创建了一个多项式 p,并插入了四项,然后输出多项式并求出了 p(2) 的值。