please give me logic of how to sort link list of string

[incredible]

how to sort link list of string

 

[Richard Heathfield]

incredible said:

how to sort link list of string

Presumably you know that sorting consists of putting items into a particular
order, which implies that you need to be able to compare them and decide
which of them belongs earlier in the order. You also need to be able to
swap strings round if they're not in the right order. Presumably you know
how to compare two strings. So your immediate problem is: "how do I
exchange two items in a linked list?"

Assuming your nodes are defined like this:

struct node
{
struct node *prev;
struct node *next;
void *data;
};

(with the data pointer pointing to some kind of aggregate containing the key
data and perhaps a payload), it's very easy to swap two nodes:

if(p1 != NULL && p2 != NULL)
{
void *tmp = p1->data;
p1->data = p2->data;
p2->data = tmp;
}

If the data is *only* a string, s/void/char/

If you're using ordinary arrays in your nodes, though, it's slightly more
annoying, in that you'll have to get an array big enough to hold the
largest string in the list, and use that as your tmp, using strcpy rather
than assignment.

Once you've got that in place, it's just a matter of doing the right
compares and the right swaps in the right order.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: normal service will be restored as soon as possible. Please do not
adjust your email clients.

 

[Ben Pfaff]

how to sort link list of string

There's a pair of fairly complete and fairly portable linked list
libraries here:
http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/?root=pspp
Look at ll.[ch] and llx.[ch].

 

[Eric Sosman]

incredible wrote On 11/20/06 12:05,:

how to sort link list of string

/* Usage instructions: Declare a `struct node' type containing a
* `struct node*' field named `next' as its forward link, along with
* whatever other elements are desired. Define a precedes() function
* that takes two `const struct node*' pointers and returns nonzero
* if the first struct must precede the second in the sorted output,
* or zero if the first follows the second or if they compare equal.
* Build a linked list of `struct node' instances, with the `next'
* field of the last node equal to NULL. Call the listsort() function,
* passing a pointer to the first node as the argument. listsort()
* will rearrange the list's links to sort the list in accordance with
* the precedes() function, and will return a pointer to the first
* `struct node' of the sorted list.
*
* Note: This code uses an OO style.
*/

