今天,我们讨论常用的和使用的算法.
有些查找算法,在实际应用中并不是经常用的(至少我在做开发时没用过,比如:分快查找),所以我就列出两个算法,循序查找和二分查找.当然了,这里还有一些编程思想和编程方法.仔细体会哦!呵呵.
好了,看代码吧:
#ifndef _SEARCH_H_
#define _SEARCH_H_
#ifndef MAX_SIZE
#define MAX_SIZE 256
#endif//MAX_SIZE
/*----------------------------------*/
要实现查找，被查找的元素最少要支持匹
配功能。即可以比较
/*----------------------------------*/
template <typename T,typename K>
class CSList;
template <typename T,typename K>
struct Elem
{
friend class CSList<T,K>;
private:
K key;
T elem;
public:
Elem(){};
Elem( T e ,K k ):elem(e),key(k){};
bool operator == ( const Elem<T,K> & e )
{
return key == e.key;
}
bool operator < ( const Elem<T,K> & e )
{
return key < e.key;
}
bool operator > ( const Elem<T,K> & e )
{
return key > e.key;
}
bool operator <= ( const Elem<T,K> & e )
{
return key <= e.key;
}
bool operator >= ( const Elem<T,K> & e )
{
return key >= e.key;
}
bool operator != ( const Elem<T,K> & e )
{
return key != e.key;
}
};
/*----------------------------------*/
声明：
1、这里只是实现查找算法
2、为了一致，我们将顺序表设置为基
于1的索引，因为0号索引内部使用
/*----------------------------------*/
template <typename T,typename K>
class CSList
{
private:
Elem<T,K> m_Elem[MAX_SIZE];
int m_nIndex;
public:
CSList():m_nIndex(1){};
/*----------------------------------*/
各种查找算法的实现,失败返回0
/*----------------------------------*/
int SSearch ( const Elem<T,K> & e ); //顺序查找
int BinSearch ( const Elem<T,K> & e ); //二分查找,用于有序表中的查找
/*----------------------------------*/
运算符重载
/*----------------------------------*/
void operator += ( const Elem<T,K> & e );
Elem<T,K> & operator [] ( const int i );
};
template <typename T,typename K>
Elem<T,K> & CSList<T,K>::operator [] ( const int i )
{
return (Elem<T,K> &)m_Elem[i + 1];
}
template <typename T,typename K>
void CSList<T,K>::operator += ( const Elem<T,K> & e)
{
m_Elem[m_nIndex++] = e;
}
template <typename T,typename K>
int CSList<T,K>::SSearch( const Elem<T,K> & e )
{
int i = m_nIndex;
m_Elem[0] = e;
while( m_Elem[i] != e ) i--;
return i;
}
template <typename T,typename K>
int CSList<T,K>::BinSearch( const Elem<T,K> & e )
{
int low = 0,high = m_nIndex;
int mid;
m_Elem[0] = e;
do
{
mid = ( low + high ) / 2;
if ( m_Elem[mid] == e )
return mid;
if ( m_Elem[mid] > e )
high = mid - 1;
else
low = mid + 1;
}while ( true );
return mid;
}
#endif//_SEARCH_H_
还行吧.呵呵,有问题要说哦,大家讨论啊.对了,树的操作,我们以后讨论吧.在那里你会发现一些经典的编程方法的.呵呵.