449,412 Members | 993 Online
Need help? Post your question and get tips & solutions from a community of 449,412 IT Pros & Developers. It's quick & easy.

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

 P: n/a how to sort link list of string Nov 20 '06 #1
9 Replies

 P: n/a 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. Nov 20 '06 #2

 P: n/a "incredible" =(int)sizeof p)i-=sizeof p-1;putchar(p[i]\ );}return 0;} Nov 20 '06 #3

 P: n/a 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 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):o;}return oO;} -- Er*********@sun.com Nov 20 '06 #4

 P: n/a Eric Sosman skrev: * Note: This code uses an OO style. ROFL! -- Tor Nov 20 '06 #5

 P: n/a 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 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):o;}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. Nov 20 '06 #6

 P: n/a 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 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):o;}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. -- Er*********@sun.com Nov 20 '06 #7