双向链表排序

 
双向链表排序  2006-10-11
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

typedef struct Node
{
 int data;
 struct Node* left;
 struct Node* right;
}Node;

//创建一个双向链表, 输入整数，以-1作为结束
Node* CreateDLinkList()
{
 int data;
 Node* pNewNode;
 Node* pHead = NULL;
 Node* pLast = NULL;

 while(1)
 {
  scanf("%d",&data);
  if(-1 == data)
   break;
  pNewNode = (Node*)malloc(sizeof(Node));
  if(!pNewNode)
  {
   fprintf(stderr,"no memory");
   exit(1);
  }
  pNewNode->data = data;
  pNewNode->left = pNewNode->right = NULL;
  if(NULL == pLast)
  {
   pHead = pLast = pNewNode;
  }
  else
  {
   pLast->right = pNewNode;
   pNewNode->left = pLast;
   pLast = pNewNode;
  }  
 }
 return pHead;
}

//遍历
void TravelDLinkList(Node* pHead)
{
 while(NULL != pHead)
 {
  printf("%d ",pHead->data);
  pHead = pHead->right;
 }
 printf("\n");
}

//销毁一个双向链表
void DestroyDLinkList(Node* pHead)
{
 Node* pNext;

 while(NULL != pHead)
 {
  pNext = pHead->right;
  free(pHead);
  pHead = pNext;
 }
}

Node* InsertListNodeToTree(Node* T, Node* newNode)
{
 if(NULL == T)
  return newNode;
 if(newNode->data <= T->data)
  T->left = InsertListNodeToTree(T->left,newNode);
 else
  T->right = InsertListNodeToTree(T->right,newNode);
 return T;
}

//给一个双向链表，利用其存储空间，构建一个二叉排序树
Node* ListToTree(Node* head)
{
 Node* root = NULL;
 Node* pNext;

 while(NULL != head)
 {
  pNext = head->right;
  head->left = head->right = NULL;
  root = InsertListNodeToTree(root, head); 
  head = pNext;
 }
 return root;
}

//实现一个堆栈
#define INIT_SIZE 10
#define INCREMENT_SIZE 5

typedef struct _Stack
{
 Node** base;
 Node** top;
 int stacksize;
}Stack;

//init a stack
void InitStack(Stack* s)
{
 assert(s);
 s->stacksize = INIT_SIZE;
 s->base = s->top = (Node**)malloc(s->stacksize*sizeof(Node*)); 
}
void Push(Stack* s, Node* T)
{
 if(s->top - s->base >= s->stacksize)
 {
  s->base = (Node**)realloc(s->base, (s->stacksize+INCREMENT_SIZE)*sizeof(Node*));
  s->top = s->base + s->stacksize;
  s->stacksize += INCREMENT_SIZE;
 }
 *(s->top) = T;
 s->top ++;
}

Node* Pop(Stack* s)
{
 if(s->base == s->top)
  return NULL;
 s->top --;
 return *(s->top);
}

Node* GetTop(Stack* s)
{
 if(s->base == s->top)
  return NULL; 
 return *(s->top-1);
}

bool isEmpty(Stack* s)
{
 if(s->top  == s->base)
  return true;
 else
  return false;
}

void DestroyStack(Stack* s)
{
 if(s->base)
  free(s->base);
}

//将一个二叉排序树，以中序遍历的形式转化为一个双向链表
Node* TreeToList(Node* T)
{
 Stack s;

 Node* pFirst = NULL;
 Node* pLast = NULL;

 InitStack(&s);

 if(NULL == T)
  return NULL; 
 Push(&s,T);

 while(!isEmpty(&s))
 {
  T = GetTop(&s); 
  if(NULL != T)
  {
   while(T->left)
   {
    Push(&s,T->left);
    T = T->left;
   }
  }
  else
  {
   Pop(&s);  
  }
  
  if(!isEmpty(&s))
  {
   T = Pop(&s);  
      
   if(NULL==pLast)
   {
    pFirst = pLast = T;
    T->left = NULL;
   }
   else
   {
    pLast->right = T;
    T->left = pLast;
    pLast = T;
   }
   Push(&s,T->right); 
  }  
 }
 if(NULL != pLast)
  pLast->right = NULL;
 
 DestroyStack(&s);
 return pFirst;
}

//对双向链表排序
/*
 1. 将双向链表改为二叉排序树
 2. 中序遍历二叉排序树，改为双向链表 
 */
Node* DLinkSort(Node* pHead)
{
 Node* pTree;
 pTree = ListToTree(pHead); 
 pHead = TreeToList(pTree);
 return pHead;
}
int main(int argc, char** argv)
{
 Node* pHead;
 
 pHead = CreateDLinkList();
 
 TravelDLinkList(pHead);

 pHead = DLinkSort(pHead);
 TravelDLinkList(pHead);
 
 De