【算法】单链表一元多项式求和(C++)

5

@TOC

要求&&实现流程

在这里插入图片描述在这里插入图片描述在这里插入图片描述 在这里插入图片描述 在这里插入图片描述

代码实现

#include<iostream>
using namespace std;

typedef struct LinkNode
{
    int cofe;//系数
    int  exp;//次方
    struct LinkNode* next;
}LinkList,LinkNode;

//初始化链表
void initLinkList(LinkList*& L)
{   
    L = new LinkList;
    L->next = NULL;
}
//尾插
void LinkPushBack(LinkList* L, int _cofe, int _exp)
{
    LinkNode* node = new LinkNode;
    node->cofe = _cofe;
    node->exp = _exp;

    LinkNode* temp = L;
    while (temp->next)
    {
        temp = temp->next;
    }
    temp->next = node;
    node->next = NULL;
}

//输入数据
void inputPoly(LinkList* L1, LinkList* L2)
{
    //系数,次方
    int l1cofe = 0;
    int l2cofe = 0;
    int l1exp = 0;
    int l2exp = 0;

    //几项式
    int l1num = 0;
    int l2num = 0;

    cout << "第一个多项式有几项?" << endl;
    cin >> l1num;
    for (int i = 0; i < l1num; i++)
    {
        cout << "请输入第"<<i+1<<"项的系数:" << endl;
        cin >> l1cofe;
        cout << "请输入第" << i+1 << "项的次方:" << endl;
        cin >> l1exp;
        LinkPushBack(L1, l1cofe, l1exp);
    }
    cout << "第一个多项式输入完毕!" << endl;

    cout << "第二个多项式有几项?" << endl;
    cin >> l2num;
    for (int i = 0; i < l2num; i++)
    {
        cout << "请输入第" << i+1<< "项的系数:" << endl;
        cin >> l2cofe;
        cout << "请输入第" << i+1 << "项的次方:" << endl;
        cin >> l2exp;
        LinkPushBack(L2, l2cofe, l2exp);
    }
    cout << "第二个多项式输入完毕!" << endl;
    cout << "多项式输入完毕!" << endl;
}

//多项式求和运算
void sumList(LinkList* L1, LinkList* L2)
{
    LinkNode* p = L1->next;//p为结果链表
    LinkNode* q = L2->next;
    LinkNode* pFront = L1;
    LinkNode* qFront = L2;
    //cofe系数
    //exp次方

    while (q && p)
    {
        if (p->exp == q->exp)//是同类项,可以合并,结果合并到p中
        {
            p->cofe += q->cofe;
            LinkNode* temp = new LinkNode;
            //删除q的结点
            temp = q;
            qFront->next = temp->next;
            delete temp;

            //工作指针后移
            pFront = p;
            p = p->next;

            q = qFront->next;
        }
        else if(p->exp < q->exp)//结果链表对应次方比q链表对应结点次方小,结果链表中工作指针后移
        {
            pFront = p;
            p = p->next;
        }
        else if(p->exp > q->exp)//结果链表对应次方比q链表对应结点次方大,q对应结点插过来。
        {
            //将这个结点插入到结果结点中

            qFront->next = q->next;
            pFront->next = q;
            q->next = p;

            q = qFront->next;//重新回到对应链表
            //结果链表的前指针后移
            pFront = pFront->next;
        }
    }
    //如果多项式L2的长度大于L1的,此时结束时,L2还有没遍历到的结点,次方大于L1所有的结点,直接插入到结果链表(L1)尾部
    if (q)//加个判断条件防止,L1最后一个项,系数大于L2的,也进入下面这个循环
    {
        while (q)
        {
            pFront->next = q;
            pFront = pFront->next;
            q = q->next;
        }
        pFront->next = NULL;//链接完成后尾结点next域置空
    }
    L2->next = NULL;//到达这里,L2除了head结点之外,后面的就算有内容也不属于它了。

    cout << "相加结果为:" << endl;
    L1 = L1->next;
    while (L1)
    {
        cout << "(" << L1->cofe << "," << L1->exp << ")" << " ";
        L1 = L1->next;
    }   
}
//销毁链表
void destoryLink(LinkNode*& L)
{
    LinkNode* tempNode = L;
    while (tempNode)
    {
        L = L->next;
        delete tempNode;
        tempNode = L;
    }
}
int main(void)
{
    LinkList* L1;
    LinkList* L2;
    initLinkList(L1);
    initLinkList(L2);

    inputPoly(L1, L2);
    sumList(L1, L2) ;

    destoryLink(L1);
    destoryLink(L2);

    return 0;
}

输出结果在这里插入图片描述