000000.cpp

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

////////////////////////////////////////////
o(Num) o(1) o(1)
////////////////////////////////////////////
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

template <class T>
class SNode
{
	friend Space<T>;
	friend List<T>;
	private:
		T data;
		int next;
};

template <class T>
class Space
{
	friend List<T>;
	public:
		Space(int Max=10000);
		~Space(){delete [] node}
		int Allocate();//分配一个数组单元
		viod Deallocate(int &i);//释放数组单元
	private:
		int Num,first;
		SNode<T> *node;//可用数组
};



template <class T>
Space<T>::Space(int Max)
{//构造函数
	Num=Max;
	node=new SNode<T>[Num];
	//初始化可用数组空间链
	for(int i=0;i<Num-1;i++)
		node[i].next=i+1;
	//可用数组空间链的最后一个结点
	node[Num-1].next=-1;
	//可用数组空间链的第一个可分配结点
	first=0;
}


template <class T>
int Space<T>::Allocate()
{
	if(first==-1) out<<"it is wrong";
	int i=first;
	first=node[i].next;
	return i;
}


template <class T>
viod Space<T>::Deallocate(int &i)
{
	node[i].next=first;
	first=i;
	i=-1;
}

//////////////////////////////////////////////
o(1) o(1)
//////////////////////////////////////////////
#include<iostream>
#include<fstream>
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");

template <class T>
class SNode
{
	friend Space<T>;
	friend List<T>;
	private:
		T data;
		int next;
};

template <class T>
class Space
{
	public:
		Space(int Max=10000);
		~Space(){delete [] node}
		int Allocate();//分配一个数组单元
		viod Deallocate(int &i);//释放数组单元
		int Num,first 1,first 2;
		SNode<T> *node;//可用数组
};

template <class T>
Space<T>::Space(int Max)
{
	Num=Max;
	node=new SNode<T>[Num];
	first 1=0;
	first 2=-1;
}


template <class T>
int Space<T>::Allocate()
{
	if(first 2==-1) 
	{
		if(first 1==Num) out<<"it is wrong";
		return first 1++;
	}
	int i=first 2;
	first 2=node[i].next;
	return i;
}


template <class T>
viod Space<T>::Deallocate(int &i)
{
	node[i].next=first 2;
	first 2=i;
	i=-1;
}


///////////////////////////////////////////////////
用游标实现的表模板类
///////////////////////////////////////////////////
template <class T>
class List
{
	public:
		List() {first=-1;}
		~List();
		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 PrintList(ostream& out) const;
	private:
		int first;//表首结点游标
		static Space<T> S;
};

template <class T>
List<T>::~List()
{
	int next;
	while(first!=-1)
	{
		next=S.node[first].next;
		S.Deallocate(first);
		first=next;
	}
}


template <class T>
int List<T>::Length() const 
{
	int current=first,
		len=0;
	while(current!=-1)
	{
		current=S.node[current].next;
		len++;
	}
	return len;
}

template <class T>
bool List<T>::Retrieve(int k,T& x) const
{
	if(k<1) return false;
	int current=first,
		index=1;
	while(index<k&&current !=-1)
	{
		current=S.node[current].next;
		index++;
	}
	if(current!=-1)
	{
		x=S.node[current].data;
		return true;
	}
	return false;
}