0001 /****************************************************************************************** 0002 * Test of Skiplist 0003 ******************************************************************************************/ 0004 0005 #include "skipList_test.h" 0006 0007 /****************************************************************************************** 0008 * 测试跳转表 0009 ******************************************************************************************/ 0010 template <typename K, typename V> //key、value 0011 void testSkiplist ( Rank n ) { 0012 Skiplist<K, V> L; 0013 while ( L.size() < n ) 0014 switch ( dice ( 3 ) ) { 0015 case 0: { //查找,成功率 <= 33.3% 0016 K key = dice ( ( K ) n * 3 ); //[0, 3n)范围内的key 0017 printf ( "Searching for " ); print ( key ); printf ( " ... " ); 0018 V* pValue = L.get ( key ); 0019 pValue ? printf ( "found with " ), print ( *pValue ) : printf ( "Not found" ); printf ( "\n\n" ); 0020 break; 0021 } 0022 case 1: { //删除,成功率 <= 33.3% 0023 K key = dice ( ( K ) n * 3 ); //[0, 3n)范围内的key 0024 printf ( "Removing " ); print ( key ); printf ( " ... " ); 0025 if ( L.remove ( key ) ) { printf ( "Done\n" ); print(L); } 0026 else printf ( "Entry not exists\n\n" ); 0027 break; 0028 } 0029 default: {//插入,成功率 == 100% 0030 K k = dice ( ( K ) n * 3 ); V v = ( V ) 'A' + dice ( 26 ); //在[0, 2n)*['A'~'Z']范围内的词条 0031 printf ( "Inserting <" ); print ( k ); printf ( "," ); print ( v ); printf ( "> ... " ); 0032 L.put ( k, v ); printf ( "Done\n" ); 0033 print ( L ); 0034 break; 0035 } 0036 } 0037 while ( L.size() > 0 ) { 0038 K key = dice ( ( K ) n * 3 ); //[0, 3n)范围内的key 0039 printf ( "Removing " ); print ( key ); printf ( " ... " ); 0040 L.remove ( key ) ? printf ( "Done\n" ) : printf ( "Entry not exists\n" ); 0041 print ( L ); printf("\n"); 0042 } 0043 } 0044 0045 /****************************************************************************************** 0046 * 主程序 0047 ******************************************************************************************/ 0048 int main ( int argc, char* argv[] ) { 0049 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0050 srand((unsigned int)time(NULL)); //随机种子 0051 //srand( 31415926 ); //固定种子(假种子,调试用) 0052 testSkiplist<int, char> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0053 return 0; 0054 }