两个多项式合并
多项式 L1 与 L2
处理方法：将较短 L2 ，合并到长的 L1
通过逐项比较，依次添加
L1 连续三项指数 ： X ,Y , Z
L1 某项指数 ：N
L2 某项指数 ：M
- 当 M == N 相同，则两项系数相加，然后 L1 与 L2 都跳到下一项
注意：存在系数为0 的情况，位于中间项的可以直接扼杀在摇篮，不占内存空间，位于结尾的则需要单独处理
-
当 X < M < Y ，则需要把 M项 插入到 X,Y 两项 之间
-
开头和结尾需要单独处理，也存在三种可能，指数相同，指数位于两项之间，指数在开头结尾
多项式排序
方法：
- 从左到右剔除第一个顺序有问题的项，并保存
- 将此项插入到合适的位置
- 依次执行，直到没有顺序错误的项
#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，处理起来都快吐了
网友评论