单链表实现两个多项式相加

两个多项式合并

多项式 L1 与 L2
处理方法：将较短 L2 ，合并到长的 L1

通过逐项比较，依次添加

L1 连续三项指数 ： X ,Y , Z
L1 某项指数 ：N
L2 某项指数 ：M

1. 当 M == N 相同，则两项系数相加，然后 L1 与 L2 都跳到下一项

注意：存在系数为0 的情况，位于中间项的可以直接扼杀在摇篮，不占内存空间，位于结尾的则需要单独处理

2. 当 X < M < Y ，则需要把 M项 插入到 X,Y 两项 之间

3. 开头和结尾需要单独处理，也存在三种可能，指数相同，指数位于两项之间，指数在开头结尾

多项式排序

方法：

1. 从左到右剔除第一个顺序有问题的项，并保存
2. 将此项插入到合适的位置
3. 依次执行，直到没有顺序错误的项

#include "pch.h"
#include <iostream>
using namespace std;
/*
1 ： 最后显示时的符号问题 ，此方法：void FindPolyn(ListNode L);
2 ： 系数为0，解决方法：void AddPolyn(ListNode &L1, ListNode L2);
3 ： 两个多项式相加时，在第一个多项式结尾出现系数为0，这个零无法直接在产生时去除，解决方法：void DelZeroPolyn(ListNode &L);
4 ： 多项式排序
5 ： 两个多项式合并，释放剩余的多项式的内存空间
*/

#define LIST_SIZE sizeof(LNode)

typedef struct Polynomial
{
    float coef;
    int expn;
    struct Polynomial *next;
}LNode,*ListNode;

ListNode CreatePolyn();                             // 创建一个多项式
void FindPolyn      (ListNode L);                   // 查看多项式
int  LengthPolyn    (ListNode L);                   // 判断多项式的长度
bool IsNULL         (ListNode L);                   // 判断是否为空

bool AddOnePolyn    (ListNode &L1, ListNode &L2);   // 处理 多项式 与 只有一项的多项式
bool AddPolyn       (ListNode &L1, ListNode &L2);   // 合并多项式
void DelZeroPolyn   (ListNode &L);                  // 处理系数为零的情况

bool UnOrderPro     (ListNode& L, LNode * &e);      // 删除按顺序第一个错误位置的元素
bool SortPolyn(ListNode &L);                        // 插入删除错误位置的元素
void ListLink       (ListNode &L, int length);      // 多项式排序

void UnRepetition(ListNode &L);                     // 多项式去重，前提条件，必须是有序多项式
void polynomial()
{
    ListNode L1 =  CreatePolyn();                   // 创建多项式
    cout << "_________________________"  << endl;
    ListNode L2 = CreatePolyn();                    // 创建多项式

    ListLink(L1, LengthPolyn(L1));                  // 多项式排序
    ListLink(L2, LengthPolyn(L2));                  // 多项式排序

    UnRepetition(L1);                               // 多项式去重
    UnRepetition(L2);                               // 多项式去重

    int n1 = LengthPolyn(L1);                       // 获取多项式长度
    int n2 = LengthPolyn(L2);                       // 获取多项式长度

    cout << "L1 = ";
    FindPolyn(L1);                                  // 查看多项式
    cout << "_________________________" << endl;
    cout << "L2 = ";
    FindPolyn(L2);                                  // 查看多项式
    cout << "_________________________" << endl;


    if (AddPolyn(L1, L2))                           // 合并多项式
    {
        DelZeroPolyn(L1);                           // 多项式去零
        cout
            << "L=";
        FindPolyn(L1);                              // 查看多项式
    }
    cout << "_________________________长度：" << endl;

    cout
        << n1 << "+" << n2 << "="
        << LengthPolyn(L1)                          // 获取多项式长度
        << endl;
    cout << "_________________________" << endl;

    ListLink(L1, LengthPolyn(L1));                  // 多项式排序
    cout
        << "L=";
    FindPolyn(L1);                                  // 查看多项式

}

