#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)
//定義鏈表申請內(nèi)存不夠時報(bào)錯信息
#define?NO_MEMORY???printf("Error!?Not?enough?memory!/n");exit(1)
//雙向鏈表結(jié)構(gòu)體定義
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;
?
?//初始化頭節(jié)點(diǎn)
?*?pstHead?=?(duNode_t?*)malloc(sizeof(duNode_t));
?(*?pstHead)->pstPrior?=?NULL;
?(*?pstHead)->pstNext?=?NULL;
?if?(?!pstHead?)
?{
??NO_MEMORY;
?}
?pstTmp1?=?*?pstHead;
?//鏈表初始化
?srand(?time(NULL)?);//隨機(jī)數(shù)
????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("鏈表的頭節(jié)點(diǎn)是空/n");
??iRet?=?RET_FAILED;
?}
?else
?{
??while?(?pstTmp?)
??{
???printf("%d?",?pstTmp->data);
???pstTmp?=?pstTmp->pstNext;
??}
??printf("/n");
?}
?return?iRet;
}
/*?刪除包括頭節(jié)點(diǎn)在內(nèi)的所有的節(jié)點(diǎn).?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----------------------------------------------*/
/*
?一趟快速排序的具體做法是：附設(shè)兩個指針low和high(即第一個和最后一個指針),
?他們的初值分別為low和high設(shè)樞軸(一般為low的值pivot)記錄的關(guān)鍵字
?(即本例子中的整形data)為pivot，則首先從high所指位置
?起向前搜索到第一個關(guān)鍵字小于pivot的記錄和樞軸記錄交換，然后從low所指位置起
?向后搜索，找到第一個關(guān)鍵字大于pivot的記錄和樞軸記錄相互交換，重復(fù)這兩步直
?至low?=?high為止。
*/
duNode_t?*?partion(duNode_t?*?pstHead,?duNode_t?*?pstLow,?duNode_t?*?pstHigh)
{
?elemType?iTmp?=?0;
?elemType?pivot?=?0;
?if?(?!pstHead?)
?{
??printf("錯誤，頭節(jié)點(diǎn)為空！/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;//找到最后一個節(jié)點(diǎn)的指針用于快排時
?quick_sort(pstHead,?pstHead->pstNext,?pstHigh);//快排序
?printf("After?sorting:/n");
?showDuList(pstHead);
?destroyList(pstHead);
?pstHead?=?NULL;
}