类似于有序表合并（单链表中有介绍）
1.两个多项式合并式，需要考虑指数不尽相同的情况，故采用结构体（包括指数和系数）作为单链表表中的结点数据，需要重载'='、'+'等运算操作符。
2.与有序表合并不同的是，多项式合并时，如果遇到指数相同的情况，需要将系数相加后插入到新链表中，且两个表的指针都需要后移，如果系数相加后为0，则不需要添加到新链表中。
如：
多项式合并
LinkListPoly.h
#pragma once
// 函数结果状态代码
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型，其值是函数结果状态代码
typedef int Status;
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;
}
};
//数据类型
typedef struct Poly ElemType;
typedef struct LNode //链表节点
{
ElemType data; //数据域
struct LNode* next; //指针域
}LNode, * LinkList;
//初始化链表
Status InitList(LinkList& L);
//判断链表是否为空
bool ListEmpty(LinkList L);
//尾插插入单个元素
void ListInsert_T(LinkList& L, ElemType e);
//遍历
void ListTraverse(LinkList L);
//有序表合并
void ListMerge_Sq(LinkList& L1, LinkList L2);
LinkListPoly.cpp
#include <iostream>
#include "LinkListPoly.h"
using namespace std;
ostream& operator<<(ostream& cout, ElemType data)
{
cout << "index=" << data.index << " " << "coefficient=" << data.coefficient << endl;
return cout;
}
//初始化链表
Status InitList(LinkList& L)
{
L = new LNode; //或L(LinkList)malloc(sizeof(LNode))
L->next = NULL;
cout << "初始化链表成功" << endl;
return OK;
}
//判断链表是否为空
bool ListEmpty(LinkList L)
{
if (L)
{
if (L->next == NULL)
{
cout << "链表为空" << endl;
return true;
}
else
{
cout << "链表不为空" << endl;
return false;
}
}
else
{
cout << "链表不存在" << endl;
return true;
}
}
//尾插插入单个元素
void ListInsert_T(LinkList& L, ElemType e)
{
LNode* p = L;
while (p->next)
{
p = p->next;
}
LNode* s = new LNode;
s->data = e;
s->next = NULL;
p->next = s;
}
//遍历
void ListTraverse(LinkList L)
{
if (ListEmpty(L) || !L)
{
cout << "链表为空或者不存在" << endl;
return;
}
LNode* p = L->next;
while (p)
{
cout << p->data;
p = p->next;
}
cout << endl;
}
//有序表合并，合并到L1中
void ListMerge_Sq(LinkList& L1, LinkList L2)
{
LNode* p1 = L1->next; //第一个结点
LNode* p2 = L2->next;
LNode* p3 = L1; //p3指向合并的链表最后一个结点
while (p1 && p2)
{
if (p1->data.index > p2->data.index) //如果p2小，
{
p3->next = p2; //将p2加入到合并链表
p2 = p2->next; //p2后移
p3 = p3->next; //添加一个，p3后移一个，保持始终指向末尾结点
}
else if (p1->data.index == p2->data.index)
{
if ((p1->data.coefficient + p2->data.coefficient)) //相加后系数不为0
{
LNode* s = new LNode;
s->data.index = p1->data.index;
s->data.coefficient = p1->data.coefficient + p2->data.coefficient; //系数之和
s->next = NULL;
p3->next = s;
p3 = p3->next; //添加一个，p3后移一个，保持始终指向末尾结点
}
p1 = p1->next;
p2 = p2->next;
}
else
{
p3->next = p1; //将p1加入到合并链表
p1 = p1->next; //p1后移
p3 = p3->next; //添加一个，p3后移一个，保持始终指向末尾结点
}
}
p3->next = p1 ? p1 : p2; //p1或者p2中未合并完的加入到合并链表
}
main.cpp
测试：
#include <iostream>
#include "LinkListPoly.h"
using namespace std;
int main(int argc, char** argv)
{
LinkList L1, L2;
InitList(L1);
InitList(L2);
ElemType d1(0, 7), d2(1, 3), d3(8, 9), d4(17, 5), d5(1, 8), d6(7, 22), d7(8, -9);
ListInsert_T(L1, d1);
ListInsert_T(L1, d2);
ListInsert_T(L1, d3);
ListInsert_T(L1, d4);
ListInsert_T(L2, d5);
ListInsert_T(L2, d6);
ListInsert_T(L2, d7);
ListTraverse(L1);
ListTraverse(L2);
ListMerge_Sq(L1, L2);
ListTraverse(L1);
return 0;
}
网友评论