Hello,
My aim is to sort a double linked list.
My understanding is that the sort functions in the standard library sort arrays; to sort a linked list I need to provide my own function/s.
Rather than re-invent the wheel, I found some code that seems to work well.
Sort a Doubly Linked List using Merge Sort - Techie Delight
However the structure of the linked list in their code is as follows;
Code:
struct node
{
int data;
struct node *next, *prev;
};
Whereas the structure of my linked list is as follows;
Code:
struct record
{
int data;
};
typedef struct record record_t;
struct node
{
record_t record;
struct node *next;
struct node *prev;
};
typedef struct node node_t;
struct dll
{
node_t *head;
node_t *tail;
};
typedef struct dll dll_t;
So I'm trying to modify the sample code to work with my data structure which has head/tail pointers.
The issue that I have encountered, is that the sample code accesses the linked list via a double-pointer
e.g. void mergeSort(struct node **head)
Where I access the linked list via a single-pointer
void mergeSort(dll_t *dll)
(e.g. dll->head or dll->tail)
If you compare the two mergesort functions
Original:
Code:
void mergeSort(struct node **head)
{
// base case: 0 or 1 node
if (*head == NULL || (*head)->next == NULL)
return;
// split head into 'a' and 'b' sublists
struct node *a = *head, *b = NULL;
split(*head, &a, &b);
// recursively sort the sub-lists
mergeSort(&a);
mergeSort(&b);
// merge the two sorted lists together
*head = merge(a, b);
}
Attempted port:
Code:
void mergeSort(dll_t *dll)
{
// base case: 0 or 1 node
if (dll->head == NULL || dll->head->next == NULL)
{
return;
}
else
{
// split list into 'a' and 'b' sublists
node_t *a = dll->head, *b = NULL;
node_t **head;
*head = dll->head;
split(*head, &a, &b)
// sort the sub-lists
mergeSort_sublists(&a);
mergeSort_sublists(&b);
// merge the two sorted lists together
*head = merge(a, b);
} // else (more than 1 node)
} //mergeSort
I try to set *head using
Code:
node_t **head;
*head = dll->head;
This causes an abend, so obviously not permitted.
I haven't been able to figure out why this is wrong / how to resolve.
Would appreciate some suggestions
Thanks
VW