storedset.cpp

本程序用VC++完成 定义类模板SortedSet （包括方法的实现）

// StoredSet.cpp: implementation of the StoredSet class.
//
//////////////////////////////////////////////////////////////////////

#include "StoredSet.h"
#include <stdio.h>
#include <stdlib.h>
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
template StoredSet<int>;
template <class Type> StoredSet<Type>::StoredSet()
{

}

template <class Type> StoredSet<Type>::~StoredSet()
{
	mpComp = NULL;
	mnSize = 0;
	mnCount = 0;
	delete []mpElem;
}

template <class Type> 
StoredSet<Type>::StoredSet(int (*pCompare) (const Type& t1,const Type& t2), int nDefaultSize = DefaultNum)
{
	mnCount = 0;
	mpComp = pCompare;
	mnSize = nDefaultSize;
	mpElem = new Type[mnSize];
}

template <class Type> int StoredSet<Type>::Insert(const Type& t1)
{
	int nPos = mnCount-1;
	for( int i =mnCount-1;i>=0;i--)  //get pos of the greatest elem which is smaller than t1 
	{
		int nComp = (*mpComp)(mpElem[i],t1);
		if(nComp == 0 ) return -1;  //found elem equal to t1
		if (nComp < 0) break;    //found the first elem smaller than t1
	}
	if( mnSize == mnCount )      //overflow,exit program
	{
		printf("Overflow!\n");
		exit(-1);
	}
	nPos = i;
	for(i = mnCount-1; i>nPos;i--)
	{
		mpElem[i+1] = mpElem[i];
	}
	mpElem[nPos+1]=t1;
	mnCount++;
	return 0;
}

template <class Type> int StoredSet<Type>::Get(const Type& t1)
{
	for( int i =mnCount-1;i>=0;i--)  //get pos of the greatest elem which is smaller than t1 
	{
		int nComp = (*mpComp)(mpElem[i],t1);
		if(nComp <= 0 ) break;
	}
	if(i<mnCount-1)
		return i+1;
	else return -1;
}

template <class Type> int StoredSet<Type>::Del(const Type& t1)
{
	for( int i =mnCount-1;i>=0;i--)  //get pos of the elem which equals t1 
	{
		int nComp = (*mpComp)(mpElem[i],t1);
		if(nComp == 0 ) break;
	}
	if(i<0) return -1;
	for(; i<=mnCount-1;i++)
	{
		mpElem[i] = mpElem[i+1];
	}
	mnCount--;
	return 0;
}

template <class Type> int StoredSet<Type>::GetCount()
{
	return mnCount;
}