merge.c (2005B)
1 /* Exercise 12.7 */ 2 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <time.h> 6 7 struct list { 8 int n; 9 struct list *next; 10 }; 11 12 typedef struct list List; 13 14 /* 15 * Prorotype 16 */ 17 void insert(List **list, int value); 18 void showlist(List *list); 19 List *merge(List *list, List *append); 20 21 int main(void) 22 { 23 List *list1 = NULL, *list2 = NULL; 24 List *list3; 25 int i; 26 27 srand( time(NULL) ); 28 29 for(i = 0; i < 10; i++) { 30 insert(&list1, 1 + rand() % 99); 31 insert(&list2, 1 + rand() % 99); 32 } 33 34 list3 = merge(list1, list2); 35 36 showlist(list1); 37 showlist(list2); 38 showlist(list3); 39 40 return 0; 41 } /* E0F main */ 42 43 void insert(List **list, int value) 44 { 45 List *newPtr; 46 List *previousPtr = NULL, *currentPtr = *list;; 47 48 if( (newPtr = malloc( sizeof(List) )) == NULL) { 49 printf("Cannot allocate the memory\n"); 50 return; 51 } 52 newPtr->n = value; 53 newPtr->next = NULL; 54 55 while( currentPtr != NULL && value > currentPtr->n) { 56 previousPtr = currentPtr; 57 currentPtr = currentPtr->next; 58 } 59 60 if( previousPtr == NULL ) { 61 newPtr->next = *list; 62 *list = newPtr; 63 } 64 else { 65 previousPtr->next = newPtr; 66 newPtr->next = currentPtr; 67 } 68 69 } /* eof insert() */ 70 71 void showlist(List *list) 72 { 73 List *currentPtr = list; 74 75 while( currentPtr != NULL ) { 76 printf("%d --> ", currentPtr->n); 77 currentPtr = currentPtr->next; 78 } 79 80 printf("NULL\n"); 81 82 } /* eof showlist() */ 83 84 List *merge(List *list, List *append) 85 { 86 List *currentPtr = list; 87 List *newPtr; 88 89 if( (newPtr = malloc( sizeof(List) )) == NULL ) { 90 printf("Cannot allocate memory\n"); 91 return NULL; 92 } 93 newPtr = newPtr->next; 94 95 /* insert list1 */ 96 while( currentPtr != NULL ) { 97 insert(&newPtr, currentPtr->n); 98 currentPtr = currentPtr->next; 99 } 100 101 currentPtr = append; 102 103 /* insert list2 */ 104 while( currentPtr != NULL ) { 105 insert(&newPtr, currentPtr->n); 106 currentPtr = currentPtr->next; 107 } 108 109 return newPtr; 110 } /* eof merge() */ 111