概要

设有一元多项式A_n(x)和B_m(X)，编程实现多项式A_m(x)和B_n(X)的加法、减法和乘法运算。其中多项式描述为：
A_n(x)=A₀+A₁x¹+A₂x²+A₃x³+….+A_mxⁿ
B_m(x)=B₀+B₁x¹+B₂x²+B₃x³+….+B_mx^m

数据结构的定义

LNode为每个节点的数据类型，表示多项式每一项的系数-指数

node为单链表链表，ELemType为已声明的LNode

typedef struct LNode {
    int coe;  // 系数
    int exp;  // 指数
} ElemType;

typedef struct node {
    ElemType data; // 数据
    node* next;    // 下一节点
} LinkNode, *LinkList;

LinkList——链表的实现

该部分用以定义链表结构以及声明链表的函数原型

LinkList.h

#ifndef LINKLIST_H_INCLUDED
#define LINKLIST_H_INCLUDED

typedef int Status;
#define OK 1
#define ERROR 0

typedef struct LNode {
    int coe;  // 系数
    int exp;  // 指数
    // 构造函数，初始化节点，赋值
    LNode() : coe(0), exp(0) {}
    LNode(int coe, int exp) : coe(coe), exp(exp) {}
    // 重载 == 用以比较，系数和指数均相同时判定相等
    bool operator==(const LNode& A) const {
        if (coe != A.coe)
            return false;
        if (exp != A.exp)
            return false;
        return true;
    }
} ElemType;

typedef struct node {
    ElemType data;
    node* next;
} LinkNode, *LinkList;

Status creat_LinkList(LinkList& L);                   // 创建链表
void clear_LinkList(LinkList& L);                     // 清空链表
Status push_back(LinkList L, const ElemType x);       // 在链表尾部插入元素
Status push_ascending(LinkList L, const ElemType x);  // 插入链表，使链表保持升序
Status delete_node(LinkList L, ElemType x);  // 删除链表中第一个与x相同的元素
void print_LinkList(LinkList L);             // 输出链表
void print_LinkList_ascending(LinkList L /*, bool op*/);   // 升幂输出链表
void print_LinkList_descending(LinkList L /*, bool op*/);  // 降幂输出链表
void print_Lnode(const ElemType x, const bool op);         // 输出当前节点元素
void copy(LinkList& C, LinkList L);                        // 复制L到C

#endif  // LINKLIST_H_INCLUDED

LinkList.cpp

实现了链表的基本操作

tip：在某些情况下，递归输出链表的格式会出现非预期效果（已解决）

例如：（升幂）当链表头元素的系数为0时（0 1 3 2 -2 1）
会输出： + 3x^2 - 2x 预期 3x^2 - 2x
例如：（降幂）当链表内只含有一个有效元素时（3 2）
会输出： + 3x^2 预期 3x^2

解决方案1：仍使用递归输出
升幂时，删除链表中所有系数为0的元素；降幂时，直接输出链表唯一元素
解决方案2：不使用递归输出
采用适当的容器，将链表中有效元素添加到容器中，控制格式输出

#include "main.h"

// 创建链表
Status creat_LinkList(LinkList& L) {
    L = (LinkList)malloc(sizeof(LNode));
    if (!L)
        return ERROR;
    L->next = NULL;
    return OK;
}

// 清空链表
void clear_LinkList(LinkList& L) {
    if (L->next) {
        clear_LinkList(L->next);
        free(L->next);
        L->next = NULL;
    }
}

// 在链表尾部插入元素
Status push_back(LinkList L, const ElemType x) {
    LinkList D;
    while (L->next)
        L = L->next;
    D = (LinkList)malloc(sizeof(LNode));
    if (!D)
        return ERROR;
    D->data = x;
    D->next = NULL;
    L->next = D;
    return OK;
}

// 插入链表，使链表保持升序
Status push_ascending(LinkList L, const ElemType x) {
    while (L->next && x.exp >= L->next->data.exp) {
        // 如果已经含有相同指数，则系数相加
        if (L->next->data.exp == x.exp) {
            L->next->data.coe += x.coe;
            return OK;
        }
        L = L->next;
    }
    // 新指数节点，插入到L的合适位置
    LinkList D = (LinkList)malloc(sizeof(LNode));
    D->data = x;
    D->next = L->next;
    L->next = D;
    return OK;
}

