1. 将绝对路径转换成相对路径。例如， input: /home/news/../tmp/game/../; ouptut: /home/tmp/
思路：利用栈的思想。每次遇到".."时，将退栈至上一个'/'位置。
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 5 char *convert_path_opt( const char *path ) 6 { 7 char *result = NULL; 8 int top = 0; 9 int path_len = 0, 10 index = 0, 11 point_cnt = 0; 12 13 /**< check */ 14 if ( NULL == path ) 15 { 16 fprintf( stderr, "convert_path_opt: invalid argument. " ); 17 return NULL; 18 } 19 20 /**< allocate memory */ 21 path_len = strlen( path ); 22 result = (char *)malloc( path_len * sizeof(char) ); 23 if ( NULL == result ) 24 { 25 fprintf( stderr, "convert_path_opt: failed to malloc. " ); 26 return NULL; 27 } 28 29 /**< convert */ 30 while ( index < path_len ) 31 { 32 /**< copy characters before point. */ 33 while ( index < path_len && path[index] != '.' ) 34 { 35 result[top++] = path[index++]; 36 } 37 38 /**< counter point. */ 39 for ( point_cnt = 0; 40 index < path_len && path[index] == '.'; 41 ++point_cnt, ++index ); 42 43 if ( point_cnt == 2 ) 44 { 45 --top; 46 while ( --top > 0 && result[top] != '/' ); 47 ++top; 48 } 49 50 ++index; 51 } 52 53 result[top] = ' '; 54 55 return result; 56 } 57 58 int main() 59 { 60 char *path = "/home/news/./../tmp/game/../"; 61 char *result = NULL; 62 63 result = convert_path_opt( path ); 64 printf( " Result is %s. ", result ); 65 66 return 0; 67 }
2. 比较两个字符串的不同，返回不同点的位置（相对第二字符串而言）
1 #include <stdio.h> 2 3 char *compare_strings( const char *plhs, 4 const char *prhs ) 5 { 6 int lhs_index = 0, 7 rhs_index = 0; 8 9 /**< check argument. */ 10 if ( NULL == plhs || NULL == prhs ) 11 { 12 fprintf( stderr, "copmare_strings:invalid argument. " ); 13 return NULL; 14 } 15 16 /**< compare */ 17 while ( plhs[lhs_index] != ' ' 18 && prhs[rhs_index] != ' ' ) 19 { 20 if ( plhs[lhs_index] != prhs[rhs_index] ) 21 break; 22 ++lhs_index; 23 ++rhs_index; 24 } 25 26 return prhs + rhs_index; 27 } 28 29 int main() 30 { 31 char *plhs = "hello, world."; 32 char *prhs = "hello, world."; 33 char *pdiff = NULL; 34 35 pdiff = compare_strings( plhs, prhs ); 36 printf( " Difference is %s. ", pdiff ); 37 38 return 0; 39 }
3. 给定一个100亿的整数文件，输出前100个最小值。
思路：大数据+top k问题。参考博客：csdn上July_v博客（http://blog.csdn.net/v_july_v）
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 /**< max_heap */ 6 struct max_heap 7 { 8 int current_index; 9 int capacity; 10 int *elem; 11 }; 12 typedef struct max_heap max_heap; 13 14 /**< allocate max_heap */ 15 max_heap *alloc_max_heap( const int cap ) 16 { 17 max_heap *new_heap = NULL; 18 19 /**< check parameter */ 20 if ( cap <= 0 ) 21 { 22 fprintf( stderr, "alloc_max_heap: invalid parameter. " ); 23 return NULL; 24 } 25 26 /**< allocate memory */ 27 new_heap = (max_heap *) malloc( sizeof(max_heap) ); 28 if ( NULL == new_heap ) 29 { 30 fprintf( stderr, "alloc_max_heap: failed to malloc. " ); 31 return NULL; 32 } 33 34 new_heap->elem = (int *) calloc( cap, sizeof(int) ); 35 if ( NULL == new_heap->elem ) 36 { 37 fprintf( stderr, "alloc_max_heap: failed to calloc. " ); 38 free( new_heap ), new_heap = NULL; /**< free allocated memory. */ 39 return NULL; 40 } 41 42 /**< set other parameter. */ 43 new_heap->capacity = cap; 44 new_heap->current_index = 0; 45 46 return new_heap; 47 } 48 49 /**< destroy max_heap */ 50 void destroy_max_heap( max_heap **heap ) 51 { 52 if ( NULL != heap ) 53 { 54 if ( (*heap)->elem ) 55 { 56 free( (*heap)->elem ); 57 (*heap)->elem = NULL; 58 } 59 60 free( *heap ); 61 *heap = NULL; 62 } 63 } 64 65 /**< swap elements */ 66 void swap_int( int *number, int lhs, int rhs ) 67 { 68 int tmp = number[lhs]; 69 number[lhs] = number[rhs]; 70 number[rhs] = tmp; 71 } 72 73 /**< insert value */ 74 void push_value( max_heap *heap, const int value ) 75 { 76 int left_child = 0, 77 right_child = 0, 78 parent_index = 0; 79 80 /**< check argument */ 81 if ( NULL == heap ) 82 { 83 fprintf( stderr, "push_value: invalid parameter. " ); 84 return; 85 } 86 if ( heap->current_index == heap->capacity ) 87 { 88 fprintf( stderr, "push_value: this max_heap is full. " ); 89 return; 90 } 91 92 /**< push element */ 93 parent_index = heap->current_index; 94 heap->elem[heap->current_index++] = value; 95 96 while ( parent_index >= 0 ) 97 { 98 left_child = 2 * parent_index + 1; 99 right_child= 2 * parent_index + 2; 100 101 if ( left_child < heap->current_index 102 && heap->elem[left_child] > heap->elem[parent_index] ) 103 { 104 swap_int( heap->elem, left_child, parent_index ); 105 } 106 107 if ( right_child < heap->current_index 108 && heap->elem[right_child] > heap->elem[parent_index] ) 109 { 110 swap_int( heap->elem, right_child, parent_index ); 111 } 112 113 --parent_index; 114 } 115 } 116 117 /**< pop element */ 118 int pop_value( max_heap *heap ) 119 { 120 int ret = 0, 121 left_child = 0, 122 right_child = 0, 123 parent_index = 0, 124 swap_index = 0; 125 126 /**< check argument. */ 127 if ( NULL == heap ) 128 { 129 fprintf( stderr, "pop_value: invalid parameter. " ); 130 return -1; 131 } 132 if ( heap->current_index == 0 ) 133 { 134 fprintf( stderr, "pop_value: this max_heap is empty. " ); 135 return -1; 136 } 137 138 /**< pop element */ 139 --heap->current_index; 140 swap_int( heap->elem, 0, heap->current_index ); 141 ret = heap->elem[heap->current_index]; 142 parent_index = 0; 143 while ( parent_index < heap->current_index ) 144 { 145 left_child = 2 * parent_index + 1; 146 right_child= 2 * parent_index + 2; 147 148 /**< looking for maximum between left and right. */ 149 if ( left_child < heap->current_index 150 && right_child < heap->current_index ) 151 { 152 swap_index = heap->elem[left_child] > heap->elem[right_child] ? 153 left_child : right_child; 154 } 155 else if ( left_child < heap->current_index ) 156 { 157 swap_index = left_child; 158 } 159 else if ( right_child < heap->current_index ) 160 { 161 swap_index = right_child; 162 } 163 164 /**< if heap->elem[swap_index] is greater than heap->elem[parent], swap each other. */ 165 if ( heap->elem[swap_index] > heap->elem[parent_index] ) 166 { 167 swap_int( heap->elem, swap_index, parent_index ); 168 parent_index = swap_index; 169 } 170 else 171 { 172 break; 173 } 174 } 175 176 return ret; 177 } 178 179 /**< test max_heap */ 180 void test_max_heap() 181 { 182 int number[] = { 79, 81, 97, 21, 88, 15, 1, 61, 28, 68 }; 183 int size_i = sizeof( number ) / sizeof( int ); 184 int index = 0; 185 max_heap *heap = NULL; 186 187 heap = alloc_max_heap( size_i); 188 for ( index = 0; index < size_i; ++index ) 189 { 190 push_value( heap, number[index] ); 191 } 192 193 printf( " the element in max_heap is " ); 194 while ( heap->current_index ) 195 { 196 index = pop_value( heap ); 197 printf( " %d", index ); 198 } 199 printf( " " ); 200 201 destroy_max_heap( &heap ); 202 } 203 204 /**< generating data */ 205 void generating_data( const char *file_name, const int size_i, const int range ) 206 { 207 FILE *output_file = NULL; 208 int index = 0, 209 data = 0; 210 211 /**< check parameter */ 212 if ( NULL == file_name || size_i <= 0 || range <= 0 ) 213 { 214 fprintf( stderr, "generating_data: invalid parameter. " ); 215 return; 216 } 217 218 /**< open file. */ 219 output_file = fopen( file_name, "w" ); 220 if ( NULL == output_file ) 221 { 222 fprintf( stderr, "generating_data: failed to open file %s. ", file_name ); 223 return; 224 } 225 226 /**< write data into file. */ 227 srand( (unsigned) time(0) ); 228 while ( index < size_i ) 229 { 230 data = rand() % range; 231 fprintf( output_file, "%d ", data ); 232 ++index; 233 } 234 235 fclose( output_file ); 236 } 237 238 /**< output min k elements */ 239 void output_min_k_elements( const char *file_name, const int k ) 240 { 241 max_heap *heap = NULL; 242 FILE *input_file = NULL; 243 int data = 0, 244 index = k; 245 246 /**< check argument. */ 247 if ( NULL == file_name || k <= 0 ) 248 { 249 fprintf( stderr, "output_min_k_elements: invalid parameter. " ); 250 return; 251 } 252 253 /**< open file */ 254 input_file = fopen( file_name, "r" ); 255 if ( NULL == input_file ) 256 { 257 fprintf( stderr, "output_min_k_elements: failed to open file %s. ", file_name ); 258 return; 259 } 260 261 heap = alloc_max_heap( k ); 262 /**< fill heap */ 263 while ( index-- > 0 && fscanf( input_file, "%d", &data) != EOF ) 264 { 265 push_value( heap, data ); 266 } 267 268 while ( fscanf( input_file, "%d", &data ) != EOF ) 269 { 270 if ( heap->current_index == k 271 && data < heap->elem[0] ) 272 { 273 pop_value( heap ); 274 push_value( heap, data ); 275 } 276 } 277 278 /**< output data */ 279 while ( heap->current_index ) 280 { 281 data = pop_value( heap ); 282 printf( " %d", data ); 283 } 284 285 /**< free memory and close file. */ 286 destroy_max_heap( &heap ); 287 fclose( input_file ); 288 } 289 290 /**< test */ 291 void test_func( void ) 292 { 293 char *file_name = "e:\test.txt"; 294 int k = 10; 295 int size_i = 100000; 296 int range = 100000000; 297 298 /**< generating data */ 299 generating_data( file_name, size_i, range ); 300 output_min_k_elements( file_name, k ); 301 } 302 303 int main() 304 { 305 test_func(); 306 307 return 0; 308 }
4. 通过随机函数生成随机数填充一个二维数组，随机数被4取余，其中0表示red，1表示blue，2表示green，3表示black。根据五子棋的规则，5个连续在一起的输出。(第一版有错误，朋友找到的。现在是更新版本)
其中，二维数组为10*10.
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 void gobang_problem( int colors[][10], int size_i ) 6 { 7 int i, j, k, p, 8 colors_cnt = 0; 9 10 /**< check argument. */ 11 if ( NULL == colors || size_i <= 0 ) 12 { 13 fprintf( stderr, "gobang_problem: invalid argument. " ); 14 return; 15 } 16 17 /**< compute */ 18 for ( i = 0; i < size_i; ++i ) 19 { 20 for ( j = 0; j < size_i; ++j ) 21 { 22 /**< 纵向 */ 23 for ( colors_cnt = 0, k = j; k < size_i; ++k ) 24 { 25 if ( colors[i][j] == colors[i][k] ) 26 { 27 colors_cnt++; 28 /**< if found, output. */ 29 if ( colors_cnt == 5 ) 30 { 31 while ( k >= j ) 32 { 33 printf( " %d %d,", i, k-- ); 34 } 35 36 return; 37 } 38 } 39 else 40 { 41 break; /**< if not same, do not need to continue. */ 42 } 43 } 44 45 /**< 横向 */ 46 for ( colors_cnt = 0, k = i; k < size_i; ++k ) 47 { 48 if ( colors[i][j] == colors[k][j] ) 49 { 50 colors_cnt++; 51 if ( colors_cnt == 5 ) 52 { 53 while ( k >= i ) 54 { 55 printf( " %d %d,", k--, j ); 56 } 57 58 return; 59 } 60 61 } 62 else 63 { 64 break; 65 } 66 } 67 68 /**< 向下斜向 */ 69 for ( colors_cnt = 0, k = i, p = j; 70 k < size_i && p < size_i; ++k, ++p ) 71 { 72 if ( colors[i][j] == colors[k][p] ) 73 { 74 colors_cnt++; 75 if ( colors_cnt == 5 ) 76 { 77 while ( k >= i && p >= j ) 78 { 79 printf( " %d %d,", k--, p-- ); 80 } 81 82 return; 83 } 84 85 } // end if 86 else 87 { 88 break; 89 } 90 }// end for 91 } // end for 92 } // end for 93 94 95 /**< 向上斜向 */ 96 for ( i = size_i - 1; i >= 0; --i ) 97 { 98 for ( j = 0; j < size_i; ++j ) 99 { 100 for ( colors_cnt = 0, k = i, p = j; 101 k >= 0 && p < size_i; 102 --k, ++p ) 103 { 104 if ( colors[i][j] == colors[k][p] ) 105 { 106 colors_cnt++; 107 if ( colors_cnt == 5 ) 108 { 109 while ( k <= i && p >= j ) 110 { 111 printf( " %d %d,", k++, p-- ); 112 } 113 114 return; 115 } 116 117 } 118 else 119 { 120 break; 121 } 122 } // end for 123 } 124 } 125 } 126 127 void generate_chessboard( int chessboard[][10], int size_i ) 128 { 129 int i, j; 130 131 /**< check argument */ 132 if ( NULL == chessboard || size_i <= 0 ) 133 { 134 fprintf( stderr, "generate_chessboard: invalid argument. " ); 135 return; 136 } 137 138 /**< generating */ 139 srand( (unsigned) time(0) ); 140 for ( i = 0; i < size_i; ++i ) 141 { 142 for ( j = 0; j < size_i; ++j ) 143 { 144 chessboard[i][j] = rand() % 4; 145 } 146 } 147 148 /**< output chessboard */ 149 printf( " This color in chessboard is " ); 150 for ( i = 0; i < size_i; ++i ) 151 { 152 for ( j = 0; j < size_i; ++j ) 153 { 154 printf( " %d", chessboard[i][j] ); 155 } 156 printf( " " ); 157 } 158 } 159 160 int main() 161 { 162 int chessboard[10][10]; 163 int size_i = 10; 164 165 generate_chessboard( chessboard, size_i ); 166 printf( " Five colors in low: " ); 167 gobang_problem( chessboard, size_i ); 168 169 return 0; 170 }
欢迎大家指导！！