listops.c
上传用户：lengbin
上传日期：2010-03-31
资源大小：121k
文件大小：4k
- /*----------------------------------------------------------------------
- File : listops.c
- Contents: some special list operations
- Author : Christian Borgelt
- History : 02.11.2000 file created from file lists.h
- ----------------------------------------------------------------------*/
- #include <stdio.h>
- #include "listops.h"
- /*----------------------------------------------------------------------
- Functions
- ----------------------------------------------------------------------*/
- void* l_sort (void *list, LCMPFN cmpfn, void *data)
- { /* --- sort a list with mergesort */
- LE *src, *dst; /* list of source/destination lists */
- LE **end; /* end of list of destination lists */
- LE *in1, *in2; /* input lists for merging */
- LE **out; /* output list for merging */
- if (!list) return list; /* check for an empty list */
- for (src = list; src->succ; ) {
- dst = src; src = src->succ; /* traverse the list and split it */
- dst->succ = NULL; /* into a list (abused pred ptr.) of */
- } /* single element lists (succ ptr.) */
- while (src->pred) { /* while more than one source list */
- end = &dst; /* start list of destination lists */
- do { /* merge pairs of source lists */
- out = end; /* start output list (merged input) */
- in1 = src; /* remove two (one) source list(s) */
- in2 = src->pred; /* and use them as input for merging */
- if (!in2) { /* if there is only one source list */
- *end = in1; end = &in1->pred;
- break; /* append it to the list of */
- } /* output list and abort the loop */
- src = in2->pred; /* remove lists from list of sources */
- while (1) { /* source lists merge loop */
- if (cmpfn(in1, in2, data) < 0) {
- /* if first list's element is smaller */
- *out = in1; /* move element to output list, */
- out = &(in1->succ); /* advance output pointer and */
- in1 = in1->succ; /* remove element from input list */
- if (!in1) break; } /* if the list gets empty, abort loop */
- else { /* if second list's element is smaller */
- *out = in2; /* move element to output list, */
- out = &(in2->succ); /* advance output pointer and */
- in2 = in2->succ; /* remove element from input list */
- if (!in2) break; /* if the list gets empty, abort loop */
- } /* (merge input lists into one) */
- }
- if (in1) *out = in1; /* append remaining elements */
- else *out = in2; /* to the output list */
- end = &(*end)->pred; /* advance destination list pointer */
- } while (src); /* while there is another source list */
- *end = NULL; /* terminate destination list */
- src = dst; /* transfer destination list */
- } /* to source list and start over */
- for (src->pred = NULL; src->succ; src = src->succ)
- src->succ->pred = src; /* set predecessor pointers */
- return dst; /* return a pointer to the first */
- } /* l_sort() */ /* element of the sorted list */
- /*--------------------------------------------------------------------*/
- void* l_reverse (void *list)
- { /* --- reverse a list */
- LE *le = NULL; /* to traverse the list elements */
- while (list) { /* while the list is not empty */
- le = list; /* get the next list element */
- list = le->succ; /* exchange the successor */
- le->succ = le->pred; /* and the predecessor */
- le->pred = list; /* of the list element */
- }
- return le; /* return a pointer to */
- } /* l_reverse() */ /* the new first element */
English