#include <limits.h>
static struct node*O(struct node*o,struct node*O){struct node*Oo,**oO;
oO=&Oo;for(;{if(precedes(O,o)){*oO=O;oO=&O->next;if(0==(O=O->next)){
*oO=o;break;}}else{*oO=o;oO=&o->next;if(!(o=o->next)){*oO=O;break;}}}\
return Oo;}struct node*listsort(struct node*oO){struct node*o,*o0[siz\
eof(void*)*CHAR_BIT-sizeof(char)],*Oo;int oo,O0;o0[O0=0]=0;while((o=o\
O)){if((Oo=o->next)==0)break;oO=Oo->next;if(precedes(Oo,o)){Oo->next=o
;o->next=0;o=Oo;}else{Oo->next=0;}for(oo=0;(Oo=o0[oo]){o0[oo]=0;o=O(
Oo,o);if(++oo>O0){O0=oo;break;}}o0[oo]=o;}for(oo=0;oo<=O0;++oo){if((o=
o0[oo]))oO=oO?O(o,oO);}return oO;}

 

[Tor Rustad]

Eric Sosman skrev:

* Note: This code uses an OO style.

ROFL!

 

[CBFalconer]

incredible wrote On 11/20/06 12:05,:

how to sort link list of string

/* Usage instructions: Declare a `struct node' type containing a
* `struct node*' field named `next' as its forward link, along with
* whatever other elements are desired. Define a precedes() function
* that takes two `const struct node*' pointers and returns nonzero
* if the first struct must precede the second in the sorted output,
* or zero if the first follows the second or if they compare equal.
* Build a linked list of `struct node' instances, with the `next'
* field of the last node equal to NULL. Call the listsort() function,
* passing a pointer to the first node as the argument. listsort()
* will rearrange the list's links to sort the list in accordance with
* the precedes() function, and will return a pointer to the first
* `struct node' of the sorted list.
*
* Note: This code uses an OO style.
*/

#include <limits.h>
static struct node*O(struct node*o,struct node*O){struct node*Oo,**oO;
oO=&Oo;for(;{if(precedes(O,o)){*oO=O;oO=&O->next;if(0==(O=O->next)){
*oO=o;break;}}else{*oO=o;oO=&o->next;if(!(o=o->next)){*oO=O;break;}}}\
return Oo;}struct node*listsort(struct node*oO){struct node*o,*o0[siz\
eof(void*)*CHAR_BIT-sizeof(char)],*Oo;int oo,O0;o0[O0=0]=0;while((o=o\
O)){if((Oo=o->next)==0)break;oO=Oo->next;if(precedes(Oo,o)){Oo->next=o
;o->next=0;o=Oo;}else{Oo->next=0;}for(oo=0;(Oo=o0[oo]){o0[oo]=0;o=O(
Oo,o);if(++oo>O0){O0=oo;break;}}o0[oo]=o;}for(oo=0;oo<=O0;++oo){if((o=
o0[oo]))oO=oO?O(o,oO);}return oO;}

[1] c:\c\junk>cc junk.c
junk.c: In function `O':
junk.c:3: warning: implicit declaration of function `precedes'
junk.c:3: dereferencing pointer to incomplete type
junk.c:3: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c: In function `listsort':
junk.c:4: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c:8: dereferencing pointer to incomplete type
junk.c:8: dereferencing pointer to incomplete type

 

[Eric Sosman]

CBFalconer wrote On 11/20/06 16:06,:

incredible wrote On 11/20/06 12:05,:

how to sort link list of string

/* Usage instructions: Declare a `struct node' type containing a
* `struct node*' field named `next' as its forward link, along with
* whatever other elements are desired. Define a precedes() function
* that takes two `const struct node*' pointers and returns nonzero
* if the first struct must precede the second in the sorted output,
* or zero if the first follows the second or if they compare equal.
* Build a linked list of `struct node' instances, with the `next'
* field of the last node equal to NULL. Call the listsort() function,
* passing a pointer to the first node as the argument. listsort()
* will rearrange the list's links to sort the list in accordance with
* the precedes() function, and will return a pointer to the first
* `struct node' of the sorted list.
*
* Note: This code uses an OO style.
*/

#include <limits.h>
static struct node*O(struct node*o,struct node*O){struct node*Oo,**oO;
oO=&Oo;for(;{if(precedes(O,o)){*oO=O;oO=&O->next;if(0==(O=O->next)){
*oO=o;break;}}else{*oO=o;oO=&o->next;if(!(o=o->next)){*oO=O;break;}}}\
return Oo;}struct node*listsort(struct node*oO){struct node*o,*o0[siz\
eof(void*)*CHAR_BIT-sizeof(char)],*Oo;int oo,O0;o0[O0=0]=0;while((o=o\
O)){if((Oo=o->next)==0)break;oO=Oo->next;if(precedes(Oo,o)){Oo->next=o
;o->next=0;o=Oo;}else{Oo->next=0;}for(oo=0;(Oo=o0[oo]){o0[oo]=0;o=O(
Oo,o);if(++oo>O0){O0=oo;break;}}o0[oo]=o;}for(oo=0;oo<=O0;++oo){if((o=
o0[oo]))oO=oO?O(o,oO);}return oO;}

[1] c:\c\junk>cc junk.c
junk.c: In function `O':
junk.c:3: warning: implicit declaration of function `precedes'
junk.c:3: dereferencing pointer to incomplete type
junk.c:3: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c: In function `listsort':
junk.c:4: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c:4: dereferencing pointer to incomplete type
junk.c:8: dereferencing pointer to incomplete type
junk.c:8: dereferencing pointer to incomplete type

Looks like you failed to heed the usage instructions.

 

[pete]

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)(void *));
void list_fputs(FILE *stream, list_type *node);
list_type *string_node(list_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(list_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(list_type *head, long unsigned count);
static list_type *list_merge(list_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *));

int main(void)
{
char *string[] = {
"one","two","three","four","five",
"six","seven","eight","nine","ten"
};
list_type *head, *tail;
unsigned index;

tail = head = NULL;
index = 0;
do {
tail = string_node(&head, tail, string[index]);
} while (tail != NULL && ++index != NMEMB(string));
if (tail == NULL) {
list_free(head, free);
puts("malloc trouble!");
exit(EXIT_FAILURE);
}
puts("/* BEGIN new.c output */\n");
puts("Original order of list:");
list_fputs(stdout, head);
head = list_sort(head, lencomp);
puts("\nList after stable mergesort by string length:");
list_fputs(stdout, 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)(void *))
{
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(list_type **head,
list_type *tail,
char *data)
{
list_type *node;

node = malloc(sizeof *node);
if (node != NULL) {
node -> next = NULL;
node -> data = malloc(strlen(data) + 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(head, compar)
? node_sort(head, node_count(head), compar)
: head;
}

static int list_sorted(list_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(list_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(list_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 */

 

[CBFalconer]

how to sort link list of string

/* Sort file stdin. By C.B. Falconer, 20 Nov. 2006 */
/* Released to public domain. Attribution appreciated */
/* Run with "sortfile < whatever" */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct line {
char *ln;
struct line *next;
} line, *lineptr;

/* ------------------------- */

#define INITSIZE 112
#define DELTASIZE (INITSIZE + 16)

enum {OK = 0, NOMEM};

/* See published ggets.zip */
int ggets(char* *ln)
{
int cursize, ch, ix;
char *buffer, *temp;

*ln = NULL; /* default */
if (NULL == (buffer = malloc(INITSIZE))) return NOMEM;
cursize = INITSIZE;

ix = 0;
while ((EOF != (ch = getc(stdin))) && ('\n' != ch)) {
if (ix >= (cursize - 1)) { /* extend buffer */
cursize += DELTASIZE;
if (NULL == (temp = realloc(buffer, (size_t)cursize))) {
/* ran out of memory, return partial line */
buffer[ix] = '\0';
*ln = buffer;
return NOMEM;
}
buffer = temp;
}
buffer[ix++] = ch;
}
if ((EOF == ch) && (0 == ix)) {
free(buffer);
return EOF;
}

buffer[ix] = '\0';
if (NULL == (temp = realloc(buffer, (size_t)ix + 1))) {
*ln = buffer; /* without reducing it */
}
else *ln = temp;
return OK;
} /* ggets */

/* ------------------------- */

/* split list p into 2 nearly equal lists, return 2nd part */
static lineptr splitlist(lineptr p)
{
lineptr p1, p2, p3;

p1 = p2 = p3 = p;
if (!p) return NULL;
do {
p3 = p2;
p2 = p2->next; /* advance 1 */
p1 = p1->next;
if (p1) p1 = p1->next; /* advance 2 */
} while (p1);

/* now form new list after p2 */
p3->next = NULL; /* terminate 1st half */
return p2;
} /* splitlist */

/* ------------------------- */

/* Merge two ordered lists into one */
static lineptr mergelists(lineptr p1, lineptr p2)
{
line n;
lineptr p;

p = &n;
n.next = p;

while (p1 && p2) {
if (strcmp(p1->ln, p2->ln) <= 0) {
p->next = p1; p = p1; p1 = p1->next;
}
else {
p->next = p2; p = p2; p2 = p2->next;
}
}
/* at least one list now empty, copy other */
/* one or both of these operations is null */
if (p1) p->next = p1;
if (p2) p->next = p2;

/* check for empty lists */
if (n.next == &n) return NULL;
return n.next;
} /* mergelists */

/* ------------------------- */

/* Recursively sort a linked list. The sort is stable */
/* This is an O(NlogN) process for all lists. */
static lineptr mergesort(lineptr root)
{
lineptr p;

if (root && root->next) { /* 2 up items in list */
p = splitlist(root); /* alters list root */
root = mergelists(mergesort(root),
mergesort( p));
}
/* else the unit or empty list is already sorted */

return root;
} /* mergesort */

/* ------------------------- */

/* Load, sort, and print file, which fits in memory. */
int main(void)
{
lineptr p, last;
char *nextln;

p = NULL;
while (0 == ggets(&nextln))
if ((last = malloc(sizeof *last))) {
last->ln = nextln;
last->next = p;
p = last;
}
else break; /* out of memory or i/o error */

p = mergesort(p);

while (p) {
puts(p->ln);
last = p;
p = p->next;
free(last->ln);
free(last);
}
return 0;
} /* sortfile main */

 

[pete]

list_type *list_sort(list_type *head,
int (*compar)(const list_type *, const list_type *));

head = list_sort(head, lencomp);

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;
}

That function's prototype should be
int lencomp(const list_type *a, const list_type *b);
and the definition should be:

int lencomp(const list_type *a, const list_type *b)
{
const size_t a_len = strlen(a -> data);
const size_t b_len = strlen(b -> data);

return b_len > a_len ? -1 : a_len != b_len;
}

instead.