数据结构一元多项式算法实现

一元多项式可以用链表来表示，每个节点包含该项的系数和指数。算法实现流程如下：

1. 定义一个节点结构体，包含系数和指数两个成员变量；
2. 定义一个链表结构体，包含头指针和链表长度两个成员变量；
3. 实现多项式的输入函数，根据输入的系数和指数插入到链表中；
4. 实现多项式的输出函数，从头到尾遍历链表输出每一项；
5. 实现多项式的加法函数，遍历两个多项式链表，按照指数大小合并相同项，最后合并未相同的项；
6. 实现多项式的乘法函数，遍历两个多项式链表，将每一项分别相乘并合并相同指数的项。

代码示例：

#include <iostream>
using namespace std;

struct Node {
    int coef;   // 系数
    int expn;   // 指数
    Node *next; // 指向下一个节点的指针
};

struct List {
    Node *head; // 头指针
    int len;    // 链表长度
};

// 初始化链表
void initList(List &L) {
    L.head = new Node;
    L.head->next = NULL;
    L.len = 0;
}

// 插入新节点
void insertNode(List &L, int coef, int expn) {
    Node *p = L.head;
    while (p->next && p->next->expn > expn) {
        p = p->next;
    }
    Node *q = new Node;
    q->coef = coef;
    q->expn = expn;
    q->next = p->next;
    p->next = q;
    L.len++;
}

// 输出链表
void printList(const List &L) {
    Node *p = L.head->next;
    while (p) {
        cout << p->coef << "x^" << p->expn;
        if (p->next) {
            cout << " + ";
        } else {
            cout << endl;
        }
        p = p->next;
    }
}

// 释放链表
void freeList(List &L) {
    Node *p, *q;
    p = L.head;
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    L.head = NULL;
    L.len = 0;
}

// 多项式加法
List addList(const List &A, const List &B) {
    List C;
    initList(C);
    Node *p = A.head->next, *q = B.head->next;
    while (p && q) {
        if (p->expn > q->expn) {
            insertNode(C, p->coef, p->expn);
            p = p->next;
        } else if (p->expn < q->expn) {
            insertNode(C, q->coef, q->expn);
            q = q->next;
        } else {
            int sum = p->coef + q->coef;
            if (sum != 0) {
                insertNode(C, sum, p->expn);
            }
            p = p->next;
            q = q->next;
        }
    }
    while (p) {
        insertNode(C, p->coef, p->expn);
        p = p->next;
    }
    while (q) {
        insertNode(C, q->coef, q->expn);
        q = q->next;
    }
    return C;
}

// 多项式乘法
List mulList(const List &A, const List &B) {
    List C;
    initList(C);
    for (Node *p = A.head->next; p; p = p->next) {
        for (Node *q = B.head->next; q; q = q->next) {
            int coef = p->coef * q->coef;
            int expn = p->expn + q->expn;
            insertNode(C, coef, expn);
        }
    }
    return C;
}

int main() {
    List A, B, C1, C2;
    initList(A);
    initList(B);
    insertNode(A, 3, 3);
    insertNode(A, 2, 2);
    insertNode(A, 1, 1);
    insertNode(A, 5, 0);
    insertNode(B, 4, 4);
    insertNode(B, 3, 3);
    insertNode(B, 1, 1);
    printList(A);
    printList(B);
    C1 = addList(A, B);
    printList(C1);
    C2 = mulList(A, B);
    printList(C2);
    freeList(A);
    freeList(B);
    freeList(C1);
    freeList(C2);
    return 0;
}