linklist.h

数据结构各种算法的比较程序

#ifndef LINKLIST
#define LINKLIST
#include<iostream>
#include"assert.h"
using namespace std;
template<class T> class Iterator;
template<class T> class link;
template<class T> class list;
template<class T> class listIterator;
template<class T> class orderedlist;
template<class T> class doubleEndlist;

//-----------------------------------------------------------------------------------------------链类
template<class T>
class link
{
public:
	link<T>* insert(T val);
//private:
	link(T val,link<T>* nextptr);
	link(const link<T>& source);
	link<T>* duplicate()const;
	T value;
	link<T>* ptrTonextlink;
	friend class list<T>;
	friend class doubleEndlist<T>;
	friend class listIterator<T>;
};
template<class T> link<T>::link(T val, link<T>* nextptr)
{
	value=val;
	ptrTonextlink=nextptr;
}
template<class T> link<T>::link(const link<T> &source)
{
	value=source.value;
	ptrTonextlink=source.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> link<T>* link<T>::insert(T val)
{
	ptrTonextlink=new link<T>(val,ptrTonextlink);
	assert(ptrTonextlink!=0);
	return ptrTonextlink;
}

//----------------------------------------------------------------------------------------------链类
//----------------------------------------------------------------------------------------------表类
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 int includes(T value)const;
	int isEmpty()const;
	virtual void removeFirst();
	list<T>* duplicate()const;
//protected:
	link<T>* ptrTofirstlink;
	friend class listIterator<T>;
};
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>* newlink=source.ptrTofirstlink;
		ptrTofirstlink=newlink->duplicate();
	}
}
template<class T> list<T>::~list()
{
	deleteAllValues();
}

template<class T> void list<T>::add(T value)
{
	ptrTofirstlink=new link<T>(value,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!=0;p=p->ptrTonextlink)
		if((p->value)==v)  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
{
	assert(ptrTofirstlink!=0);
	list<T>* newlist;
	if(ptrTofirstlink)
		newlist->ptrTofirstlink=ptrTofirstlink->duplicate();
	return newlist;
}
//----------------------------------------------------------------------------------------------表类
#endif