By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,687 Members | 1,129 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,687 IT Pros & Developers. It's quick & easy.

Problem with sorting linked-list

P: n/a
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;
};
Nov 14 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
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;
};


Pass a pointer to your sorting function that compares
two "scores" and returns true if the first should come
before the second.
--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book

Nov 14 '05 #2

P: n/a
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;
};


Merge sort is, IMHO, the most attractive method for
sorting linked lists. The Standard C library doesn't
provide an implementation, but it's easy to write.

--
Er*********@sun.com

Nov 14 '05 #3

P: n/a
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
Nov 14 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.