// 创建一个多项式
ListNode CreatePolyn()
{
    LNode * L = (ListNode)malloc(LIST_SIZE);
    if (!L) exit(1);
    L->next = NULL;

    LNode * p = (ListNode)malloc(LIST_SIZE),*q;
    if (!p) exit(1);
    int num = 1;
    cout << "第 " << num << " 项" << endl;
    cout << "输入系数：";
    cin >> p->coef;
    cout << "输入指数：";
    cin >> p->expn;
    q = L;
    while ( 1)
    {
        if (p->coef == 0)
        {
            q->next = NULL;
            break;
        }
        else
        {
            q->next = p;
            q = p;
            num++;
        }
        p = (ListNode)malloc(LIST_SIZE);
        if (!p) exit(1);
        cout << "第 " << num << " 项" << endl;
        cout << "输入系数：";
        cin >> p->coef;
        cout << "输入指数：";
        cin >> p->expn;
    }
    free(p);
    return L;
}

// 查看多项式
void FindPolyn(ListNode L)
{
    if (!L->next)
    {
        cout << 0 << endl;
        return;
    }
    ListNode p = L->next;
    while (p != NULL)
    {
        if (p->coef == 1)
        {
            // 系数为1，省略不写
            if (p->expn == 0)
            {
                // 系数为1，同时指数为0，则需要显示 1
                cout << p->coef;
            }
        }
        else
        {
            cout << p->coef;
        }

        if (p->expn != 0)
        {// 系数不为 0，指数为 0，则省略未知数部分
            if (p->coef == 1)
            {
                // 系数为一，省略乘号
                cout << "X^" << p->expn;
            }
            else
            {
                // 系数为一，显示乘号
                cout << "·X^" << p->expn;
            }
        }
        if (p->next == NULL)
        {
            // 结尾，换行
            cout << endl;
        }
        else
        {
            // 判断下一项的系数，添加符号
            if(p->next->coef < 0)
                cout << " ";
            else
                cout << " + ";
        }

        p = p->next;
    }

}

// 判断多项式的长度
int LengthPolyn(ListNode L)
{
    int num = 0;
    if (!L->next) return num;       // 判断是否为空多项式
    ListNode p = L;
    while (p->next != NULL)
    {
        p = p->next;
        num++;
    }
    return num;
}
// 判断是否为空
bool IsNULL(ListNode L)
{
    return L->next == NULL;
}

//处理 多项式 与 只有一项的多项式
bool AddOnePolyn(ListNode &L1, ListNode &L2)
{
    ListNode p1, p2 , q;
    if (LengthPolyn(L1) < LengthPolyn(L2))
    {
        // 第一个多项式长度 小于 第二个多项式
        p1 = L2, p2 = L1;
    }
    else
    {
        // 否则，默认
        p1 = L1, p2 = L2;
    }

    while (p1->next != NULL)
    {
        if (p2->expn == p1->expn)
        {
            // 当指数相同，系数相加
            p1->coef = p1->coef + p2->coef;
            // 释放内存空间
            free(p2);
            return true;
        }
        else if (p2->expn > p1->expn && p2->expn < p1->next->expn)
        {
            // 位于第一个多项式某两项之间
            // 新建空间 q ，存放 p2 的内容
            q = (ListNode)malloc(LIST_SIZE);
            if (!q) exit(1);
            q->coef = p2->coef;
            q->expn = p2->expn;
            q->next = NULL;
            // 添加 q 到 p1 中
            q->next = p1->next;
            p1->next = q;
            // 释放内存空间
            free(p2);
            return true;
        }
        else if (p2->expn < L1->next->expn)
        {
            // 小于第一个多项式的第一项
            p2->next = p1;
            L1->next = p2;
            return true;
        }
        p1 = p1->next;
    }
        // 处理最后一项
    if (p1->next == NULL)
    {
        if (p2->expn == p1->expn)
        {
            // 当指数相同，系数相加
            p1->coef = p1->coef + p2->coef;
            // 释放内存空间
            free(p2);
        }
        else
            p1->next = p2;
    }
    return true;
}

