ID #5738

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

题目:

随机产生 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的了,自己写宏么?太麻烦了,要是您有什么好办法的话,请一定写信告诉我呀。: )

本文配套源码


2011-07-01 18:29
阅读:
I'm VC , Just U know Y
本站部分文章来源于互联网,版权归原作者所有。

延伸阅读:

根据前序和中序序列生成二叉树

几个数字信号处理算法程序

用C语言描述数据结构

常用分词算法的比较与设想

采用部分快速排序算法实现数组的部分排序