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

王朝vc·作者佚名  2006-01-17
窄屏简体版  字體: |||超大  

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

作者:宋科

作者主页: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 +

+-------------+ +-------------------+ +-------------+ +------------+

这样的话,用户就可以通过派生CData类来加入新的存储格式的数据,通过派生CFind类来加入新的查找方法了, 不过,一般来说,查找方法都是和数据存储方式紧密耦合的,所以,嘿嘿嘿,...,

请注意我的目的呀,我只是为了练习C++才这样写的,哈哈:) 我想一定会有很多人大骂我白痴的吧,哈哈哈哈~~哈哈哈哈,就当耳旁风,不听。:)

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

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;

可能的执行结果:

/- SORTED DATA -/ NOT found 2 by 10 times!

/- CHAOS DATA -/ NOT found 2 by 1000 times!

/- SORTED DATA -/ found 1000 by 10 times.

/- CHAOS DATA -/ found 1000 by 822 times.

BTW: 唉,最后还是使用了丑陋的dynamic_cast运算符,真是遗憾。我按照孟岩先生的一篇文章,在VC中装了STLport的版本,但是因为SGI-STL的map和微软的不同,不知道统一起来用,所以不得不暂时不用STLport的了,自己写宏么?太麻烦了,要是您有什么好办法的话,请一定写信告诉我呀。:

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航