101012.cpp

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

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

//////////////////////////////////////////////////////////////
//9.1.3集合的简单表示法---1----用位向量实现集合
//////////////////////////////////////////////////////////////
template<class T>
class BitSet
{
	public:
		BitSet(int setsize);
		BitSet(const BitSet<T>&x);
		~BitSet(void);
		BitSet<T>&operator=(const BitSet<T>&x);
		int Member(const T&x);
		int operator==(const BitSet<T>&x)const;
		BitSet operator+(const BitSet<T>&x)const;
		BitSet operator*(const BitSet<T>&x)const;
		BitSet operator-(const BitSet<T>&x)const;
		void Insert(const T&x);
		void Delete(const T&x);
		friend istream & operator>>(istream & istr,BitSet<T> & x);
		friend ostream & operator<<(ostream & ostr,const BitSet<T> & x);
	private:
		int setsize;
		int arraysize;
		unsigned short *v;
		int ArrayIndex(const T & x) const;
		unsigned short BitMask(const T & x)const;
};

template<class T>
BitSet<T>::BitSet(int sz):setsize(sz)
{
	arraysize=(setsize+15)>>4;
	v=new unsigned short[arraysize];
	if(v==NULL) throw OutOfMemory();
	for(int i=0;i<arraysize;i++) v[i]=0;
}
template<class T>
BitSet<T>::BitSet(const BitSet<T>&x)
{
	setsize=x.setsize;
	arraysize=x.arraysize;
	v=new unsigned short[arraysize];
	if(v==NULL) throw OutOfMemory();
	for(int i=0;i<arraysize;i++) v[i]=x.v[i];
}
template<class T>
BitSet<T>::~BitSet(void)
{
	delete [] v;
}
template<class T>
BitSet<T> & BitSet<T>::operator=(const BitSet<T>&x)
{
	if(setsize!=x.setsize) throw BadInput();
	for(int i=0;i<arraysize;i++) v[i]=x.v[i];
	return *this;
}
template<class T>
int BitSet<T>::Member(const T&x)
{
	if(int(x)<0||int(x)>=setsize) throw BadInput();
	return v[ArrayIndex(x)] & BitMask(x);
}
template<class T>
int BitSet<T>::ArrayIndex(const T & x) const
{
	return int(x)>>4;
}
template<class T>
unsigned short BitSet<T>::BitMask(const T & x)const
{
	return 1<<(int(x)&15);
}
template<class T>
int BitSet<T>::operator==(const BitSet<T>&x)const
{
	int retval=1;
	if(setsize!=x.setsize) throw BadInput();
	for(int i=0;i<arraysize;i++)
		if(v[i]!=x.v[i])
		{
			retval=0;
			break;
		}
	return retval;
}
template<class T>
BitSet<T> BitSet<T>::operator+(const BitSet<T>&x)const
{
	if(setsize!=x.setsize) throw BadInput();
	BitSet<T> tmp(setsize);
	for(int i=0;i<arraysize;i++) tmp.v[i]=v[i]|x.v[i];
	return tmp;
}
template<class T>
BitSet<T> BitSet<T>::operator*(const BitSet<T>&x)const
{
	if(setsize!=x.setsize) throw BadInput();
	BitSet<T> tmp(setsize);
	for(int i=0;i<arraysize;i++) tmp.v[i]=v[i]&x.v[i];
	return tmp;
}
template<class T>
BitSet<T> BitSet<T>::operator-(const BitSet<T>&x)const
{
	if(setsize!=x.setsize) throw BadInput();
	BitSet<T> tmp(setsize);
	for(int i=0;i<arraysize;i++) tmp.v[i]=v[i]^(x.v[i]&v[i]);
	return tmp;
}
template<class T>
void BitSet<T>::Insert(const T&x)
{
	if(int(x)<0||int(x)>=setsize) throw BadInput();
	v[ArrayIndex(x)]|=BitMask(x);
}
template<class T>
void BitSet<T>::Delete(const T&x)
{
	if(int(x)<0||int(x)>=setsize) throw BadInput();
	v[ArrayIndex(x)]&=~BitMask(x);
}
//////////////////////////////////////////////////////////////
//9.1.3集合的简单表示法---2----用链表实现集合
//////////////////////////////////////////////////////////////


