类似于有序表合并（顺序表中有介绍）
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;
}
网友评论