Code:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
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;
// function to add a node at the tail of a doubly linked list
void add_tail(dll_t *dll, record_t *record)
{
node_t *node = malloc(sizeof(*node));
if (node == NULL)
{
printf("Malloc failed in: add_tail: node\n");
getchar();
}
node->record = *record;
node->next = NULL;
node->prev = NULL;
if ( dll->tail == NULL )
{
// first node
dll->head = dll->tail = node;
}
else
{
// insert additional nodes at the tail
node_t *curr = dll->tail;
dll->tail = node;
node->prev = curr;
curr->next = node;
}
} // add_tail
// function to remove head node from list
void remove_head(dll_t *dll)
{
node_t *curr = dll->head;
// walk through list
while (curr != NULL)
{
// handle first item
if (curr->prev == NULL)
{
if (curr->next == NULL)
{
// only item?
dll->head = NULL;
dll->tail = NULL;
}
else
{
// more items?
dll->head = curr->next;
dll->head->prev = NULL;
}
free(curr);
}
// Only process a single node
break;
}
} // remove_head
// Helper function to print nodes of a doubly linked list
void printDLL_fwd(dll_t *dll)
{
printf("Forward\n");
node_t *curr = dll->head;
while (curr != NULL)
{
printf("%d -> ", curr->record.data);
curr = curr->next;
}
printf("null\n\n");
} //printDLL_fwd
void printDLL_rev(dll_t *dll)
{
printf("Reverse\n");
node_t *curr = dll->tail;
while (curr != NULL)
{
printf("%d -> ", curr->record.data);
curr = curr->prev;
}
printf("null\n\n");
} // printDLL_rev
void split(dll_t *original_list, dll_t *split_list)
{
// Initialise record
record_t record;
// Copy head record from original list
record = original_list->head->record;
// Remove head record from original list
remove_head(original_list);
// Add record to split_list
add_tail(split_list, &record);
} // split
void merge(dll_t *original_list, dll_t *list_a, dll_t *list_b)
{
// Initialise record
record_t record;
while ( (list_a->head != NULL) || (list_b->head != NULL) )
{
// if list_b is empty
if (list_b->head == NULL)
{
// read record from list_a (head)
record = list_a->head->record;
// remove record from list_a
remove_head(list_a);
// add record to original_list
add_tail(original_list,&record);
}
// if list_a is empty
else if (list_a->head == NULL)
{
// read record from list_b (head)
record = list_b->head->record;
// remove record from list_b
remove_head(list_b);
// add record to original_list
add_tail(original_list,&record);
}
else
// list_a and list_b both have records
{
if (list_a->head->record.data < list_b->head->record.data)
{
// read record from list_a (head)
record = list_a->head->record;
// remove record from list_a
remove_head(list_a);
// add record to original_list
add_tail(original_list,&record);
}
else
{
// read record from list_b (head)
record = list_b->head->record;
// remove record from list_b
remove_head(list_b);
// add record to original_list
add_tail(original_list,&record);
}
} // else
} // While list_a is not empty and list_b is not empty
} //merge
// Function to sort a doubly linked list using merge sort algorithm
void mergeSort(dll_t *dll)
{
// if list empty
if ( (dll->head == NULL) && (dll->tail == NULL) )
{
// do nothing
return;
}
// if list has one node
if ( dll->head == dll->tail )
{
// do nothing
return;
}
// Initialise two "worker" lists
dll_t list_a;
list_a.head = list_a.tail = NULL;
dll_t list_b;
list_b.head = list_b.tail = NULL;
// while the original_list is not empty - split items into two lists: list_a and list_b;
while(dll->head != NULL)
{
// remove item from original list - add to list_a
split(dll, &list_a);
// if original list still not empty, remove item from original list - add to list_b
if(dll->head != NULL)
{
split(dll, &list_b);
}
} // while original_list is not empty
// Sort each "worker" list
mergeSort(&list_a);
mergeSort(&list_b);
// Merge two "worker" lists together in order
merge(dll,&list_a,&list_b);
} //mergeSort
int main(void)
{
int keys[] = { 6, 4, 5, 8, 7, 9, 5, 2, 1 };
int n = sizeof(keys)/sizeof(keys[0]);
// Initialise list
dll_t dll;
dll.head = dll.tail = NULL;
record_t record;
record.data = 0;
// add records
for (int i = 0; i < n; i++)
{
record.data = keys[i];
add_tail(&dll, &record);
}
printf("Before\n");
printf("------\n");
printDLL_fwd(&dll);
printDLL_rev(&dll);
mergeSort(&dll);
printf("After\n");
printf("-----\n");
printDLL_fwd(&dll);
printDLL_rev(&dll);
return 0;
}