怎么用一个程序用顺序表实现一元稀疏多项式的加减法,用单链表实现乘法啊
望采纳
可以使用结构体来表示一个一元稀疏多项式的一项,并使用顺序表或单链表来存储多项式的各个项。
下面代码展示了如何使用顺序表来实现一元稀疏多项式的加法
#include <iostream>
#include <vector>
using namespace std;
struct Term {
int coefficient; // 系数
int exponent; // 指数
};
// 一元稀疏多项式类型
typedef vector<Term> Polynomial;
// 多项式加法
Polynomial operator+(const Polynomial& p1, const Polynomial& p2) {
Polynomial result; // 结果多项式
int i = 0, j = 0; // p1 和 p2 的指针
while (i < p1.size() && j < p2.size()) {
if (p1[i].exponent > p2[j].exponent) {
// p1 的当前项的指数更大,将它加入结果
result.push_back(p1[i++]);
} else if (p1[i].exponent < p2[j].exponent) {
// p2 的当前项的指数更大,将它加入结果
result.push_back(p2[j++]);
} else {
// p1 和 p2 的当前项的指数相同,将它们的系数相加后加入结果
result.push_back({p1[i].coefficient + p2[j].coefficient, p1[i].exponent});
++i;
++j;
}
}
// 将 p1 和 p2 剩余的项加入结果
while (i < p1.size()) result.push_back(p1[i++]);
while (j < p2.size()) result.push_back(p2[j++]);
return result;
}
int main() {
Polynomial p1{{3, 5}, {2, 3}, {1, 1}}; // 3x^5 + 2x^3 + x
Polynomial p2{{4, 5}, {3, 4}, {2, 2}, {1, 0}}; // 4x^5 + 3x^4 + 2x^2 + 1
Polynomial p3 = p1 + p2; // 计算 p1 + p2
cout << "p1 = ";
for (const auto& t : p1) {
cout << t.coefficient << "x^" << t.exponent << " + ";
}
cout << endl;
cout << "p2 = ";
for (const auto& t : p2) {
cout << t.coefficient << "x^" << t.exponent << " + ";
}
cout << endl;
cout << "p1 + p2 = ";
for (const auto& t : p3) {
cout << t.coefficient << "x^" << t.exponent << " + ";
}
cout << endl;
return 0;
}
输出结果
p1 = 3x^5 + 2x^3 + x^1 +
p2 = 4x^5 + 3x^4 + 2x^2 + x^0 +
p1 + p2 = 7x^5 + 3x^4 + 2x^3 + 2x^2 + x^1 +
有了之前加法和乘法的思路,乘法就不用我说了。
遍历A链的所有结点,遍历B链的所有结点,也就是双重循环,AXB的所有结点添加(insert
)到新链中。
因为我们规定的 insert
就是有序,不重复幂值。
所以直接丢进去就行,不用考虑。
void mul(LIST A, LIST B)
{
LIST head = (LIST)malloc(sizeof(struct node));
head->NEXT = NULL;
LIST i = A->NEXT;
//if A NULL
LIST j = B->NEXT;
if(!i)
{
while(j)
{
insert(j->c, j->n, head);
j = j->NEXT;
}
uptate(head);
show(head);
return;
}
//if B NULL
if(!j)
{
while(i)
{
insert(i->c, i->n, head);
i = i->NEXT;
}
uptate(head);
show(head);
return;
}
while(i){
j = B->NEXT;
while(j)
{
insert(i->c * j->c, i->n + j->n, head);
j = j->NEXT;
}
i = i->NEXT;
}
uptate(head);
show(head);
}