用指针实现表.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

template<class T>
class Node{
	friend List<T>;
	private:
		T data;
		Node<T> *next;
}
template<class T>
class List{
	private:
		Node<T> *first;
	public:
		List() {first=0;}
		~List();
		bool Empty() const {return first==0;}
		int Length() const;
		bool Retrieve(int k,T& x) const;
		int Locate(const T& x) const;
		List<T>&Insert(int k,const T& x);
		List<T>&Delete(int k,T& x);
	    void Output(ostream& out) const;
}
template<class T>
List<T>::~List()
{
	Node<T> *next;
	while(first){
		next=first->next;
		delete first;
		first=next;
	}
}
template<class T>
int List<T>::Length() cosnt
{
	Node<T> *current=first;
	int len=0;
	while(current){
		len++;
		current=current->next;
	}
	return len;
}
template<class T>
bool List<T>::Retrieve(int k,T& x) const
{
	if(k<1) return false;
	Node<T> *current=first;
	int index=1;
	while(index<k&&current)
	{
		current=current->next;
		index++;
	}
	if(current)
	{
		x=current->data;
		return true;
	}
	return false;
}
template<class T>
int List<T>::Locate(const T& x) const
{
	Node<T> *current=first;
	int index=1;
	while(current && current->data!=x)
	{
		current=current->next;
		index++;
	}
	if(current) return index;
	return 0;
}

template<class T>
List<T>&List<T>::Insert(int k,const T& x)
{
	Node<T> *p=first;
	for(int index=1;index<k && p;index++)
		p=p->next;
	Node<T> *y=new Node<T>;
	y->data=x;
	if(k)
	{
		y->next=p->next;
		p->next=y;
	}
	else
	{
		y->next=first;
		first=y;
	}
	return *this;
}
template<class T>
List<T>&List<T>::Delete(int k,T& x)
{
	Node<T> *p=first;
	if(k==1) first=first->next;
	else
	{
		Node<T> *q=first;
		for(int index=1;index<k-1 && q;index++)
			q=q->next;
		p=q->next;
		q->next=p->next;
	}
	x=p->data;
	delete p;
	return *this;
}
template<class T>
void List<T>::PrintList(ostream & out) const
{
	Node<T> *current;
	for(current=first;current;current=current->next)
		out<<current->data<<" ";
}