数据结构cpp实现线性表应用 —— 一元多项式表示和实现
一元多项式的表示
多项式的每一项都可以用一个二元组
表示，具体可以表示为
，对于多项式的操作，我们可以用顺序表也可以用链表存储。但因为需要进行插入和删除操作，所以在这里使用链表存储。
加法操作实现的思路 a和b两个加数相加，算法从a、b两个链表头开始取元素，并进行步骤一。
步骤一：
1）指数不等：指数大者插入和多项式链表，并向后取元素
2）指数相等：二者相加后，若非0，则插入和多项式链表
步骤二：
将a、b链表中剩余部分加到和多项式中
减法操作相似，符号变换即可 Polynomial.h代码实现(单链表代码)
#include "LinkList.h"//包含链表类
#include "cmath"
struct PolyItem
{
double coef=0; // 系数
int expn; // 指数
PolyItem(){expn = -1;} ; // 如果是调用无参构造函数，则指数域赋值为0
PolyItem(double cf, int en){coef=cf;expn=en;};// 已知系数域和指数域建立结构
};
class Polynomial {
private:
LinkList<PolyItem> polylist;//多项式的线性表，存储系数和指数信息
public:
Polynomial(){}//无参构造函数什么都不做
~Polynomial(){}//析构函数同理
int Length() const;//获取多项式的项数
bool IsNull() const;//判断多项式是否为空
void SetNull();//将多项式清空
void Display() const;//打印多项式
void InsItem(const PolyItem &it);//插入一项，相当重要的功能
Polynomial operator +(const Polynomial &p) const;
Polynomial operator -(const Polynomial &p) const;
Polynomial &operator =(const Polynomial ©); // 赋值语句重载
Polynomial &operator =(const LinkList<PolyItem> ©LinkList); // 赋值语句重载
double_t Cal(double_t x);
};
int Polynomial::Length() const {
return polylist.GetLength();
}
bool Polynomial::IsNull() const {
return Length()==0;
}
void Polynomial::SetNull() {
polylist.clear();
}
void Polynomial::Display() const {
PolyItem temp;
for(int i=1;polylist.GetElem(i,temp);i++)
{
std::cout<<temp.coef<<"x^"<<temp.expn<<"+";
}
std::cout<<"\b"<<" ";//这个作用是清除多余的一个+号
}
void Polynomial::InsItem(const PolyItem &it) {
//多项式插入项的方式按照降幂排序
int position=1;
PolyItem temp;
while(polylist.GetElem(position,temp)&&temp.expn>it.expn)//查找按照降幂插入的位置
{
position++;
}
polylist.insert(position,it);
}
Polynomial Polynomial::operator+(const Polynomial &p) const {
LinkList<PolyItem> la=polylist;//被加数(被加多项式)
LinkList<PolyItem> lb=p.polylist;//加数
LinkList<PolyItem> lc;//合多项式的链表
int aPos=1,bPos=1;
PolyItem aItem,bItem;
bool aStatus=la.GetElem(aPos++,aItem),bStatus=lb.GetElem(bPos++,bItem);
while(aStatus && bStatus)
{
if(aItem.expn>bItem.expn)//la的项aItem的指数较大
{
lc.insert(aItem);//将取出的la的项插入到合多项式尾
aStatus=la.GetElem(aPos++,aItem);
}
else if(aItem.expn<bItem.expn)//lb的项bItem指数较大
{
lc.insert(bItem);
bStatus=lb.GetElem(bPos++,bItem);
}
else//指数相等的情况
{
PolyItem sumItem(aItem.coef+bItem.coef,aItem.expn);
if(sumItem.coef!=0)
{
lc.insert(sumItem);
aStatus=la.GetElem(aPos++,aItem);
bStatus=lb.GetElem(bPos++,bItem);
}
}
}
while (la.GetElem(aPos++,aItem)) { // 将la的剩余项追加到lc的后面
lc.insert(aItem); // 将aItem追加到lc的后面
}
while (lb.GetElem(bPos++,bItem)) { // 将lb的剩余项追加到lc的后面
lc.insert(bItem); // 将bItem追加到lc的后面
}
Polynomial fc;//合多项式
fc.polylist=lc;
return fc;
}
Polynomial Polynomial::operator-(const Polynomial &p) const {
LinkList<PolyItem> la=polylist;//被减数
LinkList<PolyItem> lb=p.polylist;//减数
LinkList<PolyItem> lc;//合多项式的链表
int aPos=1,bPos=1;
PolyItem aItem,bItem;
bool aStatus=la.GetElem(aPos++,aItem),bStatus=lb.GetElem(bPos++,bItem);
while(aStatus && bStatus)
{
if(aItem.expn>bItem.expn)//la的项aItem的指数较大
{
lc.insert(aItem);//将取出的la的项插入到合多项式尾
aStatus=la.GetElem(aPos++,aItem);
}
else if(aItem.expn<bItem.expn)//lb的项bItem指数较大
{
bItem.coef=-bItem.coef;
lc.insert(bItem);
bStatus=lb.GetElem(bPos++,bItem);
}
else//指数相等的情况
{
PolyItem sumItem(aItem.coef-bItem.coef,aItem.expn);
if(sumItem.coef!=0)
{
lc.insert(sumItem);
aStatus=la.GetElem(aPos++,aItem);
bStatus=lb.GetElem(bPos++,bItem);
}
}
}
while (la.GetElem(aPos++,aItem)) { // 将la的剩余项追加到lc的后面
lc.insert(aItem); // 将aItem追加到lc的后面
}
while (lb.GetElem(bPos++,bItem)) { // 将lb的剩余项追加到lc的后面
lc.insert(bItem); // 将bItem追加到lc的后面
}
Polynomial fc;//合多项式
fc.polylist=lc;
return fc;
}
Polynomial &Polynomial::operator =(const Polynomial ©)
// 操作结果：将多项式copy赋值给当前多项式——赋值语句重载
{
if ( © != this) {
polylist = copy.polylist;
}
return *this;
}
Polynomial &Polynomial::operator =(const LinkList<PolyItem> ©LinkList)
// 操作结果：将多项式组成的线性表copyLinkList赋值给当前多项式
// ——赋值语句重载
{
polylist = copyLinkList;
return *this;
}
double_t Polynomial::Cal(double_t x) {
using namespace std;
double result=0;//计算结果
int i=1;
PolyItem temp;
while(polylist.GetElem(i++, temp))
{
result = result+temp.coef * pow(x,temp.expn);
}
return result;
} main函数
#include <iostream>
#include "Polynomial.h"
int main() {
using namespace std;
Polynomial list,list2,list3;
PolyItem item(1,2);
PolyItem item2(2,2);
list2.InsItem(item);
list3.InsItem(item2);
list=list2-list3;
list.Display();
cout<<list.Cal(2);
return 0;
}运行结果-1x^2 -4