linklist.h

用从c++语言实现多项式的输入及计算

//////////////////////////////////////////////////////////////////////////
//   本文件内容：（1）模板类link         ：链（表结点）类
//               （2）模板类list         ：表类
//               （3）模板类listIterator ：表遍历器类
//
//   数据成员  ：（1）link类
//                       T         value;
//                       link<T>*  ptrToNextLink;
//               （2）list类
//                       link<T>*  ptrToFirstLink;
//               （3）listIterator类
// 	                   link<T>*  currentLink;
//                       link<T>*  previousLink;
//                       list<T>&  theList;
//
//   成员函数：
//
//  （1）link类
//
//	    insert：         link<T>* (T val);
//                      插入val结点于当前结点之后，返回新结点
//     duplicate：      link<T>* () const
//                      复制当前结点及后面全链
//
//  （2）list类
//
//     add：            virtual void (T value)
//                      插入表首
//     deleteAllValues：virtual void ()
//                      置为空表,删除所有结点.用于析构、拷贝和赋值之.
//     firstElement：   T () const
//                      返回表首元素
//     includes：       virtual bool (T value) const
//                      检测表中有没有值为value的结点
//     isEmpty：        bool () const
//                      检测是否空表
//     removeFirst：    virtual void ()
//                      删除表首元素
//     duplicate：      list<T>* () const
//                      返回复制过的新表指针
//     operator =：     list<T>&  (const list<T>& t) 赋值函数
//     append：         void (const list<T>& r) 添加r表于尾部
//
//  （3）listIterator类
//
//    init();operator()；operator !；operator ++；operator=;
//
//    removeCurrent：   virtual void ()
//                      删除当前元素
//    addBefore：       virtual void (T newval)
//                      插入新结点于当前元素之前
//    addAfter：        virtual void (T newval)
//                      插入新结点于当前元素之后
//
//
//////////////////////////////////////////////////////////////////////////
#ifndef LINKLIST_H
#define LINKLIST_H
#include "iterator.h"
#include <iostream.h>
#include <assert.h>
template <class T> class list;
template <class T> class listIterator;
template <class T> class ordltIterator;
template <class T> class selfList;
template <class T> class circularList;
template <class T> class doubleEndList;
template <class T> class doubleEndIterator;
template <class T> class circularListIterator;
template <class T> class queueCircularList;

template <class T>
class link
{
public:
	link<T>* insert(T val);      //插入val结点于当前结点之后，返回新结点
protected:
	link(T val, link<T>* next);  //构造函数只让友元用，不是public成员
   //link(const link<T>& s);    //浅拷贝构造函数可略
   link<T>* duplicate() const;  //复制当前结点及后面全链
   T value;
   link<T>* ptrToNextLink;
   friend class list<T>;
   friend class selfList<T>;
   friend class circularList<T>;
   friend class doubleEndList<T>;
   friend class listIterator<T>;
   friend class ordltIterator<T>;
   friend class iterator<T>;
   friend class doubleEndIterator<T>;
   friend class circularListIterator<T>;
   friend class queueCircularList<T>;
   //friend ostream&  operator << (ostream& out, circularList<T>& a);

};

template <class T>
class list
{
 public:
	list();
   list(const list<T> & source);        //拷贝构造函数采用深拷贝，不可缺省
   virtual ~list();                     //析构函数是虚函数，子类可自行定义。
   virtual void add(T value);           //插入表首
   virtual void deleteAllValues();      //置为空表,删除所有结点.用于析构、拷贝和赋值之.
   T firstElement() const;              //返回表首元素
   virtual bool includes(T value) const;//检测表中有没有值为value的结点
   bool isEmpty() const;                //检测是否空表
   virtual void removeFirst();          //删除表首元素
   list<T>* duplicate() const;          //返回复制过的新表指针
   list<T>& operator = (const list<T>& t); //赋值函数
   void append(const list<T>& r);          //添加r表于尾部
   void display( ostream& out);            //调试用
   friend class listIterator<T>;
   friend class ordltIterator<T>;
   friend class iterator<T>;
protected:
	link<T>* ptrToFirstLink;
};

