链表实现多项式的相加相减以及修改指定指数系数

#include <iostream>
using namespace std;

// 定义多项式节点结构
typedef struct PolyNode {
    int coaf;  // 系数
    int expn;  // 指数
    struct PolyNode* next; // 指向下一个节点的指针
} PolyNode, *Poly;

// 创建多项式节点
Poly createNode(int coaf, int expn) {
    Poly newNode = new PolyNode();
    newNode->coaf = coaf;
    newNode->expn = expn;
    newNode->next = nullptr;
    return newNode;
}

// 插入节点到多项式中（按指数从小到大排序，并合并同类项）
void insertNode(Poly& head, int coaf, int expn) {
    if (coaf == 0) return; // 如果系数为 0，直接忽略

    Poly newNode = createNode(coaf, expn);
    if (!head) {
        head = newNode;
        return;
    }

    Poly temp = head;
    Poly prev = nullptr;

    // 查找插入位置
    while (temp && temp->expn < expn) {
        prev = temp;
        temp = temp->next;
    }

    // 如果指数相等，合并同类项
    if (temp && temp->expn == expn) {
        temp->coaf += coaf;
        if (temp->coaf == 0) { // 如果合并后系数为 0，删除该节点
            if (prev) {
                prev->next = temp->next;
            } else {
                head = temp->next;
            }
            delete temp;
        }
        delete newNode; // 释放新节点的内存
        return;
    }

    // 插入新节点
    if (!prev) {
        newNode->next = head;
        head = newNode;
    } else {
        newNode->next = prev->next;
        prev->next = newNode;
    }
}

// 打印多项式
void printPoly(Poly head) {
    if (!head) {
        cout << "0" << endl;
        return;
    }
    Poly temp = head;
    bool isFirstTerm = true; // 标记是否为第一项
    while (temp) {
        // 处理符号
        if (!isFirstTerm) {
            if (temp->coaf > 0) {
                cout << " + ";
            } else {
                cout << " - ";
            }
        } else {
            if (temp->coaf < 0) {
                cout << "-";
            }
            isFirstTerm = false;
        }
        // 处理系数和指数
        cout << abs(temp->coaf); // 打印系数的绝对值
        if (temp->expn != 0) {
            cout << "x^" << temp->expn;
        }
        temp = temp->next;
    }
    cout << endl;
}

// 多项式相加
Poly addPoly(Poly poly1, Poly poly2) {
    Poly result = nullptr;
    while (poly1 || poly2) {
        if (!poly1) {
            insertNode(result, poly2->coaf, poly2->expn);
            poly2 = poly2->next;
        } else if (!poly2) {
            insertNode(result, poly1->coaf, poly1->expn);
            poly1 = poly1->next;
        } else if (poly1->expn == poly2->expn) {
            insertNode(result, poly1->coaf + poly2->coaf, poly1->expn);
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->expn < poly2->expn) {
            insertNode(result, poly1->coaf, poly1->expn);
            poly1 = poly1->next;
        } else {
            insertNode(result, poly2->coaf, poly2->expn);
            poly2 = poly2->next;
        }
    }
    return result;
}

// 多项式相减
Poly subtractPoly(Poly poly1, Poly poly2) {
    Poly result = nullptr;
    while (poly1 || poly2) {
        if (!poly1) {
            insertNode(result, -poly2->coaf, poly2->expn);
            poly2 = poly2->next;
        } else if (!poly2) {
            insertNode(result, poly1->coaf, poly1->expn);
            poly1 = poly1->next;
        } else if (poly1->expn == poly2->expn) {
            insertNode(result, poly1->coaf - poly2->coaf, poly1->expn);
            poly1 = poly1->next;
            poly2 = poly2->next;
        } else if (poly1->expn < poly2->expn) {
            insertNode(result, poly1->coaf, poly1->expn);
            poly1 = poly1->next;
        } else {
            insertNode(result, -poly2->coaf, poly2->expn);
            poly2 = poly2->next;
        }
    }
    return result;
}

// 修改多项式的系数或指数
void modifyPoly(Poly& head, int oldExpn, int newCoaf, int newExpn) {
    Poly temp = head;
    Poly prev = nullptr;

    // 查找要修改的节点
    while (temp && temp->expn != oldExpn) {
        prev = temp;
        temp = temp->next;
    }

    if (!temp) {
        cout << "未找到指定指数的项！" << endl;
        return;
    }

    // 删除旧节点
    if (prev) {
        prev->next = temp->next;
    } else {
        head = temp->next;
    }
    delete temp;

    // 插入新节点
    insertNode(head, newCoaf, newExpn);
}

// 释放多项式内存
void freePoly(Poly& head) {
    Poly temp;
    while (head) {
        temp = head;
        head = head->next;
        delete temp;
    }
}

// 功能菜单
void menu() {
    cout << "========== 多项式操作菜单 ==========" << endl;
    cout << "1. 输入多项式" << endl;
    cout << "2. 打印多项式" << endl;
    cout << "3. 多项式相加" << endl;
    cout << "4. 多项式相减" << endl;
    cout << "5. 修改多项式的系数或指数" << endl;
    cout << "6. 退出" << endl;
    cout << "====================================" << endl;
}

int main() {
    Poly poly1 = nullptr;
    Poly poly2 = nullptr;
    int choice;

    while (true) {
        menu();
        cout << "请选择: ";
        cin >> choice;

        if (choice == 1) {
            int coaf, expn;
            cout << "输入多项式1的项数: ";
            int n;
            cin >> n;
            for (int i = 0; i < n; i++) {
                cout << "输入第 " << i + 1 << " 项的系数和指数: ";
                cin >> coaf >> expn;
                insertNode(poly1, coaf, expn);
            }
            cout << "输入多项式2的项数: ";
            cin >> n;
            for (int i = 0; i < n; i++) {
                cout << "输入第 " << i + 1 << " 项的系数和指数: ";
                cin >> coaf >> expn;
                insertNode(poly2, coaf, expn);
            }
        } else if (choice == 2) {
            cout << "多项式1: ";
            printPoly(poly1);
            cout << "多项式2: ";
            printPoly(poly2);
        } else if (choice == 3) {
            Poly result = addPoly(poly1, poly2);
            cout << "多项式1 + 多项式2 = ";
            printPoly(result);
            freePoly(result);
        } else if (choice == 4) {
            Poly result = subtractPoly(poly1, poly2);
            cout << "多项式1 - 多项式2 = ";
            printPoly(result);
            freePoly(result);
        } else if (choice == 5) {
            int polyChoice, oldExpn, newCoaf, newExpn;
            cout << "选择要修改的多项式 (1 或 2): ";
            cin >> polyChoice;
            if (polyChoice != 1 && polyChoice != 2) {
                cout << "无效选择！" << endl;
                continue;
            }
            cout << "输入要修改的项的指数: ";
            cin >> oldExpn;
            cout << "输入新的系数和指数: ";
            cin >> newCoaf >> newExpn;
            if (polyChoice == 1) {
                modifyPoly(poly1, oldExpn, newCoaf, newExpn);
            } else {
                modifyPoly(poly2, oldExpn, newCoaf, newExpn);
            }
        } else if (choice == 6) {
            break;
        } else {
            cout << "无效选择，请重试！" << endl;
        }
    }

    // 释放内存
    freePoly(poly1);
    freePoly(poly2);

    return 0;
}