|
|
 #pragma once
  /**//*
 --- 顺序查找 ---
按数组从头开始一一查找。
 */
int SequenceSearch(int nArray[], int nLength, int nValue)
 {
for (int n = 0; n < nLength; ++n)
  {
if (nArray[n] == nValue)
{
return n;
 }
}
return -1;
}
/**//*
--- 折半查找 ---
1、确定数组的折半中点，对数组折半；
2、比较查找的数据a与中点数据b的大小关系，若a<b则对数组的后半部分重复步骤1，若a>b则对数组的前半部分重复步骤1，直到数组元素为1；
3、判断该元素是否为要找的元素。
*/
int HalfSearch(int nArray[], int nLow, int nHigh, int nValue)
{
int nIndex = -1;
if (nLow < nHigh)
{
int nMid = (nLow + nHigh) / 2;
if (nArray[nMid] > nValue)
{
nIndex = HalfSearch(nArray, 0, nMid - 1, nValue);
}
else if (nArray[nMid] < nValue)
{
nIndex = HalfSearch(nArray, nMid + 1, nHigh, nValue);
}
else if (nArray[nMid] == nValue)
{
nIndex = nMid;
}
}
return nIndex;
}
/**//*
--- 哈希查找 ---
1、确定哈希的key与value的关系，及冲突的解决方案；
2、将数据插入到哈希数组；
3、根据value结合冲突解决方案查找key。
*/
void InsertHash(int nArray[], int nValue, int nHashBase)
{
int nKey = nValue % nHashBase;
while(nArray[nKey] != 0)
{
nKey = (++nKey) % nHashBase;
}
nArray[nKey] = nValue;
}
int SearchHash(int nArray[], int nValue, int nHashBase)
{
int nKey = nValue % nHashBase;
while(nArray[nKey] != 0 && nArray[nKey] != nValue)
{
nKey = (++nKey) % nHashBase;
}
return (nArray[nKey] == nValue ? nKey : -1);
}
void Test_HashSearch()
{
int nArray[5] = {0};
InsertHash(nArray, 2, 5);
InsertHash(nArray, 3, 5);
InsertHash(nArray, 7, 5);
InsertHash(nArray, 1, 5);
InsertHash(nArray, 4, 5);
int nKey = SearchHash(nArray, 2, 5);
std::cout << "find 2: key = " << nKey << ",actual: " << nArray[nKey] << std::endl;
nKey = SearchHash(nArray, 3, 5);
std::cout << "find 3: key = " << nKey << ",actual: " << nArray[nKey] << std::endl;
nKey = SearchHash(nArray, 7, 5);
std::cout << "find 7: key = " << nKey << ",actual: " << nArray[nKey] << std::endl;
nKey = SearchHash(nArray, 1, 5);
std::cout << "find 1: key = " << nKey << ",actual: " << nArray[nKey] << std::endl;
nKey = SearchHash(nArray, 4, 5);
std::cout << "find 4: key = " << nKey << ",actual: " << nArray[nKey] << std::endl;
}
/**//*
--- 索引查找 ---
1、确定关键字key的计算方案，将索引划分区域，确定每个区域的起始地址，区域的容量；
2、根据1，将数据插入到数组对应的区域；
3、查找数据，根据1找到对应的区域，在该区域中顺序查找。
*/
struct tagIndex
{
tagIndex(int nIndex, int nStart):m_nIndex(nIndex),m_nStart(nStart),m_nLength(0){}
int m_nIndex;
int m_nStart;
int m_nLength;
};
tagIndex* Indexs[3] = {new tagIndex(0,0), new tagIndex(1,10), new tagIndex(2,20)};
void InsertIndex(int nArray[], int nValue)
{
int nIndex = nValue / 10;
int nArrayIndex = Indexs[nIndex]->m_nStart + Indexs[nIndex]->m_nLength;
nArray[nArrayIndex] = nValue;
++Indexs[nIndex]->m_nLength;
}
int IndexSearch(int nArray[], int nValue)
{
int nIndex = nValue / 10;
for (int n = Indexs[nIndex]->m_nStart; n < Indexs[nIndex]->m_nStart + Indexs[nIndex]->m_nLength; ++n)
{
if (nArray[n] == nValue)
{
return n;
}
}
return -1;
}
void Test_InsertSearch()
{
int nArray[30] = {0};
InsertIndex(nArray, 8);
InsertIndex(nArray, 18);
InsertIndex(nArray, 28);
InsertIndex(nArray, 12);
int nIndex = IndexSearch(nArray, 8);
std::cout << "find 8: Index = " << nIndex << ", actual = " << nArray[nIndex] << std::endl;
nIndex = IndexSearch(nArray, 18);
std::cout << "find 18: Index = " << nIndex << ", actual = " << nArray[nIndex] << std::endl;
nIndex = IndexSearch(nArray, 28);
std::cout << "find 28: Index = " << nIndex << ", actual = " << nArray[nIndex] << std::endl;
nIndex = IndexSearch(nArray, 12);
std::cout << "find 12: Index = " << nIndex << ", actual = " << nArray[nIndex] << std::endl;
}
void Test_Search()
{
int nArray[5] = {0,1,2,3,5};
int nIndex = SequenceSearch(nArray, 5, 5);
std::cout << "SequenceSearch find 5: index = " << nIndex << ", actual = " << nArray[nIndex] << std::endl;
nIndex = HalfSearch(nArray, 0, 4, 4);
std::cout << "HalfSearch find 4: index = " << nIndex << ", actual = " << nArray[nIndex] << std::endl;
//Test_HashSearch();
//Test_InsertSearch();
}
|