020204.cpp

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

#include<iostream>
#include<fstream>
using namespace std;

template<class T>
class List
{
	public:
		List(int Max=10);
		~List();
		bool Empty() const { return n==0;}
		int Length() const { return n;}
		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 PrintList(ostream& out) const;
	private:
		T **table;//指向表中元素的指针数组
		int n,MaxSize;
};

template<class T>
List<T>::List(int Max)
{
	MaxSize=Max;
	table=new T*[MaxSize];
	n=0;
}

template<class T>
List<T>::~List()
{
	for(int i=0;i<n;i++)
		delete table[i];
	delete[] table;
}

template<class T>
bool List<T>::Retrieve(int k,T& x) const
{
	if(k<1||k>n) return false;
	x=*table[k-1];
	return true;
}

template<class T>
int List<T>::Locate(const T& x) const
{
	for(int i=0;i<n;i++)
		if(*table[i]==x) return ++i;
	return 0;
}

template<class T>
List<T>&List<T>::Insert(int k,const T& x)
{
	if(k<0||k>n) out<<"wrong";
	if(n==MaxSize) out<<"wrong";
	for(int i=n-1;i>=k;i--)
		table[i+1]=table[i];
	table[k]=new T;
	*table[k]=x;
	n++;
	return *this;
}

template<class T>
List<T>&List<T>::Delete(int k,T& x)
{
	if(Retrieve(k,x))
	{
		for(int i=k;i<n;i++)
			table[i-1]=table[i];
		n--;
		return *this;
	}
	else out<<"wrong";
}

template<class T>
void List<T>::PrintList(ostream& out) const
{
	for(int i=0;i<n;i++)
		out<<*table[i]<<" ";
}