Sorting a double linked list 
Author Message
 Sorting a double linked list

I'm having problems quicksorting a doubly linked list in c.

The list is already sorted by the first element in a struct on insertion,
but I would like to be able to sort the list following that by the the
second element which is a int.

Essential what I need help with is with swaping the pointers as the code I
have crashes at this pont e.g.

struct report
{
 char field[256];
 int  count;
 struct report *next;
 struct report *prior;

Quote:
}

textlist_entry;

struct report *textlist_start;
struct report *textlist_last;

void textlist_countsort(struct report *left, struct report *right)
{
 int x;
 struct report *i, *j, *temp;

 i = left; j = right;

 x = i->count;

 do
 {
  while(i->count <x && i<right) i = i->prior;
  while(j->count >x && j>left) j = j->prior;

  if(i<=j)
  {
   temp = i;
    // Crashes Here
   i = j;
   j = temp;
   i = i->next;
   j = j->prior;
  }
 }
 while(i<=j);

 if(left<j) textlist_countsort(left, j);
 if(i<right) textlist_countsort(i, right);

Quote:
}

Any help would be greatly appreciated,

Thanks
Ryan



Wed, 04 Sep 2002 03:00:00 GMT  
 Sorting a double linked list

Quote:

> This sounds the best option to me - would be code be a bit more efficent if
> I used an array from scratch?

If you had a choice, probably.  

Quote:
> if so how would I use malloc to increase the
> size of the array?

That's what realloc() is for.

Quote:

> Thanks for all the help everyone.

> /*--------------------------------------*/
> Here's an idea:  Copy your links into an array, then run qsort() on the
> array.  Copy the results back into your linked list without modifying the
> link pointers.  This is the quick way to sort a linked list.
>  Later, Gregory Pietsch
> /*--------------------------------------*/

Later, Gregory Pietsch


Wed, 04 Sep 2002 03:00:00 GMT  
 Sorting a double linked list

Quote:

> I'm having problems quicksorting a doubly linked list in c.

> The list is already sorted by the first element in a struct on insertion,
> but I would like to be able to sort the list following that by the the
> second element which is a int.

> Essential what I need help with is with swaping the pointers as the code I
> have crashes at this pont e.g.

> struct report
> {
>  char field[256];
>  int  count;
>  struct report *next;
>  struct report *prior;
> }
> textlist_entry;

> struct report *textlist_start;
> struct report *textlist_last;

> void textlist_countsort(struct report *left, struct report *right)
> {
>  int x;
>  struct report *i, *j, *temp;

>  i = left; j = right;

>  x = i->count;

>  do
>  {
>   while(i->count <x && i<right) i = i->prior;
>   while(j->count >x && j>left) j = j->prior;

>   if(i<=j)
>   {
>    temp = i;
>     // Crashes Here
>    i = j;
>    j = temp;
>    i = i->next;
>    j = j->prior;
>   }
>  }
>  while(i<=j);

>  if(left<j) textlist_countsort(left, j);
>  if(i<right) textlist_countsort(i, right);
> }

> Any help would be greatly appreciated,

> Thanks
> Ryan

Here's an idea:  Copy your links into an array, then run qsort() on the
array.  Copy the results back into your linked list without modifying
the link pointers.  This is the quick way to sort a linked list.

Later, Gregory Pietsch



Wed, 04 Sep 2002 03:00:00 GMT  
 Sorting a double linked list
This sounds the best option to me - would be code be a bit more efficent if
I used an array from scratch? if so how would I use malloc to increase the
size of the array?

Thanks for all the help everyone.

/*--------------------------------------*/
Here's an idea:  Copy your links into an array, then run qsort() on the
array.  Copy the results back into your linked list without modifying the
link pointers.  This is the quick way to sort a linked list.
 Later, Gregory Pietsch
/*--------------------------------------*/



Wed, 04 Sep 2002 03:00:00 GMT  
 Sorting a double linked list

Quote:

.......
> struct report
> {
>  char field[256];
>  int  count;
>  struct report *next;
>  struct report *prior;
> }
> textlist_entry;

> struct report *textlist_start;
> struct report *textlist_last;

> void textlist_countsort(struct report *left, struct report *right)
> {
>  int x;
>  struct report *i, *j, *temp;

>  i = left; j = right;

>  x = i->count;

>  do
>  {
>   while(i->count <x && i<right) i = i->prior;
>   while(j->count >x && j>left) j = j->prior;

Should both these statement move backward through the list?

- Show quoted text -

Quote:

>   if(i<=j)
>   {
>    temp = i;
>     // Crashes Here
>    i = j;
>    j = temp;
>    i = i->next;
>    j = j->prior;
>   }
>  }
>  while(i<=j);

>  if(left<j) textlist_countsort(left, j);
>  if(i<right) textlist_countsort(i, right);
> }

I havn't worked through your code in detail.
But if member 'prior' of the head of the list
originally is a NULL pointer then you will
at some stage end up attempting to dereference
this NULL pointer. == Crash!

There is no particular order to the pointers;
I think perhaps you should be testing i!=right
and j!=left rather than i<right and j>left

Malcolm Kay



Thu, 05 Sep 2002 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. sorting a double link list

2. Sorting Double Linked List in place

3. link list of a linked list (chained links?)

4. Link-list sort algorithm question

5. basic sort for singly linked list...

6. deleting and sorting items in a linked list

7. sorting of a linked list

8. Linked List Sort/Search/delete code ??Help????

9. Linked list sorting...

10. quick-sorting a linked list?

11. Please Help: Sorting a linked list

12. Sorting on a doubly linked list

 

 
Powered by phpBB® Forum Software