1 #include <iostream>  2 #include <vector>  3 #include <string>  4 #include <cstdlib>  5 #include <ctime>  6   7 using namespace std;  8 typedef bool BOOL;  9 typedef unsigned long DWORD; 10 typedef unsigned char UINT8; 11 //typedef true TRUE; 12 //typedef false FALSE; 13 DWORD g_dwTotalTimes = 0; 14 DWORD g_dwCount = 0; 15 #define INIT_TL { g_dwTotalTimes = 0, g_dwCount = 0; } 16 #define CALL_COUNT(t) { g_dwTotalTimes += t,++ g_dwCount; } 17 #define AVERAGE ( (float)g_dwTotalTimes / g_dwCount ) 18  19 void RandString ( string & szRandString, unsigned int unAriseLength, unsigned int unMiniLength = 5 ); 20 //Data In Struct 21 typedef class A1 22 { 23 public: 24     string szSampleKey; 25     string szRealData; 26 }SampleData; 27  28 //Data Normal 29 typedef class A 30 { 31 #define MAX_SIZE_OF_DB (256) 32 #define MAX_ADDR_OF_DB (MAX_SIZE_OF_DB) 33  34 private: 35     vector<SampleData> Array; 36     vector<int> UsedFlagArray; 37     DWORD dwLeftDataSize; 38 private://function 39     DWORD GetAddrByKey ( string & KeyStr ); 40     BOOL SaveDataToDB ( SampleData & KeyToGet, DWORD dwAddr ); 41 public: 42     A(); 43     ~A(); 44     BOOL AddToArray( SampleData & sd ); 45     SampleData & FindInArray( string & Key ); 46 }NormalArray; 47  48 NormalArray::A() 49 { 50     INIT_TL; 51     UsedFlagArray.resize ( MAX_SIZE_OF_DB ); 52     Array.resize ( MAX_SIZE_OF_DB ); 53     dwLeftDataSize = MAX_SIZE_OF_DB; 54 } 55  56 NormalArray::~A() 57 { 58     ; 59 } 60  61 BOOL NormalArray::AddToArray ( SampleData & sd ) 62 { 63     if ( 0 == dwLeftDataSize ) 64     { 65         return false; 66     } 67     //根据Key值计算出地址信息 68     DWORD dwAddr = GetAddrByKey ( sd.szSampleKey ); 69     //根据地址信息将数据存放在数据库中 70     SaveDataToDB ( sd, dwAddr ); 71     return true; 72 } 73  74 DWORD NormalArray::GetAddrByKey ( string & KeyStr ) 75 { 76     DWORD dwSize = KeyStr.size (); 77     DWORD dwKeySum = 0; 78     while ( dwSize -- ) 79     { 80         dwKeySum += (UINT8)KeyStr[dwSize]; 81     } 82     //根据上限值计算出结果 83     return dwKeySum % ( MAX_ADDR_OF_DB ); 84 } 85  86 BOOL NormalArray::SaveDataToDB ( SampleData & KeyToGet, DWORD dwAddr ) 87 { 88     if ( 0 == dwLeftDataSize ) 89     { 90         return false; 91     } 92     while ( 0 != UsedFlagArray[dwAddr] ) 93     { 94         (++ dwAddr)  %= MAX_ADDR_OF_DB; 95     } 96     //在这个地址保存数据 97     Array[dwAddr].szSampleKey = KeyToGet.szSampleKey; 98     Array[dwAddr].szRealData =http://www.mamicode.com/ KeyToGet.szRealData; 99     //地址信息更新100     UsedFlagArray[dwAddr] = 1;101     -- dwLeftDataSize;102 103     return true;104 }105 106 SampleData & NormalArray::FindInArray( string & Key )107 {108     DWORD dwSearchTime = 1;109     DWORD dwAddr = GetAddrByKey (Key);110     while ( Array[dwAddr].szSampleKey != Key )111     {112         ++ dwSearchTime;113         (++ dwAddr) %= MAX_ADDR_OF_DB;114     }115     CALL_COUNT(dwSearchTime);116     cout << "Find " << Key << " With " << dwSearchTime << " Times.\n";117     return Array[dwAddr];118 }119 void InitialSampleData( vector<SampleData> & SampleDataList )120 {121     srand ( time ( NULL ) );122     unsigned int unListSize = SampleDataList.size();123     //Start124     for ( unsigned int unloop = 0; unloop < unListSize ;++ unloop )125     {126         RandString ( SampleDataList[unloop].szSampleKey, 3 );127         //what the Data is128         RandString ( SampleDataList[unloop].szRealData, 7 );129     }130 }131 132 void RandString ( string & szRandString, unsigned int unAriseLength, unsigned int unMiniLength )133 {134     const char cBaseVal = ‘a‘;135     char cIncreaseVal = 0;136     unsigned int bUpper = 0;137     unsigned int unLength = 0;138     //the length of string139     unLength = rand () % unAriseLength + unMiniLength;140     //init the Key size141     szRandString.resize( unLength + 1 );142     for ( unsigned int unWordLoop = 0; unWordLoop < unLength; ++ unWordLoop )143     {144         //0or1145         bUpper = rand () & 0x01;146         //what the Key is147         cIncreaseVal = rand () % 26;148         //Make It;149         char tmp = cBaseVal + cIncreaseVal;150         bUpper ? tmp -= 32 : tmp ;151         szRandString[unWordLoop] = tmp;152     }153     szRandString[unLength] = ‘\0‘;154 }155 156 void DspDataConsol ( const vector<SampleData> & SampleDataList )157 {158     unsigned int unListSize = SampleDataList.size();159     for ( unsigned int unLoop = 0; unLoop < unListSize; ++ unLoop )160     {161         cout << unLoop << endl;162         cout << SampleDataList[unLoop].szSampleKey << endl;163         cout << SampleDataList[unLoop].szRealData << endl;164     }165 }166 //Data Map167 168 169 int main ()170 {171     //初始化测试数据172     vector<SampleData> TestData;173     TestData.resize (128);174     InitialSampleData ( TestData );175     //DspDataConsol ( TestData );176     NormalArray Na;177     for ( DWORD dwLoop = 0; dwLoop < 128; ++ dwLoop )178     {179         Na.AddToArray ( TestData[dwLoop] );180     }181     for ( DWORD dwLoop = 0; dwLoop < 128; ++ dwLoop )182     {183         Na.FindInArray( TestData[dwLoop].szSampleKey );184     }185     cout << "平均查找时间：" << AVERAGE << endl;186     return 0;187 }