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
