Saturday, July 22, 2017

hellppppp

#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