Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > please give me logic of how to sort link list of string

Reply
Thread Tools

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

 
 
incredible
Guest
Posts: n/a
 
      11-20-2006
how to sort link list of string

 
Reply With Quote
 
 
 
 
Richard Heathfield
Guest
Posts: n/a
 
      11-20-2006
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.
 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      11-20-2006
"incredible" <(E-Mail Removed)> writes:

> 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/...spp/?root=pspp
Look at ll.[ch] and llx.[ch].
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      11-20-2006


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

--
http://www.velocityreviews.com/forums/(E-Mail Removed)

 
Reply With Quote
 
Tor Rustad
Guest
Posts: n/a
 
      11-20-2006
Eric Sosman skrev:

> * Note: This code uses an OO style.


ROFL!

--
Tor

 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      11-20-2006
Eric Sosman wrote:
> 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

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

 
Reply With Quote
 
Eric Sosman
Guest
Posts: n/a
 
      11-20-2006


CBFalconer wrote On 11/20/06 16:06,:
> Eric Sosman wrote:
>
>>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.

--
(E-Mail Removed)

 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      11-21-2006
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)(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 */


--
pete
 
Reply With Quote
 
CBFalconer
Guest
Posts: n/a
 
      11-21-2006
incredible wrote:
>
> 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 */

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net>

 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      11-21-2006
pete wrote:

> 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.

--
pete
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
Python Logic Map/Logic Flow Chart. (Example Provided) spike Python 8 02-09-2010 12:31 PM
Asynchronous Logic Gates and Analog Logic Gates Jyoti Ballabh Software 3 11-26-2009 06:48 PM
please give me logic of how to merge two sorted link list incredible C Programming 2 11-20-2006 07:22 PM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM



Advertisments