// 合并多项式
bool AddPolyn(ListNode &L1, ListNode &L2)
{
    if ((IsNULL(L1) && IsNULL(L2))
        || (!IsNULL(L1) && IsNULL(L2))
        )
    {
        // 两个都为空
        // 第一个不为空，第二个为空
        return false;
    }
    else if (IsNULL(L1) && !IsNULL(L2))
    {
        // 第一个为空，第二个不为空
        L1 = L2;
        return true;
    }
    ListNode p1, p2;
    if (LengthPolyn(L1) < LengthPolyn(L2))
    {
        // 第一个多项式长度 小于 第二个多项式
        p1 = L2->next, p2 = L1->next;
    }
    else
    {
        // 否则，默认
        p1 = L1->next, p2 = L2->next;
    }


    ListNode q , p;
    // q 作用： 新建内存，存放数据
    // p 作用： 释放L2元素内存空间

    //可以释放L2头节点
    L2->next = NULL;
    free(L2);

    // 若第二个多项式仅一项
    if (p2->next == NULL)
    {
        if (AddOnePolyn(p1, p2))
            return true;
        else
            return false;
    }


    while (1)
    {
        if (p1->next == NULL || p2->next == NULL)
        {// 当一个多项式结束，则跳出循环
            break;
        }
        if (p1->expn == p2->expn)
        {
            // 当指数相同，系数相加
            p1->coef = p1->coef + p2->coef;

            // 两式均跳到下一项
            if (p1->coef == 0)
            {
                // 若系数为0，需要删除本位元素，并释放空间
                // 存在问题，最后一项系数为零无法去除，因此创建方法  void DelZeroPolyn(ListNode &L)  去除系数为零
                // 虽然 DelZeroPolyn 可以去除全部为零的项，但为了减少内存占用，此处先去除中间的零
                if (p1->next != NULL)
                {
                    // 方法： 
                    // 把下一项传过来，释放下一项
                    // 先判断下一项是否为空
                    q = p1->next;                   // 获取下一项的地址
                    p1->coef = p1->next->coef;      // 修改 本项系数 为 下一项系数
                    p1->expn = p1->next->expn;      // 修改 本项指数 为 下一项指数
                    p1->next = p1->next->next;      // 指针 指向 下一项的下一项
                    free(q);                        // 释放下一项的内存空间
                }
            }
            else
            {
                p1 = p1->next;
            }

            p = p2;
            p2 = p2->next;
            // 释放内存空间
            free(p);
        }
        else if (p1->expn > p2->expn)
        {
            // 添加数据项
            // 若第一项指数大于第二项，因此第二项 遍历直到遇到 第一项相同的指数，中间的添加到 L1式中
            // 新建空间 q ，存放 p2 的内容
            q = (ListNode)malloc(LIST_SIZE);
            if (!q) exit(1);
            q->coef = p2->coef;
            q->expn = p2->expn;
            q->next = NULL;
            // 添加 q 到 p1 中
            q->next = p1->next;
            p1->next = q;

            // 获取p2当前位置
            p = p2;
            // L2跳到下一项
            p2 = p2->next;
            p1 = p1->next;
            // 释放内存空间
            free(p);
        }
        else if (p1->expn < p2->expn)
        {
            // 若第一项指数小于第二项，遍历到下一项
            p1 = p1->next;
        }

    }
    // 最后一项没有进行检测，因此需要在次检测
    if ( (p1->next == NULL && p2->next == NULL) || (p2->next == NULL && p1->next != NULL))
    {
        if (AddOnePolyn(p1, p2))
            return true;
        else
            return false;
    }
    // 当第一个多项式结束，第二个多项式仍存在，则把第二个多项式的内容追加在第一个多项式后边
    if (p1->next == NULL && p2->next != NULL)
    {
        p1->next = p2;
    }
}

// 处理系数为零的情况
void DelZeroPolyn(ListNode &L)
{
    // 判断是否为空
    if (IsNULL(L))
    {
        return;
    }
    ListNode p = L->next , fr;

    // 处理第一项
    if (p->coef == 0)
    {
        L->next = p->next;
    }
    while (p->next->next != NULL)
    {
        if (p->next->coef == 0)
        {
            fr = p->next;
            p->next = fr->next;
            free(fr);
        }
        p = p->next;
    }
    // 处理最后一项
    if (p->next->coef == 0)
    {
        fr = p->next;
        p->next = NULL;
        free(fr);
    }
}

// 多项式排序
void ListLink(ListNode &L, int length)
{
    if (length < 0 || L->next == NULL) return;
    int i = 0;
    // 最多的可能项为 n-1
    while (i < length)
    {
        SortPolyn(L);
        i++;
    }
}

// 插入删除错误位置的元素
bool SortPolyn(ListNode &L)
{
    if (IsNULL(L)) return false;
    ListNode e;
    if (!UnOrderPro(L, e))      // 获取有问题的第一项
    {
        return false;
    }
    ListNode lo = L->next;
    // 判断第一项，lo是第一项
    if (lo->expn >= e->expn)
    {
        e->next = lo;
        L->next = e;
        return true;
    }

    while (lo->next != NULL)
    {
        if (e->expn >= lo->expn && e->expn <= lo->next->expn)
        // 中间某项，指数在本项和后一项之间，便插入
        {
            e->next = lo->next;
            lo->next = e;
            break;
            return true;
        }
        lo = lo->next;
    }
    // 判断最后一项
    if (lo->next == NULL && lo->expn <= e->expn)
    {
        lo->next = e;
        return true;
    }
    return false;
}

// 删除书序有问题的指针，并返回该指针
bool UnOrderPro(ListNode &L,LNode * &e)
{
    if (IsNULL(L)) return false;            // 空的多项式
    ListNode p = L->next;

    // p 对应 多项式的第一项
    if (p->next == NULL) return false;      // 若只有一项，直接返回

    if ( p->expn > p->next->expn)           // 判断第一项是否合理
    {
        e = p;              // 获取第一项
        L->next = p->next;  // 删除第一项
        e->next = NULL;     // 修改第一项的next指针，防止影响原多项式
        return true;
    }
    
    // 除第一项和最后一项，中间第一个位置有问题的项
    while (p->next->next != NULL)
    {
        // 比较连续三项的指数
        if ( (  (p->expn < p->next->expn) && (p->next->expn > p->next->next->expn)  )   // 中间项 大于 前一项 且 大于 后一项
            ||  (p->expn > p->next->expn)           // 中间项 小于 前一项
            )
        {
            e = p->next;                // 获取错误项
            p->next = p->next->next;    // 修改指针，删除中间项
            e->next = NULL;             // 修改错误项的next指针，防止影响原多项式
            return true;
        }
        p = p->next;        // 遍历到下一项
    }

    // 判断最后一项是否正确
    if (p->next->next == NULL && (p->expn > p->next->expn) )
    {
        //比较最后两项，若最后一项系数不正确，修改倒数第二次项的next指针
        e = p->next;
        e->next = NULL;             // 修改错误项的next指针，防止影响原多项式
        p->next = NULL;
        return true;
    }
    //当顺序正确，不删除任何，进行初始化
    return false;
}

// 多项式去重，前提条件，必须是有序多项式
void UnRepetition(ListNode &L)
{
    if (IsNULL(L)) return;
    ListNode q = L->next;
    ListNode fr;
    while (q->next != NULL)
    {
        if (q->expn == q->next->expn)
        {
            // 连续两项指数相等，系数相加，删除后一项，并释放内存空间
            q->coef = q->coef + q->next->coef;
            fr = q->next;
            q->next = q->next->next;
            free(fr);
        }
        else
        {
            q = q->next;
        }
    }
}

简便方法：直接将两个多项式，合并，不排序，不去重，把最后的合并式直接去重，不需要写上边折磨复杂，把两个多项式一项一项拼接，感觉有好多bug

void s()
{
    ListNode L1 = CreatePolyn();                    // 创建多项式
    cout << "_________________________" << endl;
    ListNode L2 = CreatePolyn();                    // 创建多项式
    ListNode p = L1;
    while (p->next != NULL)
    {
        p = p->next;
    }
    if(p->next == NULL)
        p->next = L2->next;
    cout << "_________________________" << endl;
    cout << "L" << " = ";
        FindPolyn(L1);
    cout << "_________________________" << endl;
    ListLink(L1, LengthPolyn(L1));
    cout << "L" << " = ";
    FindPolyn(L1);
    cout << "_________________________" << endl;
    UnRepetition(L1);
    cout << "L" << " = ";
    FindPolyn(L1);
}

现在处于学习阶段，考虑问题时，可能不全面，程序可能存在Bug，没有找到，欢迎指正，会及时处理并修改

个人感觉，还存在一些bug，写的时候出现各种bug，处理起来都快吐了