2011年1月24日 星期一

Reverse a single linked list - 反轉一個串列

#include <stdio.h>
/*************************************************************
 * Struct definition
 *************************************************************/

typedef struct{
 void *next;
 int v;
}item_t;
/*************************************************************
 * Global variable
 *************************************************************/
item_t *Head;
/*************************************************************
 * Function decalaration
 *************************************************************/
int   list_add(int);
void   list_init(int);
item_t* list_reverse(item_t *);
int   list_print();
item_t *list_tail();
void list_remove();
/*************************************************************
 * Entry point
 *************************************************************/
int main(){
 list_init(9);
 list_add(1);
 list_add(7);
 list_add(5);
 list_print();  //9,1,7,5
 Head = list_reverse(Head);
 list_print();  //5,7,1,9
 list_add(6);
 list_add(9);
 list_print();  //5,7,1,9,6,9
 Head = list_reverse(Head);
 list_print();  //9,6,9,1,7,5
 list_remove();
 return 0;
}

/*************************************************************
 * list_init()
 *************************************************************/
void list_init(int value){
 Head = malloc(sizeof(item_t));
 Head->v = value;
 Head->next = NULL;
}
/*************************************************************
 * list_add()
 *************************************************************/
int list_add(int value){
 item_t *p,*tail;
 p = malloc(sizeof(item_t));
 if(p){
  p->v = value;
  p->next = NULL;
  tail=list_tail();
  tail->next=p;
  return 0;
 }else{
  return -1;
 }
}
/*************************************************************
 * list_tail()
 *************************************************************/
item_t *list_tail(){
 item_t *c;
 c = Head;
 while( c->next != NULL ){
   c = c->next;
 }
 //printf("last item is %d\n",c->v);
 return c;
}
/*************************************************************
 * list_reverse()
 *************************************************************/
item_t* list_reverse(item_t *head){
 item_t *p,*c,*n;

 p = NULL;
 c = head;
 n = c->next;
 while( c != NULL ){
  n = c->next;
  c->next = p;
  p = c;
  c = n;
 }
 return p;
}
/*************************************************************
 * list_print()
 *************************************************************/
int list_print(){
 int count=0;//calculate total items in list
 item_t *p = Head;
 if( p == NULL){
   printf("ERR:Head is NULL\n");
   return -1;
 }
 while(p!=NULL){
  count++;
  printf("%d\n",p->v);
  p = p->next;
 }
 printf("total items=%d\n",count);
return 0;
}
/*************************************************************
 * list_remove()
 *************************************************************/
void list_remove(){
 item_t *c,*t;
 c = Head;
 while( c->next != NULL ){
  t = c;
  c = c->next;
  free(t);
 }
}