使用链表实现多项式求值
时间: 2023-11-18 12:05:38 浏览: 29
多项式可以表示为 $a_nx^n + a_{n-1}x^{n-1} + \cdots + a_1x + a_0$ 的形式,其中 $a_i$ 表示系数,$x$ 表示变量,$n$ 表示次数。使用链表实现多项式可以将每一项作为一个节点,每个节点包含系数和次数两个属性。具体实现步骤如下:
1. 定义一个节点结构体,包含系数和次数两个属性:
```c++
struct Node {
int coef; // 系数
int exp; // 次数
Node* next;
};
```
2. 定义一个链表类,包含头结点和链表长度两个属性,以及添加节点、求值等方法:
```c++
class Polynomial {
public:
Polynomial() {
head = new Node();
head->next = nullptr;
length = 0;
}
void addTerm(int coef, int exp) {
Node* node = new Node();
node->coef = coef;
node->exp = exp;
node->next = nullptr;
Node* p = head;
while (p->next != nullptr && p->next->exp > exp) {
p = p->next;
}
if (p->next != nullptr && p->next->exp == exp) { // 合并同类项
p->next->coef += coef;
delete node;
} else {
node->next = p->next;
p->next = node;
length++;
}
}
int evaluate(int x) {
int result = 0;
Node* p = head->next;
while (p != nullptr) {
result += p->coef * pow(x, p->exp);
p = p->next;
}
return result;
}
private:
Node* head;
int length;
};
```
3. 在 `main` 函数中创建多项式对象并添加项,然后调用 `evaluate` 方法求值:
```c++
int main() {
Polynomial poly;
poly.addTerm(2, 4); // 添加 2x^4
poly.addTerm(3, 2); // 添加 3x^2
poly.addTerm(1, 1); // 添加 1x^1
poly.addTerm(5, 0); // 添加 5x^0
int x = 2;
int result = poly.evaluate(x); // 对 x=2 求值
cout << "f(" << x << ") = " << result << endl;
return 0;
}
```
以上代码实现的是一个简单的多项式求值功能,可以根据需要进一步扩展。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)