0001 /****************************************************************************************** 0002 * Test of list 0003 ******************************************************************************************/ 0004 #include "list_test.h" 0005 0006 int testID = 0; //测试编号 0007 0008 /****************************************************************************************** 0009 * 随机生成长度为n的列表(其中可能包含重复节点) 0010 ******************************************************************************************/ 0011 template <typename T> //元素类型 0012 void randomList ( List<T> & list, int n ) { //创建长度为n的列表,其元素随机取自[0, 4n) 0013 ListNodePosi<T> p = 0014 ( rand() % 2 ) 0015 ? list.insertAsLast ( rand() % ( T ) ( n * 4 ) ) 0016 : list.insertAsFirst ( rand() % ( T ) ( n * 4 ) ); 0017 for ( int i = 1; i < n; i++ ) 0018 p = rand() % 2 0019 ? list.insert ( rand() % ( T ) ( n * 4 ), p ) 0020 : list.insert ( p, rand() % ( T ) ( n * 4 ) ); 0021 } 0022 0023 /****************************************************************************************** 0024 * 测试列表 0025 ******************************************************************************************/ 0026 #define PRINT(x) { print(x); crc(x); checkOrder(x); } 0027 template <typename T> //元素类型 0028 void testList ( int testSize ) { 0029 printf("\n ==== Test %2d. Generate a random list with %d elements\n", testID++, testSize); 0030 List<T> L; randomList(L, testSize); PRINT(L); 0031 printf("\n ==== Test %2d. Sort it\n", testID++); 0032 L.sort(); PRINT(L); 0033 0034 printf("\n ==== Test %2d. Generate two sorted lists each with %d random elements\n", testID++, testSize); 0035 List<T> Lx; randomList(Lx, testSize); PRINT(Lx); Lx.sort(); PRINT(Lx); 0036 List<T> Ly; randomList(Ly, testSize); PRINT(Ly); Ly.sort(); PRINT(Ly); 0037 0038 printf("\n ==== Test %2d. Merge them into a single sorted list\n", testID++); 0039 Lx.merge(Ly); PRINT(Lx); PRINT(Ly); 0040 // 0041 printf ( "\n ==== Test %2d. Generate two lists each of size %d by random insertions\n", testID++, testSize ); 0042 List<T> La; randomList ( La, testSize ); PRINT ( La ); 0043 List<T> Lb; randomList ( Lb, testSize ); PRINT ( Lb ); 0044 // 0045 printf ( "\n ==== Test %2d. Call list members by rank (with high complexity)\n", testID++ ); 0046 for ( int i = 0; i < La.size(); i++ ) print ( La[i] ); printf ( "\n" ); 0047 for ( int i = 0; i < Lb.size(); i++ ) print ( Lb[i] ); printf ( "\n" ); 0048 printf ( "\n ==== Test %2d. Concatenation\n", testID++ ); PRINT ( La ); PRINT ( Lb ); 0049 while ( 0 < Lb.size() ) La.insertAsLast ( Lb.remove ( Lb.first() ) ); PRINT ( La ); PRINT ( Lb ); 0050 printf ( "\n ==== Test %2d. Increase\n", testID++ ); PRINT ( La ); 0051 increase ( La ); PRINT ( La ); 0052 printf ( "\n ==== Test %2d. Lowpass (with high complexity) on\n", testID++ ); PRINT ( La ); 0053 int i = La.size(); while ( 0 < --i ) { La[i-1] += La[i]; La[i-1] >>= 1; } PRINT ( La ); 0054 printf ( "\n ==== Test %2d. reverse\n", testID++ ); 0055 La.reverse(); PRINT ( La ); 0056 int r = dice( La.size() ); int n = dice( La.size() - r ); 0057 printf ( "\n ==== Test %2d. Copy [%d, %d)\n", testID++, r, r+n ); PRINT ( La ); 0058 List<T> Ld ( La, r, n ); PRINT ( Ld ); 0059 printf ( "\n ==== Test %2d. Copy\n", testID++ ); PRINT ( La ); 0060 List<T> Le ( La ); PRINT ( Le ); 0061 printf ( "\n ==== Test %2d. Trim by random deletions\n", testID++ ); PRINT ( Ld ); 0062 while ( testSize / 4 < Ld.size() ) { 0063 int N = rand() % Ld.size(); printf ( "removing L[%d]=", N ); 0064 ListNodePosi<T> p = Ld.first(); while ( 0 < N-- ) p = p->succ; 0065 print ( p->data ); printf ( " ...\n" ); 0066 Ld.remove ( p ); PRINT ( Ld ); 0067 } 0068 printf ( "\n ==== Test %2d. Copy\n", testID++ ); PRINT ( La ); 0069 List<T> Lf ( La ); PRINT ( Lf ); 0070 printf ( "\n ==== Test %2d. FIND in\n", testID++ ); PRINT ( Lf ); 0071 for ( int i = 0; i <= testSize * 2; i++ ) { //逐一测试[0, 2n]中的所有可能 0072 ListNodePosi<T> p = Lf.find ( ( T ) i ); printf ( "Looking for " ); print ( ( T ) i ); printf ( ": " ); 0073 if ( p ) { printf ( " found with" ); print ( p->data ); } 0074 else printf ( " not found" ); 0075 printf ( "\n" ); 0076 } //正确的结构应该是大致(n+1次)失败、(n次)成功相间 0077 printf ( "\n ==== Test %2d. Sort\n", testID++ ); PRINT ( La ); 0078 La.sort(); PRINT ( La ); 0079 printf ( "\n ==== Test %2d. SEARCH in\n", testID++ ); PRINT ( La ); 0080 for ( int i = 0; i <= testSize * 2; i++ ) { //逐一测试[0, 2n]中的所有可能 0081 ListNodePosi<T> p = La.search ( ( T ) i ); printf ( "Looking for " ); print ( ( T ) i ); printf ( ": " ); 0082 printf ( " stopped at" ); print ( p->data ); 0083 if ( ( T ) i == p->data ) printf ( " and found" ); 0084 printf ( "\n" ); 0085 } //正确的结构应该是大致(n+1次)失败、(n次)成功相间 0086 printf ( "\n ==== Test %2d. Remove redundancy in\n", testID++ ); PRINT ( La ); 0087 printf ( "%d node(s) removed\n", La.uniquify() ); PRINT ( La ); La.reverse(); PRINT ( La ); 0088 printf ( "\n ==== Test %2d. Remove redundancy in\n", testID++ ); PRINT ( Le ); 0089 printf ( "%d node(s) removed\n", Le.deduplicate() ); PRINT ( Le ); 0090 printf ( "\n ==== Test %2d. Sort\n", testID++ ); PRINT ( Le ); 0091 Le.sort(); PRINT ( Le ); 0092 return; 0093 } 0094 0095 /****************************************************************************************** 0096 * 测试列表 0097 ******************************************************************************************/ 0098 int main ( int argc, char* argv[] ) { 0099 if ( 2 > argc ) { printf ( "Usage: %s <size of test>\a\a\n", argv[0] ); return 1; } 0100 srand ( ( unsigned int ) time ( NULL ) ); 0101 testList<int> ( atoi ( argv[1] ) ); //元素类型可以在这里任意选择 0102 return 0; 0103 }