473,320 Members | 2,164 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

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

how to sort link list of string

Nov 20 '06 #1
9 4373
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
"incredible" <in**************@yahoo.comwrites:
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;}
Nov 20 '06 #3


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):o;}return oO;}

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

Nov 20 '06 #4
Eric Sosman skrev:
* Note: This code uses an OO style.
ROFL!

--
Tor

Nov 20 '06 #5
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):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.
<http://cbfalconer.home.att.net>

Nov 20 '06 #6


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):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
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
Nov 21 '06 #8
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>

Nov 21 '06 #9
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
Nov 21 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Mike | last post by:
Hey guys I am pulling my hair out on this problem!!!!! Any help or ideas or comments on how to make this work I would be grateful! I have been working on this for the past 4 days and nothing I do...
7
by: Stephen | last post by:
I have some code which I call from a custom validator however I seem to have got the logic wrong and im having trouble figuring out how to write my code to get things to work the way I require....
1
by: Jason | last post by:
I've gathered a bunch of data from Active Directory and placed it into a datatable ("ADTable"). I now need to sort and filter this table based on the selection of a drop down list("ddlCategory"). ...
1
by: David Van D | last post by:
Hi there, A few weeks until I begin my journey towards a degree in Computer Science at Canterbury University in New Zealand, Anyway the course tutors are going to be teaching us JAVA wth bluej...
48
by: Alex Chudnovsky | last post by:
I have come across with what appears to be a significant performance bug in ..NET 2.0 ArrayList.Sort method when compared with Array.Sort on the same data. Same data on the same CPU gets sorted a...
2
by: incredible | last post by:
how to merge two sorted link list
1
by: alivip | last post by:
I integrat program to be GUI using Tkinter I try browser direction as you can see # a look at the Tkinter Text widget # use ctrl+c to copy, ctrl+x to cut selected text, # ctrl+v to...
5
by: alivip | last post by:
How can I get every Token (word) and PreviousToken(Previous word) From multube files and frequency of each two word my code is trying to get all single word and double word (every Token (word) and...
3
by: BlueroY | last post by:
hi, I'm working on an exercise, i did a lot of work already and i just can't figure where I'm going wrong, this is what I'm trying to achieve Sample IO...
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.