// 删除链表中第一个与x相同的元素
Status delete_node(LinkList L, ElemType x) {
    while (L->next) {
        if (L->next->data == x) {
            // 如果是链表最后一个元素
            if (L->next->next == NULL) {
                free(L->next->next);
                L->next = NULL;
            } else {
                LinkList tmp = L->next->next;
                free(L->next);
                L->next = tmp;
            }
            return OK;
        } else {
            L = L->next;
        }
    }
    return ERROR;
}

/*
 * FOR: print_*
 * op : true   多项式第一项
 * op : false  非多项式第一项
 */

// 输出链表
void print_LinkList(LinkList L) {
    __GREEN__
    cout << "以升幂输出多项式" << endl;
    __WHITE__
    print_LinkList_ascending(L /*, true*/);
    cout << endl;
    __GREEN__
    cout << "以降幂输出多项式" << endl;
    __WHITE__
    print_LinkList_descending(L /*, false*/);
    cout << endl;
}

// 升幂输出链表
void print_LinkList_ascending(LinkList L /*, bool op*/) {
    queue<ElemType> Q;
    while (L->next) {
        if (L->next->data.coe != 0)
            Q.push(L->next->data);
        L = L->next;
    }
    bool op = true;
    while (!Q.empty()) {
        print_Lnode(Q.front(), op);
        op = false;
        Q.pop();
    }
    // if (L) {
    //     print_Lnode(L->data, op);
    //     print_LinkList_ascending(L->next, false);
    // }
}

// 降幂输出链表
void print_LinkList_descending(LinkList L /*, bool op*/) {
    stack<ElemType> S;
    while (L->next) {
        if (L->next->data.coe != 0)
            S.push(L->next->data);
        L = L->next;
    }
    bool op = true;
    while (!S.empty()) {
        print_Lnode(S.top(), op);
        op = false;
        S.pop();
    }
    // if (L) {
    //     if (L->next && L->next->next == NULL)
    //         print_LinkList_descending(L->next, true);
    //     else
    //         print_LinkList_descending(L->next, false);
    //     print_Lnode(L->data, op);
    // }
}

/*
 * 用以格式化输出
 * 例如，将会以如下格式输出多项式：
 * "-3^2 + 4^3 - 5^4"
 * "3^2 + 4^3 - 5^4"
 */

// 输出当前节点元素
void print_Lnode(const ElemType x, const bool op) {
    if (op) {
        if (x.coe < 0)
            cout << "-";
    } else {
        if (x.coe < 0)
            cout << " - ";
        else
            cout << " + ";
    }
    // 控制输出格式
    int COE = abs(x.coe);
    if (x.exp == 0) {
        cout << COE;
    } else if (x.exp == 1) {
        if (COE != 1)
            cout << COE;
        cout << "x";
    } else {
        if (COE != 1)
            cout << COE;
        cout << "x^";
        if (x.exp < 0)
            cout << "(" << x.exp << ")";
        else
            cout << x.exp;
    }
}

// 复制L到C
void copy(LinkList& C, LinkList L) {
    while (L->next) {
        push_ascending(C, L->data);
        L = L->next;
    }
}

calculate——计算多项式

该部分用以声明计算的函数原型

calculate.h

#ifndef CALCULATE_H_INCLUDED
#define CALCULATE_H_INCLUDED

void AddList(LinkList A, LinkList B, LinkList& L);  // 多项式相加
void SubList(LinkList A, LinkList B, LinkList& L);  // 多项式相减
void MulList(LinkList A, LinkList B, LinkList& L);  // 多项式相乘

#endif  // CALCULATE_H_INCLUDED

calculate.cpp

加/减：定义两个指针分别指向A，B，不断遍历两指针，分情况将得到的元素插入到L中

乘：定义两个指针la、lb，对于每个la，遍历每个lb，进行乘法运算

#include "main.h"

void AddList(LinkList A, LinkList B, LinkList& L) {  // 多项式相加
    LinkList la = A->next, lb = B->next;
    while (la && lb) {
        // 如果指数相同
        if (la->data.exp == lb->data.exp) {
            int COE = la->data.coe + lb->data.coe;
            int EXP = la->data.exp;
            push_ascending(L, ElemType(COE, EXP));
            la = la->next;
            lb = lb->next;
        }
        // 将小的元素添加到L中
        else if (la->data.exp < lb->data.exp) {
            push_ascending(L, la->data);
            la = la->next;
        } else {
            push_ascending(L, lb->data);
            lb = lb->next;
        }
    }
    // 将A、B中剩余元素添加到L中
    // 可以直接令L尾指针指向la或lb
    while (la) {
        push_ascending(L, la->data);
        la = la->next;
    }
    while (lb) {
        push_ascending(L, lb->data);
        lb = lb->next;
    }
}

