数据结构:用链表实现两个多项式相加,用C++或者C语言实现多项式相加,求完整代码输入:第一行输入包含两个整数m,n后续为m行和n行数据m,n分别代表两个多项式的项数后续每一行代表多项式
来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/23 22:18:45
数据结构:用链表实现两个多项式相加,用C++或者C语言实现多项式相加,求完整代码输入:第一行输入包含两个整数m,n后续为m行和n行数据m,n分别代表两个多项式的项数后续每一行代表多项式
数据结构:用链表实现两个多项式相加,用C++或者C语言实现多项式相加,求完整代码
输入:
第一行输入包含两个整数m,n
后续为m行和n行数据
m,n分别代表两个多项式的项数
后续每一行代表多项式的项,包含a,b两个数据,表示该项的系数和指数.
输出:
从较高指数到较低指数,依次输出求得的和.
每行一项,格式与输入相同,但无需输出项数,系数为0的项也不输出.
输入样例:
2 3
1 2
1 1
2 2
1 1
2 0
输出样例:
3 2
2 1
2 0
在线等·········求,急
数据结构:用链表实现两个多项式相加,用C++或者C语言实现多项式相加,求完整代码输入:第一行输入包含两个整数m,n后续为m行和n行数据m,n分别代表两个多项式的项数后续每一行代表多项式
#include <iostream>
#include <cmath>
using namespace std;
#define EPS 1E-6
typedef struct item {
\x09double coefficient;
\x09int power;
\x09struct item *next;
} *POLYNOMIAL,*pItem;
POLYNOMIAL Create() { // 创建多项式
\x09pItem head,p;
\x09double coe;
\x09int pwr,iterms,i;
\x09head = p = new item;
\x09cin >> iterms; // 读入多项式的项数
\x09for(i = 0; i < iterms; ++i) {
\x09\x09cin >> coe >> pwr;
\x09\x09p->next = new item;
\x09\x09p->next->coefficient = coe;
\x09\x09p->next->power = pwr;
\x09\x09p = p->next;
\x09}
\x09p->next = NULL;
\x09return head;
}
void Sort(POLYNOMIAL head) { // 按幂次降排序
\x09pItem pt,q,p = head;
\x09while(p->next) {
\x09\x09q = p->next;
\x09\x09while(q->next) {
\x09\x09\x09if(p->next->power < q->next->power) {
\x09\x09\x09\x09pt = p->next;
\x09\x09\x09\x09p->next = q->next;
\x09\x09\x09\x09q->next = p->next->next;
\x09\x09\x09\x09p->next->next = pt;
\x09\x09\x09}
\x09\x09\x09else q = q->next;
\x09\x09}
\x09\x09p = p->next;
\x09}
}
void Show(POLYNOMIAL head) { // 显示
\x09POLYNOMIAL p = head->next;
\x09int flag = 1;
\x09if(p == NULL) return;
\x09while(p) {
\x09\x09if(flag) {
\x09\x09\x09if(fabs(p->coefficient) >= EPS) {
\x09\x09\x09\x09if(p->power == 0) cout << p->coefficient;
\x09\x09\x09\x09else if(p->power == 1) {
\x09\x09\x09\x09\x09if(p->coefficient == 1.0) cout << "x ";
\x09\x09\x09\x09\x09else if(p->coefficient == -1.0) cout << "-x ";
\x09\x09\x09\x09\x09else cout << p->coefficient << "x ";
\x09\x09\x09\x09}
\x09\x09\x09\x09else if(p->coefficient == 1.0) cout << "x^" << p->power << " ";
\x09\x09\x09\x09else if(p->coefficient == -1.0) cout << "-x^" << p->power << " ";
\x09\x09\x09\x09else cout << p->coefficient << "x^" << p->power << " ";
\x09\x09\x09\x09flag = 0;
\x09\x09\x09}
\x09\x09}
\x09\x09else if(p->coefficient > 0.0 && fabs(p->coefficient) >= EPS) {
\x09\x09\x09if(p->power == 0) cout << "+ " << p->coefficient << " ";
\x09\x09\x09else if(p->power == 1) {
\x09\x09\x09\x09if(p->coefficient == 1.0) cout << "+ x ";
\x09\x09\x09\x09else cout << "+ " << p->coefficient << "x ";
\x09\x09\x09}
\x09\x09\x09else if(p->coefficient == 1.0) cout << "+ x^" << p->power << " ";
\x09\x09\x09else cout << "+ " << p->coefficient << "x^" << p->power << " ";
\x09\x09}
\x09\x09else if(p->coefficient < 0.0 && fabs(p->coefficient) >= EPS) {
\x09\x09\x09if(p->power == 0) cout << "- " << -p->coefficient << " ";
\x09\x09\x09else if(p->power == 1) {
\x09\x09\x09\x09if(p->coefficient == -1.0) cout << "- x ";
\x09\x09\x09\x09else cout << "- " << -p->coefficient << "x ";
\x09\x09\x09}
\x09\x09\x09else if(p->coefficient == -1.0) cout << "- " << "x^" << p->power << " ";
\x09\x09\x09else cout << "- " << -p->coefficient << "x^" << p->power << " ";
\x09\x09}
\x09\x09p = p->next;
\x09}
\x09cout << endl;
}
double Power(double x,int n) {
\x09double value = 1.0;
\x09int i;
\x09for(i = 0; i < n; ++i) value *= x;
\x09return value;
}
double Value(POLYNOMIAL head,double x) { // 多项式求值
\x09POLYNOMIAL p;
\x09double value = 0.0;
\x09for(p = head->next; p; p = p->next)
\x09\x09value += p->coefficient * Power(x,p->power);
\x09return value;
}
POLYNOMIAL Copy(POLYNOMIAL A) {
\x09POLYNOMIAL head,t,p;
\x09head = t = new item;
\x09for(p = A->next; p; p = p->next) {
\x09\x09t->next = new item;
\x09\x09t->next->coefficient = p->coefficient;
\x09\x09t->next->power = p->power;
\x09\x09t = t->next;
\x09}
\x09t->next = NULL;
\x09return head;
}
POLYNOMIAL Additive(POLYNOMIAL A, POLYNOMIAL B) { // 多项式加
\x09POLYNOMIAL head,p,q,t;
\x09head = Copy(A);
\x09for(p = B; p->next; p = p->next) {
\x09\x09q = head;
\x09\x09while(q->next) {
\x09\x09\x09if(p->next->power == q->next->power) {
\x09\x09\x09\x09q->next->coefficient += p->next->coefficient;
\x09\x09\x09\x09if(fabs(q->next->coefficient) <= EPS) {
\x09\x09\x09\x09\x09t = q->next;
\x09\x09\x09\x09\x09q->next = t->next;
\x09\x09\x09\x09\x09free(t);
\x09\x09\x09\x09}
\x09\x09\x09\x09break;
\x09\x09\x09}
\x09\x09\x09q = q->next;
\x09\x09}
\x09\x09if(q->next == NULL) {
\x09\x09\x09q->next = new item;
\x09\x09\x09q->next->coefficient = p->next->coefficient;
\x09\x09\x09q->next->power = p->next->power;
\x09\x09\x09q->next->next = NULL;
\x09\x09}
\x09}
\x09Sort(head);
\x09return head;
}
POLYNOMIAL Subtract(POLYNOMIAL A, POLYNOMIAL B) { // 多项式减
\x09POLYNOMIAL head,p,q,t;
\x09head = Copy(A);
\x09for(p = B; p->next; p = p->next) {
\x09\x09q = head;
\x09\x09while(q->next) {
\x09\x09\x09if(p->next->power == q->next->power) {
\x09\x09\x09\x09q->next->coefficient -= p->next->coefficient;
\x09\x09\x09\x09if(fabs(q->next->coefficient) <= EPS) {
\x09\x09\x09\x09\x09t = q->next;
\x09\x09\x09\x09\x09q->next = t->next;
\x09\x09\x09\x09\x09free(t);
\x09\x09\x09\x09}
\x09\x09\x09\x09break;
\x09\x09\x09}
\x09\x09\x09q = q->next;
\x09\x09}
\x09\x09if(q->next == NULL) {
\x09\x09\x09q->next = new item;
\x09\x09\x09q->next->coefficient = -p->next->coefficient;
\x09\x09\x09q->next->power = p->next->power;
\x09\x09\x09q->next->next = NULL;
\x09\x09}
\x09}
\x09Sort(head);
\x09return head;
}
POLYNOMIAL Multiplication(POLYNOMIAL A, POLYNOMIAL B) { // 多项式乘
\x09POLYNOMIAL head,t,p,q;
\x09head = t = new item;
\x09for(p = A->next; p; p = p->next) { // 完成相乘过程
\x09\x09for(q = B->next; q; q = q->next) {
\x09\x09\x09t->next = new item;
\x09\x09\x09t->next->coefficient = p->coefficient * q->coefficient;
\x09\x09\x09t->next->power = p->power + q->power;
\x09\x09\x09t = t->next;
\x09\x09}
\x09}
\x09t->next = NULL;
\x09Sort(head); // 排序
\x09p = head;
\x09while(p->next) { // 合并同类项
\x09\x09q = p->next;
\x09\x09while(q->next) {
\x09\x09\x09if(p->next->power == q->next->power) {
\x09\x09\x09\x09p->next->coefficient += q->next->coefficient;
\x09\x09\x09\x09t = q->next;
\x09\x09\x09\x09q->next = t->next;
\x09\x09\x09\x09free(t);
\x09\x09\x09}
\x09\x09\x09else q = q->next;
\x09\x09}
\x09\x09p = p->next;
\x09}
\x09return head;
}
void FreeMemory(POLYNOMIAL head) {
\x09POLYNOMIAL q,p = head;
\x09while(p) {
\x09\x09q = p;
\x09\x09p = q->next;
\x09\x09delete q;
\x09}
}
int main() {
\x09char ops[3];
\x09POLYNOMIAL A,B,C = NULL,D = NULL,E = NULL;
\x09cout << "创建多项式A:\n";
\x09A = Create();
\x09Sort(A);
\x09cout << "A(x) = ";Show(A);
\x09cout << "创建多项式B:\n";
\x09B = Create();
\x09Sort(B);
\x09cout << "B(x) = ";Show(B);
\x09cout << "运算符 : ";
\x09fflush(stdin);
\x09gets(ops);
\x09for(int i = 0; ops[i]; ++i) {
\x09\x09switch(ops[i]) {
\x09\x09\x09case '+' : C = Additive(A,B);
\x09\x09\x09\x09cout << "C(x) = ";
\x09\x09\x09\x09Show(C);
\x09\x09\x09\x09break;
\x09\x09\x09case '-' : D = Subtract(A,B);
\x09\x09\x09\x09cout << "D(x) = ";
\x09\x09\x09\x09Show(D);
\x09\x09\x09\x09break;
\x09\x09\x09case '*' : E = Multiplication(A,B);
\x09\x09\x09\x09cout << "E(x) = ";
\x09\x09\x09\x09Show(E);
\x09\x09\x09\x09break;
\x09\x09\x09default : cout << "不能识别运算符 : " << ops[i] << endl;
\x09\x09\x09}
\x09}
\x09cout << "A(2) = " << Value(A,2.0) << endl;
\x09cout << "B(2) = " << Value(B,2.0) << endl;
\x09if(C) cout << "C(2) = " << Value(C,2.0) << endl;
\x09if(D) cout << "D(2) = " << Value(D,2.0) << endl;
\x09if(E) cout << "E(2) = " << Value(E,2.0) << endl;
\x09FreeMemory(A);
\x09FreeMemory(B);
\x09FreeMemory(C);
\x09FreeMemory(D);
\x09FreeMemory(E);
\x09return 0;
}