|
|
 #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();
}
|