这天要面试，提前把链表操作重新写了一遍。备份一下，以备不时之需。
希望有人能看到这篇代码，并指正。
1 // File Name : list.h 2 #include "stdafx.h" 3 #include "stdio.h" 4 #include <stdlib.h> 5 #include "string.h" 6 7 //creat list 8 //creat node 9 //insert 10 //del 11 //find 12 //sort 13 typedef int data_t ; 14 typedef struct NODE{ 15 data_t data; 16 NODE* next; 17 }NODE ,*NODEPTR; 18 19 typedef struct LIST{ 20 NODE* head;//init==0 21 NODE* tail;//init==0 22 int num ; //min==0 23 }LIST; 24 25 //create 26 extern NODE *create_node(data_t data); 27 extern LIST *creat_list(); 28 extern bool is_null(LIST* list); 29 //find 30 extern NODE* find_node(LIST* list ,data_t data); 31 extern NODE* inline find_node_by_index(LIST* list , int index);//index : from 1 to list->num 32 33 //del 34 extern int del_node_data(LIST* list,data_t data); 35 extern data_t del_node_head(LIST* list ); 36 extern data_t del_node_index(LIST* list,int index);//index : from 1 to list->num 37 extern data_t del_node_tail(LIST* list ); 38 39 //insert 40 extern int insert_data_F(LIST* list, data_t data); 41 extern void insert_node_F(LIST* list, NODE* node); 42 extern int insert_data_T(LIST* list, data_t data); 43 extern void insert_node_T(LIST* list, NODE* node ); 44 extern int insert_data_index(LIST* list , data_t data,int index);//index : from 1 to list->num 45 extern int insert_node_index(LIST* list , NODE* node,int index);//index : from 1 to list->num 46 47 extern int insert_data_ordered(LIST* list , data_t data );//assume the list is ordered (low to high )48 49 //sort 50 extern int sort(LIST* list); 51 extern int swap(LIST* list, int indexf,int indexn);//index : from 1 to list->num 52 extern int inline swap_node(NODE* before ,NODE* next); 53
1 /****************************************************************************** 2 3 Copyright (C), 2001-2011, DCN Co., Ltd. 4 5 ****************************************************************************** 6 File Name : list.c 7 Version : Initial Draft 8 Author : ocj 9 Created : 2014/8/8 10 Last Modified : 11 Description : singlelist 12 Function List : 13 create_node 14 creat_list 15 del_node_data 16 del_node_head 17 del_node_index 18 del_node_tail 19 find_node 20 find_node_by_index 21 insert_data_F 22 insert_data_index 23 insert_data_ordered 24 insert_data_T 25 insert_node_F 26 insert_node_index 27 insert_node_T 28 is_null 29 sort 30 swap 31 swap_node 32 History : 33 1.Date : 2014/8/8 34 Author : ocj 35 Modification: Created file 36 37 ******************************************************************************/ 38 #include "list.h" 39 //if success :ret!=0 40 LIST *creat_list() 41 { 42 LIST* list = (LIST*)malloc(sizeof(LIST)); 43 list->head = 0; 44 list->tail = 0; 45 list->num = 0; 46 return list; 47 } 48 //if success :ret!=0 49 NODE *create_node(data_t data) 50 { 51 NODE* node = (NODE*)malloc(sizeof(NODE)); 52 node->dext = 0; 53 node.data = data; 54 return node; 55 } 56 57 //return 1: is null 58 //return 0: not null 59 bool is_null(LIST* list) 60 { 61 //return (list->num==0); //method 1 62 return (list->head->next == 0 ) ;//method 2 63 } 64 65 //ret==0:fail 66 int insert_node_F(LIST* list, NODE* node) 67 { 68 if(list==0 || node ==0){ 69 return 0; 70 } 71 if(list->head==0){ 72 list->tail = node; 73 } 74 list->head = node ; 75 node->next = list->head; 76 //if list is null ,node->next == list->head==0 77 //if list is not null ,node->next == list->head!=0 78 list->num++; 79 } 80 81 //return 1 : ok 82 //return 0 : fail 83 int insert_data_F(LIST* list, data_t data) 84 { 85 NODE* node = create_node(data); 86 if(node){ 87 return 0; 88 } 89 insert_node_F(list , node); 90 return 1; 91 } 92 93 void insert_node_T(LIST* list, NODE* node ) 94 { 95 if(list->head==0){ 96 node->next = 0; 97 list->head = list->tail = node; 98 } 99 100 list->tail = node ; 101 node->next = 0 ; 102 list->num++; 103 } 104 105 //return 1 : ok 106 //return 0 : fail 107 int insert_data_T(LIST* list, data_t data) 108 { 109 NODE* node = create_node(data); 110 if(node){ 111 return 0; 112 } 113 insert_node_T(list , node); 114 return 1; 115 } 116 117 //ret=0: fail 118 int insert_node_index(LIST* list , NODE* node,int index) 119 { 120 if(index>listnum+1) { 121 return 0; 122 } 123 124 if(index==1){ 125 insert_node_F(list ,node); 126 }else if(index ==list->num+1){ 127 insert_node_T(list ,node); 128 }else{ 129 NODE* before = list->head; 130 while(index>2){ 131 index--; 132 before = before->next; 133 } 134 node->next = before->next ; 135 before->next = node ; 136 list->num++; 137 } 138 return 1; 139 } 140 //ret=0: fail 141 int insert_data_index(LIST* list , data_t data,int index) 142 { 143 NODE* node = create_node(data) ; 144 if(node==null){ 145 return 0 ; 146 } 147 return insert_node_index(list , node,index ); 148 } 149 150 //assume the order is low to high 151 //ret==0: fail 152 int insert_data_ordered(LIST* list , data_t data ) 153 { 154 NODE* node = create_node(data); 155 if(node==0){ 156 return 0; 157 } 158 if(list->head == 0){ 159 list->head = list->tail = node; 160 return 1; 161 } 162 163 if(node->data < head->data){ 164 insert_data_F(list ,node); 165 }else { 166 list->num++; 167 NODE *before = head; 168 NODE* nodet = head->next ; 169 while(node->data > nodet->data && nodet->next!=0){ 170 //until( node->data < nodet->data || tail ) 171 nodet = nodet->next ; 172 before = before->next; 173 } 174 if(nodet->next==0){ 175 nodet->next = node ; 176 }else{ 177 node->next = nodet ; 178 before->next = node ; 179 } 180 } 181 return 1; 182 } 183 184 //not find: return 0 185 //success find and del :return 1 186 int del_node_data(LIST* list,data_t data) //find and del first_found 187 { 188 if(list->num ==0){ 189 return 0; 190 } 191 192 NODE* before = list->head ; 193 NODE* nodet = list->head ; 194 if(nodet->data == data){ //head->data == data 195 list->head = list->head->next ; 196 free(nodet); 197 list->num--; 198 return 1; 199 } 200 201 nodet = nodet->next; 202 while(nodet->data!=data && nodet->next!=0 ){ 203 nodet = nodet->next; 204 } 205 if(nodet->data == data ){ 206 before->next = nodet->next ; 207 free(nodet); 208 list->num--; 209 }else{//not found 210 return 0; 211 } 212 return 1; 213 } 214 215 216 data_t del_node_index(LIST* list,int index) 217 { 218 if(is_null(list) || index > list->num){ 219 exit(-1); 220 } 221 NODE* before = list->head ; 222 NODE* del = list->head ; 223 data_t data ; 224 if(list->num == 1 ) { //head 225 list->num--; 226 list->head = list->tail = 0; 227 data = del->data; 228 free(del); 229 return data; 230 } 231 232 int first = 1 ; 233 for( ;index>1;index--){//offset --- index 234 if(!first){ 235 before = before->next ; 236 } 237 first = 0; 238 del = del->next; 239 } 240 241 before->next = del->next ; 242 data = del->data; 243 if(del==list->tail){ 244 list->tail = before ; 245 } 246 free(del); 247 list->num--; 248 return data; 249 250 } 251 data_t del_node_head(LIST* list ) 252 { 253 if(is_null(list)){ 254 exit(-1) ; 255 } 256 data_t data ; 257 NODE* del = list->head ; 258 list->head = list->head->next ; 259 free(del); 260 list->num--; 261 return data; 262 } 263 data_t del_node_tail(LIST* list ) 264 { 265 if(is_null(list)){ 266 exit(-1) ; 267 } 268 NODE *before = list->head ; 269 data_t data = list->tail->data; 270 271 if(list->num ==1){ 272 list->head = list->tail = 0; 273 list->num--; 274 free(before); 275 return data ; 276 } 277 278 while(before->next!=0 && before->next->next != 0) { 279 before = before->next ; 280 } 281 282 list->tail = before; 283 list->num--; 284 free(before->next); 285 return data ; 286 } 287 288 //return 0: fail to find 289 //return node* : node first_found 290 NODE* find_node(LIST* list ,data_t data) 291 { 292 if(is_null(list)){ 293 return 0 ; 294 } 295 296 NODE* nodet = list->head; 297 do{ 298 if(nodet->data == data) 299 return nodet; 300 }while(nodet->next!=0); 301 302 return 0; 303 } 304 305 //head_index == 1; 306 //return 0: fail to find 307 //return node* : node first_found 308 NODE* inline find_node_by_index(LIST* list , int index) 309 { 310 if(list==0 || list->num ==0 || index > list->num){ 311 return 0; 312 } 313 NODE* find = list->head; 314 while(--index){ 315 find =find->next; 316 } 317 return find ; 318 } 319 320 int swap(LIST* list, int indexf,int indexn) 321 { 322 NODE* nodef = find_node( list , indexf ) ; 323 NODE* noden = find_node( list , indexn ) ; 324 data_t swp = nodef->data; 325 nodef->data = noden->data; 326 noden->data = swp->data; 327 } 328 329 //ret==0 : fail 330 int inline swap_node(NODE* before ,NODE* next) 331 { 332 if(before == 0 ||next == 0){ 333 return 0; 334 } 335 before->data ^=next->data ; 336 next->data ^=before->data ; 337 before->data ^=next->data ; 338 } 339 340 //asume from little to big 341 int sort(LIST* list) 342 { 343 int times; 344 int index; 345 NODE* before = list->head; 346 NODE* next = 0; 347 if(list==0){ 348 return 0; 349 } 350 if(list->num==0){ 351 return 1 ; 352 } 353 for(times=0;times<list->num ;times++){ 354 for(index=1;index<=size-times;index++){ 355 before = find_node_by_index(list ,index); 356 next = before->next; 357 if(next->data<before->data){ 358 //before->data = before->data^ next->data ; 359 //nexty->data = before->data^ next->data ; 360 //before->data = before->data^ next->data ; 361 swap_node(before , next); 362 } 363 } 364 return 1; 365 }