incredible wrote:
>
how to sort link list of string
/* BEGIN new.c output */
Original order of list:
one
two
three
four
five
six
seven
eight
nine
ten
List after stable mergesort by string length:
one
two
six
ten
four
five
nine
three
seven
eight
The list has been freed.
/* END new.c output */
/* BEGIN new.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NMEMB(A) (sizeof (A) / sizeof *(A))
struct list_node {
struct list_node *next;
void *data;
};
typedef struct list_node list_type;
void list_free(list_ type *node, void (*free_data)(vo id *));
void list_fputs(FILE *stream, list_type *node);
list_type *string_node(li st_type **head,
list_type *tail,
char *data);
int lencomp(const void *a, const void *b);
list_type *list_sort(list _type *head,
int (*compar)(const list_type *, const list_type *));
static int list_sorted(lis t_type *list,
int (*compar)(const list_type *, const list_type *));
static long unsigned node_count(list _type *head);
static list_type *node_sort(list _type *head, long unsigned count,
int (*compar)(const list_type *, const list_type *));
static list_type *list_split(lis t_type *head, long unsigned count);
static list_type *list_merge(lis t_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));
int main(void)
{
char *string[] = {
"one","two","th ree","four","fi ve",
"six","seven"," eight","nine"," ten"
};
list_type *head, *tail;
unsigned index;
tail = head = NULL;
index = 0;
do {
tail = string_node(&he ad, tail, string[index]);
} while (tail != NULL && ++index != NMEMB(string));
if (tail == NULL) {
list_free(head, free);
puts("malloc trouble!");
exit(EXIT_FAILU RE);
}
puts("/* BEGIN new.c output */\n");
puts("Original order of list:");
list_fputs(stdo ut, head);
head = list_sort(head, lencomp);
puts("\nList after stable mergesort by string length:");
list_fputs(stdo ut, head);
list_free(head, free);
puts("\nThe list has been freed.\n");
puts("/* END new.c output */");
return 0;
}
void list_free(list_ type *node, void (*free_data)(vo id *))
{
list_type *next_node;
while (node != NULL) {
next_node = node -next;
free_data(node -data);
free(node);
node = next_node;
}
}
void list_fputs(FILE *stream, list_type *node)
{
while (node != NULL) {
fputs(node -data, stream);
putc('\n', stream);
node = node -next;
}
}
list_type *string_node(li st_type **head,
list_type *tail,
char *data)
{
list_type *node;
node = malloc(sizeof *node);
if (node != NULL) {
node -next = NULL;
node -data = malloc(strlen(d ata) + 1);
if (node -data != NULL) {
if (*head == NULL) {
*head = node;
} else {
tail -next = node;
}
strcpy(node -data, data);
} else {
free(node);
node = NULL;
}
}
return node;
}
int lencomp(const void *a, const void *b)
{
const size_t a_len = strlen(((const list_type *)a) -data);
const size_t b_len = strlen(((const list_type *)b) -data);
return b_len a_len ? -1 : a_len != b_len;
}
list_type *list_sort(list _type *head,
int (*compar)(const list_type *, const list_type *))
{
return
!list_sorted(he ad, compar)
? node_sort(head, node_count(head ), compar)
: head;
}
static int list_sorted(lis t_type *list,
int (*compar)(const list_type *, const list_type *))
{
if (list != NULL) {
while (list -next != NULL) {
if (compar(list, list -next) 0) {
break;
}
list = list -next;
}
}
return list == NULL || list -next == NULL;
}
static long unsigned node_count(list _type *head)
{
long unsigned count;
for (count = 0; head != NULL; head = head -next) {
++count;
}
return count;
}
static list_type *node_sort(list _type *head, long unsigned count,
int (*compar)(const list_type *, const list_type *))
{
long unsigned half;
list_type *tail;
if (count 1) {
half = count / 2;
tail = list_split(head , half);
tail = node_sort(tail, count - half, compar);
head = node_sort(head, half, compar);
head = list_merge(head , tail, compar);
}
return head;
}
static list_type *list_split(lis t_type *head, long unsigned count)
{
list_type *tail;
while (--count != 0) {
head = head -next;
}
tail = head -next;
head -next = NULL;
return tail;
}
static list_type *list_merge(lis t_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
list_type *list, *sorted, **node;
node = compar(head, tail) 0 ? &tail : &head;
sorted = list = *node;
*node = sorted -next;
while (*node != NULL) {
node = compar(head, tail) 0 ? &tail : &head;
sorted -next = *node;
sorted = *node;
*node = sorted -next;
}
sorted -next = head != NULL ? head : tail;
return list;
}
/* END new.c */
--
pete