template <class T>
class listIterator: public iterator<T> {
 public:
    listIterator(  list<T>& a);       //theList是引用，a不能是const
    virtual int init();
    virtual T operator() ();
    virtual int operator !();
    virtual int operator ++();
    virtual void operator=(T val);
    void removeCurrent();     // 删除当前元素
    void addBefore(T newval); // 插入新结点于当前元素之前
    void addAfter(T newval);  // 插入新结点于当前元素之后
 protected:
 	link<T>* currentLink;
   link<T>* previousLink;
   list<T>& theList;
 };


template <class T>
link<T>::link(T val, link<T>* next) //T可为引用类型
	:value(val),ptrToNextLink(next)
{
	//cout<<"\t结点()"<<'@'<<this<<" {"<<value<<" "<<ptrToNextLink<<"}\n";
}
/*
template <class T>
link<T>::link(const link<T>& s)
	:value(s.value),ptrToNextLink(s.ptrToNextLink)
{
  //	cout<<"\t结点(&)"<<'@'<<this<<" {"<<value<<" "<<ptrToNextLink<<"}\n";
}
*/
template <class T>
link<T>* link<T>::insert(T val)
{  //在本结点之后，插入一个值为val的新结点
	ptrToNextLink=new link<T>(val,ptrToNextLink);
   assert(ptrToNextLink!=0);
   return ptrToNextLink;
}
template <class T>
link<T>* link<T>::duplicate() const
{
	link<T>* newnode;
   if (ptrToNextLink!=0)
   	newnode=new link<T>(value,ptrToNextLink->duplicate());
   else
      newnode=new link<T>(value,0);
   assert(newnode!=0);
   return newnode;
}

template <class T>
list<T>:: list():ptrToFirstLink(0)
{
    //cout<<"\t表( )"<<'@'<<this<<" {"<<ptrToFirstLink<<"}\n";
}

template <class T> //复制需深
list<T>::list(const list<T> & s)
{
	//cout<<"\t表(&)"<<'@'<<this<<" {"<<ptrToFirstLink<<"}\n";
   if (s.isEmpty()) ptrToFirstLink=0;
   else
   {
   	link<T> *pf=s.ptrToFirstLink;
      ptrToFirstLink=pf->duplicate();
   }
}

template <class T>
void list<T>::add(T val)
{
	ptrToFirstLink=new link<T>(val,ptrToFirstLink);
   assert(ptrToFirstLink!=0);
}

template <class T>
void list<T>::deleteAllValues()  //置为空表，删除所有结点
{
	link<T> *next,*p;
   for (p=ptrToFirstLink; p!=0; p=next)
   {
   	next=p->ptrToNextLink;
      p->ptrToNextLink=0;   // 似多余
      delete p;
   }
   ptrToFirstLink=0;
}

template <class T>
T list<T>::firstElement() const
{
	assert(ptrToFirstLink!=0);
   return ptrToFirstLink->value;
}

template <class T>
bool list<T>::includes(T val) const
{
	for (link<T>* p=ptrToFirstLink; p; p=p->ptrToNextLink)
   	if (val==p->value) return true;
   return false;
}

template <class T>
bool list<T>::isEmpty() const
{
	return ptrToFirstLink==0;
}

template <class T>
void list<T>::removeFirst()
{
	assert(ptrToFirstLink!=0);
   link<T>* p=ptrToFirstLink;
   ptrToFirstLink=p->ptrToNextLink;
   delete p;
}

