Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1334074
  • 博文数量: 953
  • 博客积分: 52320
  • 博客等级: 大将
  • 技术积分: 13090
  • 用 户 组: 普通用户
  • 注册时间: 2008-08-05 13:42
文章分类

全部博文(953)

文章存档

2011年(1)

2008年(952)

我的朋友

分类: C/C++

2008-08-05 13:52:33

下载本文示例代码
下载本文源代码

题目:
随机产生 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(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的了,自己写宏么?太麻烦了,要是您有什么好办法的话,请一定写信告诉我呀。: ) 下载本文示例代码
阅读(104) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~