void SubList(LinkList A, LinkList B, LinkList& L) {  // 多项式相减
    LinkList la = A->next, lb = B->next;
    while (la && lb) {
        // 如果指数相同
        if (la->data.exp == lb->data.exp) {
            int COE = la->data.coe - lb->data.coe;
            int EXP = la->data.exp;
            push_ascending(L, ElemType(COE, EXP));
            la = la->next;
            lb = lb->next;
        }
        // 将小的元素添加到L中
        else if (la->data.exp < lb->data.exp) {
            push_ascending(L, la->data);
            la = la->next;
        } else {
            // 相减，系数取负
            push_ascending(L, ElemType(-lb->data.coe, lb->data.exp));
            lb = lb->next;
        }
    }
    // 将A、B中剩余元素添加到L中
    while (la) {
        push_ascending(L, la->data);
        la = la->next;
    }
    while (lb) {
        // 相减，系数取负
        push_ascending(L, ElemType(-lb->data.coe, lb->data.exp));
        lb = lb->next;
    }
}

void MulList(LinkList A, LinkList B, LinkList& L) {  // 多项式相乘
    LinkList la = A->next;
    while (la) {
        LinkList lb = B->next;
        while (lb) {
            // 系数相乘，指数相加
            int COE = la->data.coe * lb->data.coe;
            int EXP = la->data.exp + lb->data.exp;
            push_ascending(L, ElemType(COE, EXP));
            lb = lb->next;
        }
        la = la->next;
    }
}

solve——主体框架

solve.h

#ifndef SOLVE_H_INCLUDED
#define SOLVE_H_INCLUDED

#define TOL 2  // 多项式的总数

void solve();
void tip_polynomial(const int num, LinkList& L);    // 提示输入多项式
void tip_outPolynomial(const int num, LinkList L);  // 提示输出输入的多项式
void tip_operator(char& op);                        // 提示输入运算符
void tip_outOperator(const char op);                // 输出输入的运算符
void cal_polynomial(LinkList A, LinkList B, LinkList& L, const char op);  // 计算多项式
void tip_answer();  // 提示输出结果

#endif  // SOLVE_H_INCLUDED

solve.cpp

实现简单的交互界面

#include "main.h"

/*
 * 能够实现n个多项式计算
 * 更改solve.h中的TOL即可
 */

void solve() {
    LinkList L[TOL + 1];
    // 输入多项式
    for (int i = 1; i <= TOL; i++) {
        creat_LinkList(L[i]);
        tip_polynomial(i, L[i]);
    }
    // 输出输入数据
    for (int i = 1; i <= TOL; i++) {
        tip_outPolynomial(i, L[i]);
        cout << endl;
    }
    // 输入操作符
    char oper;
    tip_operator(oper);
    tip_outOperator(oper);
    // 创建RES链表，记录运算答案
    LinkList CAS, RES;
    creat_LinkList(CAS);
    creat_LinkList(RES);
    // 计算结果
    for (int i = 1; i < TOL; i++) {
        if (i == 1)
            cal_polynomial(L[i], L[i + 1], RES, oper);
        else {
            // 将中间结果复制到CAS中，用于下一次计算
            copy(CAS, RES);
            cal_polynomial(CAS, L[i + 1], RES, oper);
        }
    }
    // 输出结果多项式
    tip_answer();
    print_LinkList(RES);
}

// 提示输入多项式
void tip_polynomial(const int num, LinkList& L) {
    __GREEN__
    cout << "请输入第" << num << "个多项式" << endl;
    cout << "请先输入一个整数n，表示多项式的项数" << endl;
    __WHITE__
    int n;
    cin >> n;
    __GREEN__
    cout << "接着输出" << n << "个多项式(系数 指数)" << endl;
    __WHITE__
    for (int i = 0; i < n; i++) {
        ElemType x;
        cin >> x.coe >> x.exp;
        push_ascending(L, x);
    }
}