//////////////////////////////////////////////////////
//9.2.1实现字典的简单方法
//////////////////////////////////////////////////////
template<class T>
class ADictionary
{
	public:
		ADictionary(int size);
		~ADictionary(void);
		int Member(const T&x);
		void Insert(const T&x);
		void Delete(const T&x);
	private:
		int arraysize;
		int last;
		T *data;
};
template<class T>
ADictionary<T>::ADictionary(int size):arraysize(size)
{
	data=new T[arraysize];
	last=0;
}
template<class T>
ADictionary<T>::~ADictionary(void)
{
	delet [] data;
}
template<class T>
int ADictionary<T>::Member(const T&x)
{
	for(int i=0;i<last;i++)
		if(data[i]==x) return 1;
	return 0;
}
template<class T>
void ADictionary<T>::Insert(const T&x)
{
	if(!Member(x)&&last<arraysize) data[last++]=x;
}
template<class T>
void ADictionary<T>::Delete(const T&x)
{
	if(last>0)
	{
		int i=0;
		while(data[i]!=x&&i<last)i++;
		if(i<last&&data[i]==x) data[i]=data[--last];
	}
}
//////////////////////////////////////////////////////
//9.2.2用散列表实现字典-----1----开散列
//////////////////////////////////////////////////////
int hash1(char* x)
{
	int len=strlen(x),hashval=0;
	for(int i=0;i<len;i++)
		hashval+=x[i];
	return hashval%101;
}
template<class T>
class OpenHashTable
{
	public:
		OpenHashTable(int nbuckets,int hashf(T x));
		~OpenHashTable() {Clear();}
		bool Member(const T&x) const;
		OpenHashTable<T> & Insert(const T&x);
		OpenHashTable<T> & Delete(const T&x);
	private:
		void Clear();
		int size;
		int (*hf)(T x);
		List<T> *ht;
}
template<class T>
OpenHashTable<T>::OpenHashTable(int nbuckets,int hashf(T x)):
		size(nbuckets),hf(hashf),ht(new List<T>[size])
{}

template<class T>
void OpenHashTable<T>::Clear()
{
	for(int i=0;i<size;i++)
		ht[i].ClearList();
}
template<class T>
bool OpenHashTable<T>::Member(const T&x) const
{
	int i=int(hf(x)%size);
	return (ht[i].Locate(x)>0);
}
template<class T>
OpenHashTable<T> & OpenHashTable<T>::Insert(const T&x)
{
	if(Member(x)) throw BadInput();
	int i=int(hf(x)%size);
	ht[i]=ht[i].Insert(0,x);
	return *this;
}
template<class T>
OpenHashTable<T> & OpenHashTable<T>::Delete(const T&x)
{
	T y;
	int i=int(hf(x)%size);
	if(int k=ht[i].Locate(x)) ht[i]=ht[i].Delete(k,y);
	return *this;
}
//////////////////////////////////////////////////////
//9.2.2用散列表实现字典----2----闭散列
//////////////////////////////////////////////////////
template<class T>
class HashTable
{
	public:
		HashTable(int divisor,int hashf(T x));
		~HashTable() {delete [] ht;delete [] state;}
		bool Member(const T&x) const;
		HashTable<T> & Insert(const T&x);
		HashTable<T> & Delete(const T&x);
		HashTable<T> & Delete1(const T&x);
	private:
		int FindMatch(const T&x)const;
		int Unoccupied(const T&x)const;
		int (*hf)(T x);
		int c(int i)const;
		int size;
		T *ht;
		int *state;
}
template<class T>
HashTable<T>::HashTable(int divisor,int hashf(T x)):size(divisor),hf(hashf)
{
	ht=new T[size];
	state=new int [size];
	for(int i=0;i<size;i++)
		state[i]=1;
}
template<class T>
int HashTable<T>::FindMatch(const T&x)const
{
	int j=hf(x);
	for(int i=0;i<size;i++)
	{
		int k=(j+c(i))%size;
		if(state[k]==1)break;
		if(!state[k]&&ht[k]==x) return k;
	}
	return size;
}
template<class T>
int HashTable<T>::c(int i)const
{
	return i;
}
template<class T>
int HashTable<T>::Unoccupied(const T&x)const
{
	int j=hf(x);
	for(int i=0;i<size;i++)
	{
		int k=(j+c(i))%size;
		if(state[k]) return k;
	}
	return size;
}
template<class T>
bool HashTable<T>::Member(const T&x) const
{
	int i=FindMatch(x);
	if(i<size&&ht[i]==x) return true;
	return false;
}
template<class T>
HashTable<T> & HashTable<T>::Insert(const T&x)
{
	if(Member(x)) throw BadInput();
	int i=Unoccupied(x);
	if(i<size){
		state[i]=0;
		ht[i]=x;
		return *this;
	}
	throw NoMem();
}
template<class T>
HashTable<T> & HashTable<T>::Delete(const T&x)
{
	int i=FindMatch(x);
	if(i<size&&ht[i]==x)
		state[i]=2;
	return *this;
}
template<class T>
HashTable<T> & HashTable<T>::Delete1(const T&x)
{
	int i=FindMatch(x);
	if(i<size&&ht[i]==x)
	{
		for(;;)
		{
			state[i]=1;
			int j;
			for(j=(i+1)%size;!size[j];j=(j+1)%size)
			{
				int h=hf(ht[j]);
				if((h<=i&&i<j)||(i<j&&j<h)||(j<h&&h<=i)) break;
			}
			if(state[j]) break;
			ht[i]=ht[j];
			state[i]=state[j];
			i=j;
		}
	}
	return *this;
}