比较数据排序前后的查找次数

比较数据排序前后的查找次数
作者:宋科
作者主页:kesongemini.diy.163.com

下载本文源代码

题目：
随机产生 1000 个 1-2000 以内的互不相同的整数，
1）存储于一个数组中（不排序）
2）存储于一个数组中（排序）
分别应用查找运算，要求输入一个查找元素，输出各自的查找比较次数。

要求：
1）查找元素 2
2）查找元素 1000


目的：
练习一下C++的神仙眷侣所提倡的用“类”来表达观点的编程风格。

用类来思考：

查找（CFind）是一个概念，作用于特定的数据（CData），因为数据有各种不同的特性，有排序了的（CDataSorted），和没有排序过的（CDataChaos），对于不同特性的数据，应该应用不同的查找方法， 对于排序过的数据(CDataSorted)，应该使用一种查找方法（CFindBinarySearch）， 对于没有排序过的数据(CDataChaos)，应该使用另一种查找方法（CFindWorker）， 呵呵，所以产生了如下的类图:

            +----------+                             +-------+
            +  CFind   +<>-------------------------->+ CData +
            +-+------+-+                             +---+---+
              ^      ^                                   ^
              ^      ^                          +--------+------+
              ^      ^                          ^               ^
  +-----------+-+  +-+-----------------+  +-----+-------+   +---+--------+     
  + CFindWorker +  + CFindBinarySearch +  + CDataSorted +   + CDataChaos +     
  +-------------+  +-------------------+  +-------------+   +------------+

数据的基类：(每个类的实现请在本文提供的源代码中查找)

class CData
{
public:
	CData();
	CData(int iNum, int iMax); // generate the data : _v
	virtual ~CData(){};

	CData(const CData& rhs);
	void get_data(vector& v);

protected:
	vector _v;

private:
	CData& operator=(const CData& rhs);
	const int _iMin;
};

排序数据类：

class CDataSorted : public CData
{
public:
	CDataSorted(CData rhs);
	virtual ~CDataSorted(){};

private:
	CDataSorted();
	CDataSorted& operator=(const CDataSorted& rhs);
};

原始数据类：

class CDataChaos : public CData
{
public:
	CDataChaos(CData rhs);
	virtual ~CDataChaos(){};

private:
	CDataChaos();
	CDataChaos& operator=(const CDataChaos& rhs);
};

查找的基类：

class CFind
{
public:
	CFind(const CData& data);
	virtual ~CFind();
	virtual bool to_find(int elem, int& num);

protected:
	CData* _pdata;

private:
	CFind& operator=(const CFind& rhs);
	CFind();
};

常规查找类：

class CFindWorker : public CFind
{
public:
	CFindWorker(const CData& data);
	virtual ~CFindWorker(){};

	virtual bool to_find(int elem, int& num);

private:
	CFindWorker();
};

二分查找类：

class CFindBinarySearch : public CFind
{
public:
	CFindBinarySearch(const CData& data);
	virtual ~CFindBinarySearch(){};

	virtual bool to_find(int elem, int& num);

private:
	CFindBinarySearch(); // BINARY SEARCH
};

全局方法：

void g_find(CFind* pFind, int elem)
{
	int num = 0;

	if ( pFind->to_find(elem, num) ) 
	{
		cout << "\tfound " << elem
			<< " by " << num << " times."
			<< endl;
	}
	else
	{
		cout << "\tNOT found " << elem
			<< " by " << num << " times!"
			<< endl;
	}
	cout << endl;
}

void g_answer(CData* pData, int elem)
{
	// VC++6 IDE -- add "/GR" to settings
	if ( dynamic_cast<CDataSorted*>(pData) )
	{
		CFindBinarySearch* pBin = new CFindBinarySearch(*pData);
		g_find(pBin, elem);
		delete pBin;
	}
	else
	{
		CFindWorker* pWorker = new CFindWorker(*pData);
		g_find(pWorker, elem);
		delete pWorker;
	}
}

使用方法：

CData* pData = new CData(1000, 2000);
CDataChaos* pDataChaos = new CDataChaos(*pData);
CDataSorted* pDataSorted = new CDataSorted(*pData);

cout << "/- SORTED DATA -/";
g_answer( pDataSorted, 2);

cout << "/- CHAOS DATA -/";
g_answer( pDataChaos, 2);

cout << "/- SORTED DATA -/";
g_answer( pDataSorted, 1000);

cout << "/- CHAOS DATA -/";
g_answer( pDataChaos, 1000);

delete pDataSorted;
delete pDataChaos;
delete pData;

可能的执行结果：