#include <stdio.h>
#include <stdlib.h>
// List element: a list is a chain of these
typedef struct element
{
int val;
struct element* next;
} element_t;
// List header - keep track of the first and last list elements
typedef struct list
{
element_t* head;
element_t* tail;
} list_t;
list_t* list_create( void )
{
list_t* l = malloc( sizeof(list_t) );
if(l){
l->head = NULL;
l->tail = NULL;
}
}
void list_destroy( list_t* list )
{
element_t* el = list->head;
while( el )
{
element_t* next = el->next;
free( el );
el = next;
}
free( list );
}
element_t* element_create( int i )
{
element_t* el = malloc( sizeof(element_t) );
if( el )
{
el->val = i;
el->next = NULL;
}
return el;
}
int list_append( list_t* list, int i )
{
element_t* el = element_create( i );
if( el == NULL )
return 1;
if( list->head == NULL )
list->head = el;
if( list->tail )
list->tail->next = el;
list->tail = el;
return 0;
}
int list_prepend( list_t* list, int i )
{
element_t* el = element_create( i );
if( el == NULL )
return 1;
if( list->tail == NULL )
list->tail = el;
if( list->head )
el->next = list->head;
list->head = el;
return 0;
}
element_t* list_index( list_t* list, unsigned int i )
{
if( list->head == NULL )
return NULL;
element_t* el = list->head;
unsigned int now = 0;
while( now < i )
{
if( el->next == NULL )
return NULL;
now++;
el = el->next;
}
return el;
}
int arrLength(list_t* list)
{
if(list->head == NULL) return 0;
element_t* el = list->head;
int num = 1;
while(el->next != NULL){
num++;
el = el->next;
}
return num;
}
void swap(list_t* list, int i, int j)
{
int x;
x = list_index(list, i)->val;
list_index(list, i)->val = list_index(list, j)->val;
list_index(list, j)->val = x;
}
int partition(list_t* list, int low, int high)
{
int pivot = list_index(list, low)->val;
int i = low; int j = high;
while(1){
do i++; while((i<high) &&(list_index(list, i)->val <= pivot) );
do j--; while(list_index(list, j)->val > pivot);
if( i>=j )break;
swap(list, i, j);
}
swap(list, low, j);
return j;
}
void quicksort(list_t* list, int low, int high)
{
if(low<high){
int pivot = partition(list, low, high);
quicksort(list, low, pivot-1);
quicksort(list, pivot+1, high);
}
}
void list_sort(list_t* list)
{
int n = arrLength(list)-1;
quicksort(list, 0, n);
}
int main()
{
list_t* list = list_create();
list_append(list, 3);
list_append(list, 2);
list_append(list, 8);
list_append(list, 5);
list_append(list, 7);
list_sort(list);
return 0;
}
No comments:
Post a Comment