sugaray wrote:

hi, i have to build a linked-list which has another sturcture _score

as it's data entry, so how can i sort such linked-list based on, let say,

history score into proper order (descending/ascending). thanx for your help !

struct _score {

float literature;

float history;

float sociology;

};

struct _node {

struct _score scores;

struct _node *next;

};

BEGIN output from n_sort.c

Random order

node -> scores.history is 4797963776.000000

node -> scores.history is 1558316800.000000

node -> scores.history is 10910205952.000000

node -> scores.history is 11304023040.000000

node -> scores.history is 9889975296.000000

node -> scores.history is 5643980288.000000

node -> scores.history is 10205063168.000000

node -> scores.history is 4162190592.000000

node -> scores.history is 9174709248.000000

node -> scores.history is 970891072.000000

node -> scores.history is 11570582528.000000

node -> scores.history is 2910468608.000000

node -> scores.history is 3875984384.000000

node -> scores.history is 8482416128.000000

node -> scores.history is 4301542400.000000

node -> scores.history is 25585348.000000

node -> scores.history is 13060592640.000000

Sorted order

node -> scores.history is 25585348.000000

node -> scores.history is 970891072.000000

node -> scores.history is 1558316800.000000

node -> scores.history is 2910468608.000000

node -> scores.history is 3875984384.000000

node -> scores.history is 4162190592.000000

node -> scores.history is 4301542400.000000

node -> scores.history is 4797963776.000000

node -> scores.history is 5643980288.000000

node -> scores.history is 8482416128.000000

node -> scores.history is 9174709248.000000

node -> scores.history is 9889975296.000000

node -> scores.history is 10205063168.000000

node -> scores.history is 10910205952.000000

node -> scores.history is 11304023040.000000

node -> scores.history is 11570582528.000000

node -> scores.history is 13060592640.000000

END output from n_sort.c

/* BEGIN n_sort.c */

#include <stdio.h>

#include <stdlib.h>

#define NODES 17

#define N_TYPE \

struct node { \

struct node *next; \

struct score scores;\

}

#define GT(A, B) ((A) -> scores.history > (B) -> scores.history)

#define NEXT next

#define LU_RAND_SEED 123456789LU

#define LU_RAND(S) ((S) * 69069 + 362437 & 0xffffffff)

#define str(s) # s

#define xstr(s) str(s)

struct score {

float literature;

float history;

float sociology;

};

typedef N_TYPE n_type;

void l_free(n_type *);

n_type *l_make(size_t);

void l_init(n_type *, long unsigned);

void l_print(n_type *);

n_type *n_sort(n_type *, size_t);

n_type *list_sort(n_type *);

int main(void)

{

n_type *list;

list = l_make(NODES);

if (list == NULL) {

fputs("The list was not allocated.\n", stderr);

exit(EXIT_FAILURE);

}

puts("BEGIN output from n_sort.c\n\nRandom order");

l_init(list, LU_RAND_SEED);

l_print(list);

puts("Sorted order");

list = list_sort(list);

l_print(list);

puts("END output from n_sort.c\n");

l_free(list);

return 0;

}

void l_free(n_type *node)

{

n_type *next;

do {

next = node -> NEXT;

free(node);

node = next;

} while (node != NULL);

}

n_type *l_make(size_t count)

{

n_type *node, *list;

list = count ? malloc(sizeof *list) : NULL;

if (list != NULL) {

node = list;

while (--count != 0) {

node -> NEXT = malloc(sizeof *node -> NEXT);

if (node -> NEXT == NULL) {

l_free(list);

return NULL;

} else {

node = node -> NEXT;

}

}

node -> NEXT = NULL;

}

return list;

}

void l_init(n_type *node, long unsigned seed)

{

do {

seed = LU_RAND(seed);

node -> scores.history = 3.14159265f * seed;

node = node -> NEXT;

} while (node != NULL);

}

void l_print(n_type *node)

{

do {

printf("node -> scores.history is %f\n",

node -> scores.history);

node = node -> NEXT;

} while (node != NULL);

putchar('\n');

}

n_type *list_sort(n_type *list)

{

n_type *node;

size_t count;

count = 1;

node = list -> NEXT;

while (node != NULL) {

++count;

node = node -> NEXT;

}

return n_sort(list, count);

}

n_type *n_sort(n_type *list, size_t count)

{

size_t half, other_half;

n_type *head, *tail, *sorted, **node;

if (count > 1) {

head = list;

other_half = half = count / 2;

while (--other_half != 0) {

head = head -> NEXT;

}

tail = head -> NEXT;

head -> NEXT = NULL;

tail = n_sort(tail, count - half);

head = n_sort(list, half);

node = GT(head, tail) ? &tail : &head;

sorted = list = *node;

*node = sorted -> NEXT;

while (*node != NULL) {

node = GT(head, tail) ? &tail : &head;

sorted = sorted -> NEXT = *node;

*node = sorted -> NEXT;

}

sorted -> NEXT = head != NULL ? head : tail;

}

return list;

}

/* END n_sort.c */

--

pete