list_link.h

一个不错库存管理算法

#include<iostream.h>
#include<assert.h>
template<class T>
class list;
template<class T>
class listiterator;
//*******************************************************************************
template<class T>
class link
{
public:
	//插入一个新结点
	link<T>*insert(T val);
	//构造函数
	link(T linkvalue,link<T>* np);
	link(const link<T>& s);
	//复制
    link<T>* duplicate()const;
    friend class list<T>;
    friend class listiterator<T>;
//private:	
    T value;
	link<T>* ptrtonextlink;
};
//--------------------------------------------------------------------
template<class T>
link<T>*link<T>::insert(T val)
{
    ptrtonextlink=new link<T>(val,ptrtonextlink);
    assert(ptrtonextlink!=0);
    return ptrtonextlink;
}

//------------------------------
template<class T>
link<T>::link(T val,link<T>* nxt)
:value(val),ptrtonextlink(nxt){}

//-------------------------------
template<class T>
link<T>::link(const link<T>& s)
:value(s.value),ptrtonextlink(s.ptrtonextlink){}

//------------------------------------
template<class T>
link<T>*link<T>::duplicate()const
{
    link<T>* newlink;
    if(ptrtonextlink!=0)             //当还有下一个结点时递归调用复制函数
    newlink=new link<T>(value,ptrtonextlink->duplicate());
    else
    newlink=new link<T>(value,0);
    assert(newlink!=0);              //检查动态分配是否成功
    return newlink;
}

//***********************************************************************
template<class T>
class list
{
public:
    list();
    list(const list<T> &);
    virtual  ~list();
    virtual  void  add(T );
    virtual  void  deleteallvalues();
    T  firstelement( )const;
    virtual  int  includes(T)const;
    int  isempty()const; 
    virtual  void  removefirst();
    list<T> *duplicate()const;
//	friend class listiterator<T>;
//protected:
    link<T>* ptrtofirstlink;
};

//-------------------------------------------------------
template<class T>list<T>::list():ptrtofirstlink(0){}

//--------------------------------------------------
template<class T> list<T>::list(const list<T>&source)
{  
	if(source.isempty())
      ptrtofirstlink=0;
    else
	{
		link<T>*firstlink=source.ptrtofirstlink;
        ptrtofirstlink=firstlink->duplicate();
	}
}

//--------------------------------------------
template<class T> list<T>::~list()
{
	deleteallvalues();
}

//---------------------------------------------------------
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;
    for(link<T>*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>int list<T>::includes(T  v)const
{
	for(link<T>*p=ptrtofirstlink;p;p=p->ptrtonextlink)
       if(v==p->value)return 1;
               return 0;
}

//-------------------------------------------------------
template<class T>int 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;
}

//********************************************************************iterator类定义
template<class T>
class iterator{
public:
	//对循环做初始化
	virtual int init()=0;
	//检查是否还有元素
	virtual int operator!()=0;
	//访问当前元素
	virtual T operator()()=0;
	//访问下一个元素
	virtual int operator++()=0;
	//改变当前元素
	virtual void operator=(T newvalue)=0;
};

//***********************************************************************listiterator
template<class T>class listiterator:public iterator<T>{//表遍历
	public: 
		listiterator(list<T>& );
		virtual  int  init();//初始化游标
  		virtual  int operator!();
  		virtual  T  operator()();
  		virtual  int operator++();//只有该操作能改变游标指向
  		virtual  void operator=(T);
		void  removecurrent();//删除当前结点
		void  addbefore(T);//在当前结点前插入
		void  addafter(T);//在当前结点后插入
	protected:
		link<T> * currentlink;      //遍历中的游标（指针）
		link<T> * previouslink;            //遍历中的前驱游标（指针）
		list<T>& thelist;        //引用一个表
};

//-----------------------------------------------------------------------
template<class T>listiterator<T>::listiterator(list<T>& alist):thelist(alist)
{
	init();
}

//------------------------------------------------------------------------
template<class T>int listiterator<T>::init()
{    
	previouslink=0;
	currentlink=thelist.ptrtofirstlink;
	return currentlink!=0;
}

//--------------------------------------------------------
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>T listiterator<T>::operator()(){
	if (currentlink!=NULL) 	return  currentlink->value;
	else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
			return  previouslink->ptrtonextlink->value;
    else if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
			return thelist.ptrtofirstlink->value;

assert(previouslink!=NULL&&previouslink->ptrtonextlink
!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}

//----------------------------------------------------------------------------
template<class T>int listiterator<T>::operator++()
{
	if(currentlink==0)
	{  
		if(previouslink==0)
            currentlink=thelist.ptrtofirstlink;
        else	
			currentlink=previouslink->ptrtonextlink;
	}
    else 
	{
		previouslink=currentlink;
        currentlink=currentlink->ptrtonextlink;
	}
    return currentlink!=0;
}

//---------------------------------------------------------------
template<class T> void listiterator<T>::operator=(T val){
	if (currentlink!=NULL)
	{
		currentlink->value=val; return;
	}
	else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
previouslink->ptrtonextlink->value=val;
return;
    if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
thelist.ptrtofirstlink->value=val; return ;
	
assert(previouslink!=NULL&&previouslink->ptrtonextlink
!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}

//--------------------------------------------------------------
template<class T>void listiterator<T>::removecurrent()
{//删除当前结点
  link<T> *p;
  if (currentlink!=NULL) {
	if (previouslink==NULL) 
		thelist.ptrtofirstlink=currentlink->ptrtonextlink;
	else previouslink->ptrtonextlink=currentlink->ptrtonextlink;
	delete currentlink;	currentlink=0; 
	return;
  }
  else 
	if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL){
		p=previouslink->ptrtonextlink;
		previouslink->ptrtonextlink=p->ptrtonextlink;
		delete p; 	return ;
  	}
  	else 
		if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL){
			p=thelist.ptrtofirstlink;
			thelist.ptrtofirstlink=p->ptrtonextlink;
			delete p;
			return ;
  		}
        assert(previouslink!=NULL&&previouslink->ptrtonextlink!=NULL
        ||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}

//-----------------------------------------------------------
template<class T>void listiterator<T>::addbefore(T val)
{  
	if(previouslink)
       previouslink=previouslink->insert(val);
    else
	{  
	   thelist.list<T>::add(val);
	   previouslink=thelist.ptrtofirstlink;
	}
}

//-----------------------------------------------------------------
template<class T>
void listiterator<T>::addafter(T val){
	//当前结点非空，在当前结点后插入
	if (currentlink!=NULL) 
		currentlink->insert(val);
	else if (previouslink!=NULL) //当前结点空，但前驱非空
		if (previouslink->ptrtonextlink!=NULL)
			 //前的后继非空，在前驱的后继结点后插入
			previouslink->ptrtonextlink->insert(val);
		else 	
		previouslink->insert(val);
	else  if  (thelist.ptrtofirstlink)//表非空，在第一个结点后插入
		 	thelist.ptrtofirstlink-> insert(val);
	else  thelist.add(val);
						//表空，作为第一个结点插入
}