#include <iostream.h>
#if !defined(AFX_SLItem_H__890711BE_DB9F_4EFA_88C4_51B43F6F7E99__INCLUDED_) //头文件预处理块
#define AFX_SLItem_H__890711BE_DB9F_4EFA_88C4_51B43F6F7E99__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
//////////////////////////////////////////////////////////////////////
// 单链表的节点类
// 版本：1.0
//////////////////////////////////////////////////////////////////////
class SLItem //节点类声明
{
public:
SLItem(double val, int exp);
SLItem(const SLItem& item);
~SLItem();
//节点有如下职责
inline double Value(){return value_;} //告知自己的系数
inline int Exp(){return exp_;} //告知自己的指数
inline void Value(const double& val){value_=val;} //设置自己的系数
inline void Exp(const int& e){exp_=e;} //设置自己的指数
inline SLItem* Next(){return next_;} //告知自己的后续节点
inline void Next(SLItem* p){next_=p;} //设置自己的后续节点
void InsertAfter(SLItem* p); //在自己后面插入一个节点
//节点的运算
const SLItem& operator=(const SLItem& item); //赋值运算
const SLItem& operator+=(const SLItem& item); //加法，合并同类项，这里只能实现“+=”，如何实现“+”是个值得深思的问题，到底应该返回什么类型，const x&的话会造成内存泄漏的
const SLItem& operator*(const SLItem& item); //乘法
private:
double value_;
int exp_;
SLItem* next_;
};
//////////////////////////////////////////////////////////////////////
// 单链表多项式类
// 版本：1.0
//////////////////////////////////////////////////////////////////////
class SLPoly
{
public:
SLPoly();
~SLPoly();
//链表表示的是一个多项式，其职责如下
bool IsNull(void) const;//判断自己是否为0多项式
SLItem* Find(int exp); //找到一个指数为指定值的节点，否则返回空
void Delete(void); //删除头节点和尾节点中间所有的节点
void Insert(double val, int exp); //将一个项插入到多项式
void Insert(SLItem *item); //将一个节点插入到多项式
//多项式的运算
const SLPoly& operator=(const SLPoly& list); //赋值运算
const SLPoly& operator*(const SLPoly& list); //乘法运算
private:
SLItem* head_;
SLItem* tail_;
SLItem* FindPosition(const int&); //找到指数为指定值的插入位置
};
//////////////////////////////////////////////////////////////////////
// 单链表节点类函数定义
// 版本：1.0
//////////////////////////////////////////////////////////////////////
SLItem::SLItem(double val=0, int exp=0)
{
value_=val;
exp_=exp;
next_=NULL;
};
SLItem::SLItem(const SLItem& item)
{
value_=item.value_;
exp_=item.exp_;
next_=NULL; //为什么要使用NULL还没有什么道理，暂时这么用了
};
SLItem::~SLItem()
{
//delete next_;
};
void SLItem::InsertAfter(SLItem* p)
{
SLItem *temp = p;
temp->Next(next_);
next_ = p;
};
const SLItem& SLItem::operator=(const SLItem& item) //赋值运算
{
value_ = item.value_;
exp_ = item.exp_;
next_ = NULL;
return *this; //此处返回的是左值
}
const SLItem& SLItem::operator+=(const SLItem& item) //加法，合并同类项
{
value_+=item.value_;
return *this;
}
const SLItem& SLItem::operator*(const SLItem& item) //乘法
{
SLItem* temp=new SLItem(0);
temp->value_=value_*item.value_;
temp->exp_=exp_+item.exp_;
temp->next_=NULL;
return *temp;
}
//////////////////////////////////////////////////////////////////////
// 单链表类函数定义
// 版本：1.0
//////////////////////////////////////////////////////////////////////
SLPoly::SLPoly()
{
tail_ = new SLItem(0,0);
head_ = new SLItem(0,0);
head_->Next(tail_);
}
SLPoly::~SLPoly()
{
Delete();
delete tail_;
delete head_;
}
SLItem* SLPoly::Find(int exp)
{
SLItem* p = head_->Next(); //首先指向头节点后第一个节点
if (p == tail_) return NULL; //如果这个节点是尾节点，那么返回空
while (p->Exp() != exp) //如果这个不是要找的节点
{
p = p->Next(); //往后移一个
if (p == tail_) return NULL; //如果移到尾节点了，返回空
}
return p; //否则，就是找到了
};
void SLPoly::Delete()
{
SLItem* temp = head_; //首先指向头节点
while (temp->Next()!=tail_) //如果下一个不是尾节点
{
temp = temp->Next(); //把临时指针往后移一个
head_->Next(temp->Next()); //孤立临时指针指的那个节点
delete temp; //删除临时指针所指的节点
temp = head_; //临时指针再次指向头指针
}
};
void SLPoly::Insert(double val, int exp) //按照升序插入元素
{
SLItem* temp=new SLItem(val,exp); //生成新节点
SLItem* p=Find(exp);
if (p!=NULL) //如果原来的队列里已经存在了指数相同的节点
{
(*p)+=(*temp); //将新节点加上去
}
else
{
p=FindPosition(exp); //找到插入位置
p->InsertAfter(temp); //插入节点
}
};
void SLPoly::Insert(SLItem *item)
{
SLItem *p;
p=Find(item->Exp());
if (p!=NULL) //原理同上
{
(*p)+=*item;
}
else
{
p=FindPosition(item->Exp());
p->InsertAfter(item);
}
};
SLItem* SLPoly::FindPosition(const int& exp) //此函数用以找寻插入位置
{
SLItem* p=head_;
while (p->Next()!=tail_ && p->Next()->Exp()<exp) //搜索的队列为一个升序队列
{
p=p->Next();
}
return p;
};
bool SLPoly::IsNull() const//判断自己是否为0多项式
{
if (head_->Next()==tail_)
{
return true;
}
else
{
return false;
}
};
const SLPoly& SLPoly::operator=(const SLPoly& list) //赋值运算
{
SLItem* current=list.head_->Next();
while(current!=list.tail_)
{
Insert(current->Value(),current->Exp());
current=current->Next();
}
return *this;
};
const SLPoly& SLPoly::operator*(const SLPoly& list) //乘法运算
{
SLPoly* temp=new SLPoly();
SLItem *p,*q; //用指针分别指向要相乘的两条队列的首项
p=head_->Next();
q=list.head_->Next();
while (p!=tail_)
{
while (q!=list.tail_)
{
SLItem *newitem=new SLItem((*p)*(*q)); //两个节点相乘产生新的节点
temp->Insert(newitem); //将新节点插入队列
q=q->Next(); //第二条队列的指针向后移动
}
q=list.head_->Next(); //第二条队列的指针复位
p=p->Next();
}
return *temp;
};
#endif // !defined(AFX_SLItem_H__890711BE_DB9F_4EFA_88C4_51B43F6F7E99__INCLUDED_)