双向链表的快速排序

逃离我推掉我的手 2022-06-10 09:15 178阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    //定义类型 所有的排序例子中都是用的int作为data
    typedef int elemType;     
    //返回值
    #define RET_SUCCESS   ( 1  ) 
    #define RET_FAILED   ( 0  )  
    //定义链表的长度
    #define  LIST_MAX_SIZE      (10)
    //定义链表申请内存不够时报错信息
    #define NO_MEMORY   printf("Error! Not enough memory!/n");exit(1)
    //双向链表结构体定义
    typedef struct tagDuNode_t
    {
     elemType data;     
     struct tagDuNode_t * pstNext; 
     struct tagDuNode_t * pstPrior;
    }duNode_t;
    //初始化双向链表
    int initDuList(duNode_t ** pstHead)
    {
     int iRet = RET_SUCCESS;
     int iCir = 0;
     duNode_t * pstTmp1 = NULL;
     duNode_t * pstTmp2 = NULL;
     
     //初始化头节点
     * pstHead = (duNode_t *)malloc(sizeof(duNode_t));
     (* pstHead)->pstPrior = NULL;
     (* pstHead)->pstNext = NULL;
     if ( !pstHead )
     {
      NO_MEMORY;
     }
     pstTmp1 = * pstHead;
     //链表初始化
     srand( time(NULL) );//随机数
        for( iCir = 0; iCir < LIST_MAX_SIZE; iCir++ )
     {
      pstTmp2 = (duNode_t *)malloc(sizeof(duNode_t));
      if ( !pstTmp2 )
      {
       NO_MEMORY;
      }
      //赋初值
      pstTmp2->data = rand() % LIST_MAX_SIZE;
      pstTmp2->pstNext = NULL;
      pstTmp1->pstNext = pstTmp2;
      pstTmp2->pstPrior = pstTmp1;
      pstTmp1 = pstTmp2;
     } 
     return iRet;
    }
    // 打印链表 链表的data元素是可打印的整形    
    int showDuList(duNode_t * pstHead)
    {
     int iRet = RET_SUCCESS;
     duNode_t * pstTmp = pstHead->pstNext;
     if ( NULL == pstHead )
     {
      printf("链表的头节点是空/n");
      iRet = RET_FAILED;
     }
     else
     {
      while ( pstTmp )
      {
       printf("%d ", pstTmp->data);
       pstTmp = pstTmp->pstNext;
      }
      printf("/n");
     }
     return iRet;
    }
    /* 删除包括头节点在内的所有的节点. 07/04/28  */
    int destroyList(duNode_t * pstHead)
    {
     duNode_t * pstTmp = NULL;   /* Temp pointer for circle  */
     int iRet = RET_SUCCESS;
     if ( !pstHead )
     {
      printf("Error! pstHead is null/n");
      iRet = RET_FAILED;
     }
     else
     {
      while ( pstHead )  /* Free  nodes      */
      {
       pstTmp = pstHead;
       pstHead = pstHead->pstNext;
       free(pstTmp);
      }
      pstHead = NULL;
     }
     return iRet;
    }/* End of destroyList----------------------------------------------*/
    //正确的快速排序 2007/05/09
    /*
     一趟快速排序的具体做法是：附设两个指针low和high(即第一个和最后一个指针),
     他们的初值分别为low和high设枢轴(一般为low的值pivot)记录的关键字
     (即本例子中的整形data)为pivot，则首先从high所指位置
     起向前搜索到第一个关键字小于pivot的记录和枢轴记录交换，然后从low所指位置起
     向后搜索，找到第一个关键字大于pivot的记录和枢轴记录相互交换，重复这两步直
     至low = high为止。
    */
    duNode_t * partion(duNode_t * pstHead, duNode_t * pstLow, duNode_t * pstHigh)
    {
     elemType iTmp = 0;
     elemType pivot = 0;
     if ( !pstHead )
     {
      printf("错误，头节点为空！/n");
      exit(1);
     }
     if ( !pstHead->pstNext )
     {
      return pstHead->pstNext;//就一个元素
     } 
     pivot = pstLow->data;
     while ( pstLow != pstHigh )
     {
      //从后面往前换
      while ( pstLow != pstHigh && pstHigh->data >= pivot )
      {
       pstHigh = pstHigh->pstPrior;
      }
      //交换high low
      iTmp = pstLow->data;
      pstLow->data = pstHigh->data;
      pstHigh->data = iTmp;
      //从前往后换
      while ( pstLow != pstHigh && pstLow->data <= pivot )
      {
       pstLow = pstLow->pstNext;
      }
      //交换high low
      iTmp = pstLow->data;
      pstLow->data = pstHigh->data;
      pstHigh->data = iTmp;
     }
     return pstLow;
    }
    //快排
    void quick_sort(duNode_t * pstHead, duNode_t * pstLow, duNode_t * pstHigh)
    {
     duNode_t * pstTmp = NULL;
     pstTmp = partion(pstHead, pstLow, pstHigh);
     if ( pstLow != pstTmp )
     {
      quick_sort(pstHead, pstLow, pstTmp->pstPrior);
     }
     if ( pstHigh != pstTmp )
     {
      quick_sort(pstHead, pstTmp->pstNext, pstHigh);
     }
     
    }
    void main()
    {
     duNode_t * pstHead = NULL;
     duNode_t * pstHigh = NULL;
     duNode_t * pstTmp = NULL;
     initDuList(&pstHead);   //初始化
     printf("Before sorting:/n");
     showDuList(pstHead);   //打印
     pstTmp = pstHead->pstNext;
     while ( pstTmp->pstNext )
     {
      pstTmp = pstTmp->pstNext;
     }
     pstHigh = pstTmp;//找到最后一个节点的指针用于快排时
     quick_sort(pstHead, pstHead->pstNext, pstHigh);//快排序
     printf("After sorting:/n");
     showDuList(pstHead);
     destroyList(pstHead);
     pstHead = NULL;
    }