0001 #include "Splay_test.h" 0002 0003 template <typename T> void testSplayPeriod ( int n ) { //周期性访问测试 0004 Splay<T> splay; 0005 for ( int i = 0; i < n; i++ ) splay.insert ( ( T ) i ); print ( splay ); 0006 for ( int i = 0; i < n; i++ ) { splay.search ( ( T ) i ); print ( splay ); } 0007 } 0008 0009 template <typename T> void testSplayRandom ( int n ) { //随机访问测试 0010 Splay<T> splay; 0011 while ( splay.size() < n ) { 0012 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0013 switch ( dice ( 3 ) ) { 0014 case 0: { //查找,成功率 <= 33.3% 0015 printf ( "Searching for " ); print ( e ); printf ( " ...\n" ); 0016 splay.search ( e ) ? 0017 printf ( "Found with" ), print ( splay.root() ), printf ( "\n" ) : 0018 printf ( "Not found\n" ); 0019 break; 0020 } 0021 case 1: { //删除,成功率 <= 33.3% 0022 printf ( "Removing " ); print ( e ); printf ( " ...\n" ); 0023 splay.remove ( e ) ? 0024 printf ( "Removal done\n" ) : 0025 print ( e ), printf ( " not exists\n" ); 0026 break; 0027 } 0028 default: {//插入,成功率 == 100% 0029 printf ( "Inserting " ); print ( e ); printf ( " ...\n" ); 0030 splay.insert ( e ); 0031 ( e == splay.root()->data ) ? 0032 printf ( "Insertion done with" ), print ( splay.root() ), printf ( "\n" ) : 0033 print ( e ), "duplicated"; 0034 break; 0035 } 0036 } //switch 0037 print ( splay ); //无论调用哪个接口,Splay都会自我调整形态,故需统一输出 0038 } //while 0039 while ( splay.size() > 0 ) { 0040 T e = dice ( ( T ) n * 3 ); //[0, 3n)范围内的e 0041 printf ( "Removing " ); print ( e ); printf ( " ...\n" ); 0042 splay.remove ( e ) ? printf ( "Removal done\n" ), print ( splay ) : print ( e ), printf ( " not exists\n" ); 0043 } 0044 } //课后:利用这一接口,针对不同分布的访问,验证课上对Splay分摊分析的结论 0045 0046 int main ( int argc, char* argv[] ) { //测试主入口 0047 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0048 srand ( ( unsigned int ) time ( NULL ) ); 0049 testSplayRandom<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0050 testSplayPeriod<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0051 return 0; 0052 }