C++链表实现多项式的加减乘除

大作业之C++实现链式存储结构实现一元多项式的加减乘除

首先定义链表的每个节点

struct polynode
{int coef;int exp;polynode* link;
};
typedef polynode* polypointer;

每个节点储存这一项的系数、指数以及下一项的指针。

将一个新节点链接到已有表的最后：

void Attach(int c, int e, polypointer& d)
{polypointer x;x = new polynode;x->coef = c;x->exp = e;d->link = x;x->link = NULL;d = d->link;
}

输入的函数：

void Input(polypointer& L)
{int c, e;cout << "输入系数:" << endl;cin >> c;polypointer p = new polynode;p = L;while (c){cout << "输入指数:" << endl;cin >> e;Attach(c, e, p);cout << "请输入下一项的系数，若输入完毕，按0回车:";cin >> c;}
}

加减法过于简单，这里以加法为例做演示

polypointer PolyAdd(polypointer L1, polypointer L2)
{polypointer p, q, d, c;int x;p = L1->link;q = L2->link;c = new polynode;d = c;while ((p != NULL) && (q != NULL)){if (p->exp == q->exp){x = p->coef + q->coef;if (x != 0)Attach(x, p->exp, d);p = p->link;q = q->link;}else if (p->exp > q->exp){Attach(p->coef, p->exp, d);p = p->link;}else if (p->exp < q->exp){Attach(q->coef, q->exp, d);q = q->link;}}while (p != NULL){Attach(p->coef, p->exp, d);p = p->link;}while (q != NULL){Attach(q->coef, q->exp, d);q = q->link;}return c;
}

结果返回相加结果的链表的指针。

乘法的算法：1、以暴力的方式先做拆括号运算，每一项是系数相乘指数相加，连到新表之后

2、以指数做冒泡排序，之后遍历检测后做合并同类项操作。

polypointer Sort(polypointer& L)
{int temp1, temp2;polypointer r = NULL;bool isChange = true;while (r != L->link->link && isChange){polypointer q = L->link;isChange = false; //标志当前这一轮中又没有发生元素交换，如果没有则表示数组已经有序for (; q->link && q->link != r; q = q->link)if (q->exp < q->link->exp) {temp1 = q->exp;q->exp = q->link->exp;q->link->exp = temp1;temp2 = q->coef;q->coef = q->link->coef;q->link->coef = temp2;isChange = true;}r = q;}return L;
}

void SameUnit(polypointer& L)
{polypointer r;r = L->link;while (r->link != NULL){if (r->exp == r->link->exp) {r->coef = r->link->coef + r->coef;Delete(r, L);}r = r->link;}
}

以上为排序和合并操作

polypointer PolyMultiply(polypointer L1, polypointer L2)
{polypointer p, q, c, d;int x, y;c = new polynode;c->link = NULL;d = c;for (p = L1->link;p != NULL;p = p->link) {for (q = L2->link;q != NULL;q = q->link) {x = p->coef * q->coef;y = p->exp + q->exp;Attach(x, y, d);}}Sort(c);SameUnit(c);return c;
}

除法的算法：（带余除法）

1、参考多项式大除法的方式，一位一位地算商式，并链接到商式链表最后

2、每操作一次：新的被除式=原被除式—（除式*这一位的商式）

3、迭代该除法操作，当被除式的最高次小于除式的最高次时产生余项。

void PolyDivide(polypointer& L3, polypointer& L4, polypointer& L1/*被除式*/, polypointer& L2/*除式*/)
{polypointer p, q;p = L1->link;q = L2->link;if (p->exp < q->exp) {Copy(L4, L1);}else {polypointer r, s, t;r = L1->link;s = L2->link;int c, e;c = r->coef / s->coef;e = r->exp - s->exp;t = L3;while (t->link != NULL)t = t->link;Attach(c, e, t);polypointer temp = new polynode;temp->link = NULL;polypointer a = temp;Attach(c, e, a);polypointer temp2 = PolyMultiply(L2, temp);L1 = PolyMinus(L1, temp2);PolyDivide(L3, L4, L1, L2);}
}

当然这样操作需要将系数为0的项先补全

void Insert0(polypointer p, polypointer& L)
{polypointer q;q = new polynode;q->coef = 0;q->exp = p->exp - 1;q->link = p->link;p->link = q;
}

void MakeFull(polypointer& L1)
{polypointer p;for (p = L1->link;p->link != NULL;p = p->link) {if (p->exp != p->link->exp + 1)Insert0(p, L1);}while (p->exp != 0){Attach(0, p->exp - 1, p);}}

主函数：

int main()
{polypointer L1, L2;L1 = new polynode;L1->link = NULL;L2 = new polynode;L2->link = NULL;cout << "输入L1" << endl;Input(L1);cout << "输入L2" << endl;Input(L2);cout << "L1: ";Print(L1);cout << endl;cout << "L2: ";Print(L2);cout << endl;char ch;cout << "请输入要进行的运算（ + or - or * or / ）：";cin >> ch;switch (ch){case '+': {polypointer L0 = new polynode;L0 = PolyAdd(L1, L2);cout << "L1 + L2 = ";Print(L0);break;}case '-': {polypointer L9 = new polynode;L9 = PolyMinus(L1, L2);cout << "L1 - L2 = ";Print(L9);break;}case '*': {polypointer L8 = new polynode;L8 = PolyMultiply(L1, L2);cout << "L1 * L2 = ";Print(L8);break;}case '/': {MakeFull(L1);MakeFull(L2);polypointer L3, L4;L3 = new polynode;L3->link = NULL;L4 = new polynode;L4->link = NULL;PolyDivide(L3, L4, L1, L2);cout << "L1 / L2: "<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！