template <class T>
list<T> * list<T>::duplicate() const
{
	list<T>* newlist=new list<T>;
   assert(newlist!=0);
   if (ptrToFirstLink)
   	newlist->ptrToFirstLink = ptrToFirstLink->duplicate();
   return newlist;
}
template <class T>
list<T>&  list<T>::operator = (const list<T>& t)
{
   deleteAllValues();
   if (t.ptrToFirstLink)
   	ptrToFirstLink = t.ptrToFirstLink->duplicate();
   return *this;
}
template <class T>
list<T>::~list()
{
	//cout<<" ~list()"<<this<<endl;
   deleteAllValues();
}
template <class T>
void list<T>::display( ostream& out)
{
   link<T>* p=ptrToFirstLink;
   while(p)
   {
   	out<<p->value<<" ";
      p=p->ptrToNextLink;
   }
   out<<endl;
}

template <class T>
listIterator<T>::listIterator(  list<T>& a):theList(a)
{
	init();
}
template <class T>
int listIterator<T>::init()
{
	previousLink=0;
   currentLink=theList.ptrToFirstLink;
   return currentLink!=0;
}

template <class T>
T listIterator<T>::operator() ()
{
	assert(currentLink!=0);
   return currentLink->value;
}
template <class T>
int listIterator<T>::operator !()
{
	if (currentLink!=0) return 1;  //当前结点在
   if (previousLink!=0) return previousLink->ptrToNextLink!=0;//有前驱结点可决定是否到头
   return theList.ptrToFirstLink!=0; // 无当前也无前驱，看基表
}
template <class T>
int listIterator<T>::operator ++()  //注意 removeCurrent()的处理
{
	if (currentLink!=0)
   {
   	previousLink=currentLink;
      currentLink=currentLink->ptrToNextLink;
   }
   else if (previousLink!=0)
       currentLink=previousLink->ptrToNextLink; //当前结点可能被删除
   else
       currentLink=theList.ptrToFirstLink;  //被删可能是第一结点
   return currentLink!=0;
}
template <class T>
void listIterator<T>::operator=(T val)
{
	assert(currentLink!=0);
   currentLink->value=val;
}
template <class T>
void listIterator<T>::removeCurrent()
{
	assert(currentLink!=0);
   if (previousLink==0)	//删除第一结点
   	theList.ptrToFirstLink =currentLink->ptrToNextLink;
   else
   	previousLink->ptrToNextLink = currentLink->ptrToNextLink;
   delete currentLink;
   currentLink=0;//删除后禁用当前结点
}
template <class T>
void listIterator<T>::addBefore(T val)  //插入,不管当前结点是否空
{
	if (previousLink!=0)
   	previousLink=previousLink->insert(val);
   else
   {
   	theList.list<T>::add(val);
      previousLink=theList.ptrToFirstLink;
   }
   //currentLink=previousLink->ptrToNextLink; //currentLink一律不恢复
}
template <class T>
void listIterator<T>::addAfter(T val)
{
	if (currentLink!=0)	currentLink->insert(val);
   else if (previousLink!=0)  previousLink->insert(val);
   else   theList.list<T>::add(val);
}
template <class T>
ostream&  operator << (ostream& out, list<T>& a)
{
	listIterator<T> litr(a);
   for (litr.init(); !litr; ++litr)
   	out<<litr()<<"  ";
   out<<endl;
   return out;
}
template <class T>
void list<T>::append(const list<T>& r)
{

   if  (isEmpty()) ptrToFirstLink=r.ptrToFirstLink->duplicate();
   else
   {
   	link<T>* p=ptrToFirstLink;
      for(;(p->ptrToNextLink); p=p->ptrToNextLink);
      p->ptrToNextLink=r.ptrToFirstLink->duplicate();
   }
}
/* 等效的另一写法
template <class T>
void list<T>::append(const list<T>& r)
{
	link<T>* p=ptrToFirstLink;
   if  (!p) ptrToFirstLink=r.ptrToFirstLink->duplicate();
   else
   {
   	while(p->ptrToNextLink) p=p->ptrToNextLink;
      p->ptrToNextLink=r.ptrToFirstLink->duplicate();
   }
}*/
#endif