多项式乘法

曾经终败给现在 2021-09-11 02:10 345阅读 0赞

L1和L2是两个带头结点的单链表表示的多项式，编写算法计算两个多项式的乘积，运算结果仍用单链表进行存储

#include <iostream>
    
    using namespace std;
    
    typedef struct LNode { 
        int coefficient;    //系数
        int degree; //次数
        struct LNode *next; //下一个结点
    } LNode, *LinkedList;
    
    /** * 查找计算结果应该插入的位置 * @param L 链表的头结点指针 * @param degree 次数 * @return 插入结点的前一个结点 */
    LinkedList findPre(LinkedList L, int degree) { 
        LinkedList pre = L;
        LNode *p = L->next;
        while (p != nullptr) { 
            if (p->degree <= degree) { 
                break;
            }
            pre = p;
            p = p->next;
        }
        return pre;
    }
    
    
    /** * 两个多项式进行乘法运算（多项式的次数按递减排列） * @param L1 多项式一 * @param L2 多项式二 * @return 计算结果 */
    LinkedList calculate(LinkedList L1, LinkedList L2) { 
        // 结果的头结点
        LinkedList head = (LinkedList) malloc(sizeof(LNode));
        head->next = nullptr;
        LNode *p = L1->next;
        while (p != nullptr) { 
            LNode *q = L2->next;
            while (q != nullptr) { 
                // 暂存结点信息
                LinkedList temp = (LinkedList) malloc(sizeof(LNode));
                // 系数相乘
                temp->coefficient = p->coefficient * q->coefficient;
                // 次数
                temp->degree = p->degree + q->degree;
                temp->next = nullptr;
                // 将temp插入到结果链表中
                LinkedList insertNode = findPre(head, temp->degree);
                if (insertNode->next == nullptr) { 
                    insertNode->next = temp;
                } else if (insertNode->next->degree == temp->degree) { 
                    insertNode->next->coefficient += temp->coefficient;
                    free(temp);
                } else if (insertNode->next->degree < temp->degree) { 
                    temp->next = insertNode->next;
                    insertNode->next = temp;
                }
                q = q->next;
            }
            p = p->next;
        }
        return head;
    }
    
    void printLinkList(LinkedList L) { 
        LNode *p = L->next;
        while (p != nullptr) { 
            cout << p->coefficient << "x^" << p->degree << " ";
            p = p->next;
        }
        cout << endl;
    }
    
    
    int main() { 
        LinkedList L1 = (LinkedList) malloc(sizeof(LNode));
        LinkedList L2 = (LinkedList) malloc(sizeof(LNode));
        L1->next = nullptr;
        L2->next = nullptr;
        for (int i = 0; i < 3; i++) { 
            LinkedList temp1 = (LinkedList) malloc(sizeof(LNode));
            temp1->coefficient = (2 + i);
            temp1->degree = (1 + i);
            temp1->next = L1->next;
            L1->next = temp1;
            LinkedList temp2 = (LinkedList) malloc(sizeof(LNode));
            temp2->coefficient = (4 + i);
            temp2->degree = (i);
            temp2->next = L2->next;
            L2->next = temp2;
        }
        printLinkList(L1);
        printLinkList(L2);
        LinkedList result = calculate(L1, L2);
        printLinkList(result);
    
        return 0;
    }

![在这里插入图片描述][20191021213847876.png]

[20191021213847876.png]: /images/20210911/6dd20b314403497eb300875670fc1e0f.png