?? singlelist.c
字號(hào):
pNodeB = pSingleListB->pHead;
pPrevA = NULL;
while ( pNodeB != NULL )
{
while ( pNodeA != NULL )
{
if ( (*CompareFunc)( pNodeA->pData, pNodeB->pData ) >= 0 )
{
SINGLENODE *pNode;
/* 將pNodeB彈出來(lái)保存到pNode中 */
pNode = pNodeB;
pNodeB = pNodeB->pNext;
/* 將pNode插入到pNodeA前面 */
if ( pPrevA == NULL )
{
/* 插入在頭指針前的情況，需要修改頭指針 */
pSingleListA->pHead = pNode;
pNode->pNext = pNodeA;
}
else
{
pPrevA->pNext = pNode;
pNode->pNext = pNodeA;
}
pPrevA = pNode;
break;
}
pPrevA = pNodeA;
pNodeA = pNodeA->pNext;
}
/*
* 如果pSingleListB的所有數(shù)據(jù)都大于鏈表A的數(shù)據(jù)，
* 將pSingleListB插入到pSingleListA尾部.
*/
if ( pNodeA == NULL )
{
pSingleListA->pTail->pNext = pNodeB;
pSingleListA->pTail = pSingleListB->pTail;
break;
}
}
/* 修改pSingleListA的節(jié)點(diǎn)總數(shù)量 */
pSingleListA->uCount += pSingleListB->uCount;
free( pSingleListB );
return CAPI_SUCCESS;
}
/** 對(duì)鏈表使用歸并插入排序，歸并和插入排序結(jié)合使用，先使用歸并排序，
當(dāng)鏈表里面元素?cái)?shù)量個(gè)數(shù)小于一定值時(shí)便使用插入排序。
@param SINGLELIST *pSingleList - 要排序的鏈表指針
@param COMPAREFUNC CompareFunc - 鏈表節(jié)點(diǎn)比較函數(shù)
@param UINT uInsertSortCount - 使用插入排序時(shí)的鏈表節(jié)點(diǎn)個(gè)數(shù)，當(dāng)鏈表節(jié)點(diǎn)
個(gè)數(shù)小于這個(gè)值時(shí)會(huì)使用插入排序算法
@return INT - CAPI_FAILED表示失敗，CAPI_SUCCESS表示成功。
*/
INT SingleList_MergeSort(SINGLELIST *pSingleList,
COMPAREFUNC CompareFunc,
UINT uInsertSortCount)
{
SINGLELIST *pSecondList;
/* 參數(shù)校驗(yàn) */
if ( pSingleList == NULL || CompareFunc == NULL )
{
return CAPI_FAILED;
}
if ( pSingleList->uCount < 2 )
{
/* 如果節(jié)點(diǎn)個(gè)數(shù)少于兩個(gè)，認(rèn)為是已經(jīng)排好序的 */
return CAPI_SUCCESS;
}
/*
* 如果鏈表節(jié)點(diǎn)個(gè)數(shù)小于給定的做插入排序的個(gè)數(shù)，直接使用插入排序。
*/
if ( pSingleList->uCount <= uInsertSortCount )
{
(void)SingleList_InsertSort( pSingleList, CompareFunc );
}
else
{
/* 將鏈表劈成兩半 */
pSecondList = SingleList_Split(pSingleList, (pSingleList->uCount) / 2 );
/* 對(duì)劈完后的第一個(gè)鏈表進(jìn)行遞歸調(diào)用歸并排序 */
(void)SingleList_MergeSort( pSingleList, CompareFunc, uInsertSortCount );
/* 對(duì)劈完后的第二個(gè)鏈表進(jìn)行遞歸調(diào)用歸并排序 */
(void)SingleList_MergeSort( pSecondList, CompareFunc, uInsertSortCount );
/* 將排好序的兩個(gè)鏈表合成一個(gè). */
(void)SingleList_Merge( pSingleList, pSecondList, CompareFunc );
}
return CAPI_SUCCESS;
}
/** 對(duì)鏈表的數(shù)據(jù)的第uKeyIndex位上的元素進(jìn)行分類(lèi)，
依照它們的大小放入對(duì)應(yīng)的箱子中
@param SINGLELIST *pSingleList - 單向鏈表指針
@param UINT uRadix - 基數(shù)排序的基數(shù)，與具體數(shù)據(jù)類(lèi)型有關(guān)，
一般來(lái)講整數(shù)的基數(shù)為16，字符串的基數(shù)最大為255。
@param UINT uKeyIndex - 第多少位
@param SINGLENODE **ppHead - 用來(lái)記錄頭指針的箱子
@param SINGLENODE **ppTail - 記錄箱子的尾指針
@param GETKEYFUNC GetKeyFunc - 獲取數(shù)據(jù)的第uKeyIndex位上的元素值
@return void - 無(wú)
*/
static void SingleList_Distribute(SINGLELIST *pSingleList,
UINT uRadix,
UINT uKeyIndex,
SINGLENODE **ppHead,
SINGLENODE **ppTail,
GETKEYFUNC GetKeyFunc )
{
SINGLENODE *pNode;
UINT i;
/* 初始化子表 */
for ( i = 0; i < uRadix; i++ )
{
ppHead[i] = NULL;
ppTail[i] = NULL;
}
pNode = pSingleList->pHead;
while ( pNode != NULL )
{
UINT uRadixIndex = (*GetKeyFunc)(pNode->pData, uKeyIndex);
if ( ppHead[uRadixIndex] == NULL )
{
ppHead[uRadixIndex] = pNode;
ppTail[uRadixIndex] = pNode;
pNode = pNode->pNext;
ppTail[uRadixIndex]->pNext = NULL;
}
else
{
ppTail[uRadixIndex]->pNext = pNode;
ppTail[uRadixIndex] = ppTail[uRadixIndex]->pNext;
pNode = pNode->pNext;
ppTail[uRadixIndex]->pNext = NULL;
}
}
}
/** 對(duì)基數(shù)排序中分好類(lèi)的箱子進(jìn)行收集操作，將箱子重新連成一條鏈表
@param SINGLELIST *pSingleList - 單向鏈表指針
@param UINT uRadix - 基數(shù)
@param SINGLENODE **ppHead - 用來(lái)記錄頭指針的箱子
@param SINGLENODE **ppTail - 記錄箱子的尾指針
@return void - 無(wú)。
*/
static void SingleList_Collect(SINGLELIST *pSingleList,
UINT uRadix,
SINGLENODE **ppHead,
SINGLENODE **ppTail )
{
SINGLENODE *pHead;
SINGLENODE *pTail;
UINT uRadixIndex;
/* 查早第1個(gè)非空子表 */
uRadixIndex = 0;
while ( uRadixIndex < uRadix )
{
if ( ppHead[uRadixIndex] == NULL )
{
uRadixIndex++;
continue;
}
else
{
break;
}
}
if ( uRadixIndex == uRadix )
{
/* 沒(méi)有找到非空子表 */
return ;
}
pHead = ppHead[uRadixIndex];
pTail = ppTail[uRadixIndex];
while ( uRadixIndex < uRadix - 1 )
{
/* 繼續(xù)查找下一個(gè)非空子表 */
++uRadixIndex;
if ( ppHead[uRadixIndex] == NULL )
{
continue;
}
if ( uRadixIndex < uRadix )
{
/* 找到了非空子表，需要把它和前一個(gè)非空子表鏈接起來(lái) */
pTail->pNext = ppHead[uRadixIndex];
pTail = ppTail[uRadixIndex];
}
}
pSingleList->pHead = pHead;
pSingleList->pTail = pTail;
}
/** 單向鏈表的基數(shù)排序函數(shù)
@param SINGLELIST *pSingleList - 單向鏈表指針
@param UINT uRadix - 基數(shù)，字符串如果以單字節(jié)為基的話基數(shù)為256
整數(shù)以10進(jìn)制計(jì)算基數(shù)的話，基數(shù)為10
@param UINT uMaxKeyLen - 關(guān)鍵詞的長(zhǎng)度，字符串以字節(jié)為單位則長(zhǎng)度為字符串
本身最大可能長(zhǎng)度，如果32位整數(shù)以16進(jìn)制為單位的
話，則最大長(zhǎng)度為8
@param GETKEYFUNC GetKeyFunc - 關(guān)鍵詞獲取回調(diào)函數(shù)
@return INT - CAPI_FAILED表示失敗，CAPI_SUCCESS表示成功。
*/
INT SingleList_RadixSort( SINGLELIST *pSingleList,
UINT uRadix,
UINT uMaxKeyLen,
{
SINGLENODE **ppHead; /* 用來(lái)記錄各個(gè)箱子頭節(jié)點(diǎn)的雙指針 */
SINGLENODE **ppTail; /* 用來(lái)記錄各個(gè)箱子尾節(jié)點(diǎn)的雙指針 */
UINT i; /* 臨時(shí)循環(huán)變量 */
/* 給箱子申請(qǐng)內(nèi)存 */
ppHead = (SINGLENODE **)malloc( uRadix * sizeof(SINGLENODE *) );
ppTail = (SINGLENODE **)malloc( uRadix * sizeof(SINGLENODE *) );
if ( ppHead == NULL || ppTail == NULL )
{
return CAPI_FAILED;
}
/* 按順序?qū)﹃P(guān)鍵字的第i位進(jìn)行分配和收集操作 */
for ( i = 0; i < uMaxKeyLen; i++ )
{
SingleList_Distribute(pSingleList, uRadix, i, ppHead, ppTail, GetKeyFunc);
SingleList_Collect(pSingleList, uRadix, ppHead, ppTail);
}
/* 釋放分配的箱子 */
free( ppHead );
free( ppTail );
return CAPI_SUCCESS;
}
/** 獲取字符串的第uKeyIndex位置上的字符
獲取到的字符會(huì)自動(dòng)轉(zhuǎn)換成大寫(xiě)形式。
@param void *pszData - 指向字符串的指針
@param UINT uKeyIndex - 表示第多少位，位置是從后向前算
@return UINT - 返回第uKeyIndex位的字符值
*/
UINT GetStrKeyNoCase( void *pszData, UINT uKeyIndex )
{
char *psz = (char *)pszData;
UINT uKey;
if ( psz == NULL || (*psz) == '\0' )
{
return 0;
}
if ( uKeyIndex >= strlen(psz) )
{
return 0;
}
uKey = strlen(psz) - uKeyIndex - 1;
if( psz[uKey] >= 'a' && psz[uKey] <= 'z' )
{
uKey = (UINT)(unsigned char)(psz[uKey] - 'a' + 'A');
}
else
{
uKey = (UINT)(unsigned char)(psz[uKey]);
}
return uKey;
}
/** 獲取字符串的第uKeyIndex位置上的字符
獲取到的字符區(qū)分大小寫(xiě)，保持原值不變。
@param void *pszData - 指向字符串的指針
@param UINT uKeyIndex - 表示第多少位，位置是從后向前算
@return UINT - 返回第uKeyIndex位的字符值
*/
UINT GetStrKey( void *pszData, UINT uKeyIndex )
{
char *psz = (char *)pszData;
UINT uKey;
if ( psz == NULL || (*psz) == '\0' )
{
return 0;
}
if ( uKeyIndex >= strlen(psz) )
{
return 0;
}
uKey = strlen(psz) - uKeyIndex - 1;
uKey = (UINT)(unsigned char)(psz[uKey]);
return uKey;
}
/** 獲取整數(shù)的第uKeyIndex位數(shù)字，以16進(jìn)制為單位
因此獲取到的數(shù)字最大為0xf，對(duì)整數(shù)作基數(shù)排序時(shí)，
基數(shù)為16，最大關(guān)鍵詞長(zhǎng)度為8
@param void *pData - 整數(shù)值
@param UINT uKeyIndex - 整數(shù)的第多少位
@return UINT - 返回第uKeyIndex位的數(shù)字
*/
UINT GetIntKey( void *pData, UINT uKeyIndex )
{
UINT uData;
if ( uKeyIndex > 8 )
{
return 0;
}
uData = (UINT)pData;
uData = (uData >> (uKeyIndex - 1)) & 0xf;
return uData;
}
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -