顺序表实现多项式合并

类似于有序表合并（顺序表中有介绍）

1.两个多项式合并式，需要考虑指数不尽相同的情况，故采用结构体（包括指数和系数）作为顺序表中的数据，需要重载'='、'+'等运算操作符。
2.与有序表合并不同的是，多项式合并时，如果遇到指数相同的情况，需要将系数相加后插入到新顺序表中，且两个表的指针都需要后移，如果相加后系数为0，则不需要添加到新的顺序表中。
如：

SqListPoly.h

#pragma once
#define MAXSIZE 20

//函数结果状态代码
#define OK      1
#define ERROR   0
#define INFEASIBLE  -1
#define OVERFLOW    -2

struct Poly
{
    int index;          //指数
    float coefficient;  //系数

    //默认构造
    Poly()
    {
        this->index = 0;
        this->coefficient = 0;
    }
    //有参构造
    Poly(int index, float coefficient)
    {
        this->index = index;
        this->coefficient = coefficient;
    }

    //重载 =
    Poly& operator=(Poly& data)
    {
        index = data.index;
        coefficient = data.coefficient;

        return *this;
    }
};

//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
typedef struct Poly ElemType;   //元素类型为char

//动态数组
typedef struct
{
    ElemType* elem;
    int length;
}SqList_dynamic;

//构造一个空的顺序表
Status InitSqlList(SqList_dynamic& L);

//判断线性表是否存在
bool IsExist(SqList_dynamic L);

//查找（找到返回位置序号，未找到返回0）
int LocateElem(SqList_dynamic L, ElemType e);

//插入
int ListInsert(SqList_dynamic& L, int i, ElemType e);

//遍历
int ListTraverse(SqList_dynamic L);

//多项式合并
void ListMerge_sq(SqList_dynamic L1, SqList_dynamic L2, SqList_dynamic& L3);

SqListPoly.cpp

#include "SqListPoly.h"

#include <iostream>
using namespace std;

ostream& operator<<(ostream& cout, ElemType data)
{
    cout << "index=" << data.index << " " << "coefficient=" << data.coefficient << endl;
    return cout;
}

//构造一个空的顺序表
Status  InitSqlList(SqList_dynamic& L)
{
    L.elem = new ElemType[MAXSIZE]; //为顺序表分配空间
    if (!L.elem)                    //内存分配失败
    {
        cout << "内存分配失败" << endl;
        exit(OVERFLOW);
    }

    L.length = 0;                   //空表长度为0
    cout << "线性表初始化成功" << endl;

    return OK;
}
//判断线性表是否存在
bool IsExist(SqList_dynamic L)
{
    if (L.elem)
    {
        //cout << "L存在" << endl;
        return true;
    }
    else
    {
        //cout << "L不存在" << endl;
        return false;
    }
}

//查找（找到返回位置序号，未找到返回0）(平均查找长度（n+1）/2,n=L.length),则平均时间复杂度为O(n)
int LocateElem(SqList_dynamic L, ElemType e)
{
    if (!IsExist(L))
    {
        cout << "L不存在" << endl;

        return ERROR;
    }
    for (int i = 0; i < L.length; i++)
    {
        if (L.elem[i].index == e.index && L.elem[i].coefficient == e.coefficient)
        {
            cout << e << "对应的序号为：" << i + 1 << endl;
            return i + 1;
        }
    }
    return 0;
}

//插入（平均移动次数n/2,n=L.length）,则平均时间复杂度为O(n)
int ListInsert(SqList_dynamic& L, int i, ElemType e)
{
    if (i < 1 || i > L.length + 1 || L.length == MAXSIZE || (!IsExist(L)))  //插入位置不合法或者存储空间已满
    {
        cout << "插入位置不合法或L不存在" << endl;
        return ERROR;
    }
    for (int j = L.length - 1; j >= i - 1; j--)     //插入位置及之后的元素后移
    {
        L.elem[j + 1] = L.elem[j];
    }                                               //新元素e放入第i个位置
    L.elem[i - 1] = e;
    L.length++;                                     //表长增1

    cout << "插入成功" << endl;

    return OK;
}

//遍历
int ListTraverse(SqList_dynamic L)
{
    if (!L.length || (!IsExist(L)))
    {
        cout << "L为空或L不存在" << endl;
        return ERROR;
    }
    for (int i = 0; i < L.length; i++)
    {
        cout << L.elem[i];
    }
    cout << endl;

    return OK;
}

//多项式合并（类似于有序表合并）
void ListMerge_sq(SqList_dynamic L1, SqList_dynamic L2, SqList_dynamic& L3)
{

    //指向顺序表的开头
    ElemType* p1 = L1.elem;
    ElemType* p2 = L2.elem;

    //指向顺序表的末尾
    ElemType* p1_last = L1.elem + L1.length - 1;
    ElemType* p2_last = L2.elem + L2.length - 1;

    while (p1 <= p1_last && p2 <= p2_last)
    {
        if ((*p1).index > (*p2).index)              //指数不等
        {
            ListInsert(L3, L3.length + 1, *p2++);
        }
        else if ((*p1).index == (*p2).index)        //指数相等
        {

            if ((*p1).coefficient + (*p2).coefficient)  //相加后系数不为0
            {
                Poly* p = new Poly;
                p->index = (*p1).index;
                p->coefficient = (*p1).coefficient + (*p2).coefficient;
                ListInsert(L3, L3.length + 1, *p);
            }

            p1++;
            p2++;
        }
        else                                        //指数不等
        {
            ListInsert(L3, L3.length + 1, *p1++);
        }
    }

    while (p1 <= p1_last)
    {
        ListInsert(L3, L3.length + 1, *p1++);
    }
    while (p2 <= p2_last)
    {
        ListInsert(L3, L3.length + 1, *p2++);
    }
}

main.cpp

测试：

#include "SqListPoly.h"

#include <iostream>

using namespace std;

int main(int argc, char** argv)
{
    SqList_dynamic L1, L2;
    InitSqlList(L1);
    InitSqlList(L2);

    ElemType d1(0, 7), d2(1, 3), d3(8, 9), d4(17, 5), d5(1, 8), d6(7, 22), d7(8, -9);

    ListInsert(L1, 1, d1);
    ListInsert(L1, 2, d2);
    ListInsert(L1, 3, d3);
    ListInsert(L1, 4, d4);

    ListInsert(L2, 1, d5);
    ListInsert(L2, 2, d6);
    ListInsert(L2, 3, d7);


    ListTraverse(L1);
    ListTraverse(L2);

    SqList_dynamic L3;
    InitSqlList(L3);
    ListMerge_sq(L1, L2, L3);
    ListTraverse(L3);
    return 0;
}