// 提示输出输入的多项式
void tip_outPolynomial(const int num, LinkList L) {
    cout << "输入的第" << num << "个多项式的降幂形式为：";
    print_LinkList_descending(L /*, false*/);
    cout << endl;
}

// 提示输入运算符
void tip_operator(char& oper) {
    __GREEN__
    cout << "请输入操作符(+ - *)" << endl;
    __WHITE__
    cin >> oper;
}

// 输出输入的运算符
void tip_outOperator(const char op) {
    cout << "输入的运算符为" << op << endl;
}

// 计算多项式
void cal_polynomial(LinkList A, LinkList B, LinkList& L, const char op) {
    clear_LinkList(L);
    switch (op) {
        case '+':
            AddList(A, B, L);
            break;
        case '-':
            SubList(A, B, L);
            break;
        case '*':
            MulList(A, B, L);
            break;
        default:
            __RED__
            cout << "操作符错误" << endl;
            __WHITE__
            break;
    }
}

// 提示输出结果
void tip_answer() {
    __GREEN__
    cout << "计算结果多项式为：" << endl;
    __WHITE__
}

main——主函数

包含其他所有使用到的头文件以及.h文件

main.h

#include <windows.h>

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <stack>

#include "LinkList.h"
#include "calculate.h"
#include "changeFontColor.h"
#include "solve.h"
using namespace std;

#define __DEFAULT__ fontColorToDefault();
#define __WHITE__ fontColorToWhite();
#define __RED__ fontColorToRed();
#define __GREEN__ fontColorToGreen();
#define __BLUE__ fontColorToBlue();
#define __YELLOW__ fontColorToYellow();
#define __PINK__ fontColorToPink();
#define __CYANBLUE__ fontColorToCyanBlue();

int main();

main.cpp

#include "main.h"

int main() {
    // freopen("D:\\CF\\in.txt", "r", stdin);
    solve();
    system("pause");
    return 0;
}

changeFontColor——更改字体颜色

changeFontColor.h

#ifndef CHANGEFONTCOLOR_H_INCLUDED
#define CHANGEFONTCOLOR_H_INCLUDED

void fontColorToDefault();
void fontColorToWhite();
void fontColorToRed();
void fontColorToGreen();
void fontColorToBlue();
void fontColorToYellow();
void fontColorToPink();
void fontColorToCyanBlue();

#endif  // CHANGEFONTCOLOR_H_INCLUDED

changeFontColor.cpp

#include "main.h"

void fontColorToDefault() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);
}

void fontColorToWtipe() {
    SetConsoleTextAttribute(
        GetStdHandle(STD_OUTPUT_HANDLE),
        FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE);
}

void fontColorToRed() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                            FOREGROUND_INTENSITY | FOREGROUND_RED);
}

void fontColorToGreen() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                            FOREGROUND_INTENSITY | FOREGROUND_GREEN);
}

void fontColorToBlue() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                            FOREGROUND_INTENSITY | FOREGROUND_BLUE);
}

void fontColorToYellow() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                            FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_GREEN);
}

void fontColorToPink() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                            FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_BLUE);
}

void fontColorToCyanBlue() {
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),
                            FOREGROUND_INTENSITY | FOREGROUND_GREEN | FOREGROUND_BLUE);
}

附：随机生成数据

生成用以上述程序的数据，通过修改TOL值可以改变生成多项式的个数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include <iostream>
using namespace std;

#define TOL 2  // 多项式的总数

int getRand(int n, int m) {
    return (rand() % (m - n + 1)) + n;
}

int main() {
    freopen("D:\\CF\\in.txt", "w", stdout);
    srand(time(0));
    int n[TOL + 1];
    for (int i = 1; i <= TOL; i++) {
        n[i] = getRand(1, 10);
        cout << n[i] << endl;
        for (int j = 0; j < n[i]; j++)
            if (j == 0)
                cout << getRand(-10, 10) << " " << getRand(-10, 10) << " ";
            else
                cout << getRand(-10, 10) << " " << getRand(-10, 10) << " ";
        cout << endl;
    }
    int op = getRand(0, 2);
    switch (op) {
        case 0:
            cout << "+" << endl;
            break;
        case 1:
            cout << "-" << endl;
            break;
        case 2:
            cout << "*" << endl;
            break;
        default:
            break;
    }
}