|
|
|
|
|
/* merge_sort.prob.c */
/* 1998.1.19 by Kohji Itoh */ /* Unveil the $$$$$ (the number of $ does not necessarily coincidewith the correct number of characters) covered part of the program,compile, make the a.out run and print out the execution profile. */ /* you can ask me questions any time by mailing to itoh@te.noda.sut.ac.jp*/ #include #include typedef struct CELL *LIST; struct CELL{ int element; LIST next; }; LIST merge(LIST list1, LIST list2); LIST split(LIST list); LIST mergesort(LIST list); LIST makelist(); void printlist(LIST list); main() { LIST list; list=makelist(); printlist(mergesort(list)); } /* link cells with keyinput integers to make a list */ LIST makelist() { int c,x; LIST newlist; if ((c = getchar()) == '\n') return NULL; else { while (!isdigit(c)) c = getchar(); ungetc(c,stdin); scanf("%d",&x); newlist = (LIST)malloc(sizeof(struct CELL)); newlist->next = makelist(); newlist->element = x; return newlist; } } /* print out the list */ void printlist(LIST list) { while (list != NULL){ printf("%d ", list->element); list = list->next; } printf("\n"); } /* sort the list by $$$$$$$, $$$$$$$ and $$$$$$$, and return the result */ LIST mergesort(LIST list) { LIST secondlist; if (list == NULL) return NULL; else if (list->next == NULL) return list; else { secondlist = split(list); return merge(mergesort(list) , mergesort(secondlist)) ; } } /* merge the 2 sorted list and return the result*/ LIST merge(LIST list1, LIST list2) { if (list1 == NULL) return list2; else if (list2 == NULL) return list1; else if (list1->element <= list2-> element){ list1->next = merge(list1->next, list2); return list1; } else { list2->next = merge(list1, list2->next); return list2; } } /* split the list into one with even-numbered elements to be reteurned and the other with odd-numbered elements obtained by a side effect */ LIST split(LIST list) { LIST secondlist; if (list == NULL) return NULL; else if (list->next == NULL) return NULL; else { secondlist = list->next; list->next = secondlist->next; secondlist->next = split(list->next); return secondlist; } } |
|
2001ǯ07·î16Æü 22»þ04ʬ25ÉÃ
|
