singlelist.c

操作系统中的一个例子

    pNodeB = pSingleListB->pHead;
    pPrevA = NULL;

    while ( pNodeB != NULL )
    {
        while ( pNodeA != NULL )
		{
            if ( (*CompareFunc)( pNodeA->pData, pNodeB->pData ) >= 0 )
			{
                SINGLENODE *pNode;
				
				/* 将pNodeB弹出来保存到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的所有数据都大于链表A的数据，
         * 将pSingleListB插入到pSingleListA尾部.
         */
        if ( pNodeA == NULL )
		{
			pSingleListA->pTail->pNext = pNodeB;
			pSingleListA->pTail = pSingleListB->pTail;
			
			break;
		}				
    }
	
    /* 修改pSingleListA的节点总数量 */
    pSingleListA->uCount += pSingleListB->uCount;

	free( pSingleListB );

	return CAPI_SUCCESS;
}


/**	对链表使用归并插入排序，归并和插入排序结合使用，先使用归并排序，
   当链表里面元素数量个数小于一定值时便使用插入排序。
    
	@param	SINGLELIST *pSingleList - 要排序的链表指针	
	@param	COMPAREFUNC CompareFunc - 链表节点比较函数	
	@param	UINT uInsertSortCount - 使用插入排序时的链表节点个数，当链表节点
                                    个数小于这个值时会使用插入排序算法
                                    
	@return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功。	
*/
INT SingleList_MergeSort(SINGLELIST *pSingleList, 
                         COMPAREFUNC CompareFunc, 
                         UINT uInsertSortCount)
{
   	SINGLELIST	 *pSecondList;

    /* 参数校验 */
	if ( pSingleList == NULL || CompareFunc == NULL )
	{
		return CAPI_FAILED;
	}

    if ( pSingleList->uCount < 2 )
    {
        /* 如果节点个数少于两个，认为是已经排好序的 */
        return CAPI_SUCCESS;
    }

    /*
     * 如果链表节点个数小于给定的做插入排序的个数，直接使用插入排序。 
	 */
    if ( pSingleList->uCount <= uInsertSortCount )
	{
		(void)SingleList_InsertSort( pSingleList, CompareFunc );
	}
    else
	{
		/* 将链表劈成两半 */
        pSecondList = SingleList_Split(pSingleList, (pSingleList->uCount) / 2 );
		
        /* 对劈完后的第一个链表进行递归调用归并排序 */
        (void)SingleList_MergeSort( pSingleList, CompareFunc, uInsertSortCount );
		
        /* 对劈完后的第二个链表进行递归调用归并排序 */
		(void)SingleList_MergeSort( pSecondList, CompareFunc, uInsertSortCount );

		/* 将排好序的两个链表合成一个. */
		(void)SingleList_Merge( pSingleList, pSecondList, CompareFunc );
	}

    return CAPI_SUCCESS; 
}

/**	对链表的数据的第uKeyIndex位上的元素进行分类，
    依照它们的大小放入对应的箱子中

	@param	SINGLELIST *pSingleList - 单向链表指针	
	@param	UINT       uRadix - 基数排序的基数，与具体数据类型有关，
                                一般来讲整数的基数为16，字符串的基数最大为255。
	@param	UINT       uKeyIndex - 第多少位	
	@param	SINGLENODE **ppHead - 用来记录头指针的箱子	
	@param	SINGLENODE **ppTail - 记录箱子的尾指针	
	@param	GETKEYFUNC GetKeyFunc - 获取数据的第uKeyIndex位上的元素值	
	@return	void - 无	
*/
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;
        }
    }
}


/**	对基数排序中分好类的箱子进行收集操作，将箱子重新连成一条链表

	@param	SINGLELIST *pSingleList - 单向链表指针	
	@param	UINT        uRadix - 基数	
	@param	SINGLENODE **ppHead - 用来记录头指针的箱子	
	@param	SINGLENODE **ppTail - 记录箱子的尾指针	
	@return	void - 无。
*/
static void SingleList_Collect(SINGLELIST *pSingleList,
                       UINT        uRadix,
                       SINGLENODE **ppHead,
                       SINGLENODE **ppTail )
{
    SINGLENODE  *pHead;
    SINGLENODE  *pTail;
    UINT        uRadixIndex;

    /* 查早第1个非空子表 */
    uRadixIndex = 0;
    while ( uRadixIndex < uRadix )
    {
        if ( ppHead[uRadixIndex] == NULL )
        {
            uRadixIndex++;
            continue;
        }
        else
        {
            break;
        }
    }

    if ( uRadixIndex == uRadix )
    {
        /* 没有找到非空子表 */
        return ;
    }

    pHead = ppHead[uRadixIndex];
    pTail = ppTail[uRadixIndex];

    while ( uRadixIndex < uRadix - 1 )
    {
        /* 继续查找下一个非空子表 */
        ++uRadixIndex;
        if ( ppHead[uRadixIndex] == NULL )
        {
            continue;
        }

        if ( uRadixIndex < uRadix )
        {
            /* 找到了非空子表，需要把它和前一个非空子表链接起来 */
            pTail->pNext = ppHead[uRadixIndex];
            pTail = ppTail[uRadixIndex];
        }
    }

    pSingleList->pHead = pHead;
    pSingleList->pTail = pTail;
}

/**	单向链表的基数排序函数

	@param	SINGLELIST *pSingleList - 单向链表指针	
	@param	UINT uRadix - 基数，字符串如果以单字节为基的话基数为256	
                                整数以10进制计算基数的话，基数为10
	@param	UINT uMaxKeyLen - 关键词的长度，字符串以字节为单位则长度为字符串
                              本身最大可能长度，如果32位整数以16进制为单位的
                              话，则最大长度为8
	@param	GETKEYFUNC GetKeyFunc - 关键词获取回调函数	
	@return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功。	
*/
INT SingleList_RadixSort( SINGLELIST *pSingleList,
                          UINT uRadix,
                          UINT uMaxKeyLen,
                          GETKEYFUNC GetKeyFunc )
{
    SINGLENODE  **ppHead;  /* 用来记录各个箱子头节点的双指针 */
    SINGLENODE  **ppTail;  /* 用来记录各个箱子尾节点的双指针 */
    UINT        i;         /* 临时循环变量 */

    /* 给箱子申请内存 */
    ppHead = (SINGLENODE **)malloc( uRadix * sizeof(SINGLENODE *) );
    ppTail = (SINGLENODE **)malloc( uRadix * sizeof(SINGLENODE *) );
    if ( ppHead == NULL || ppTail == NULL )
    {
        return CAPI_FAILED;
    }

    /* 按顺序对关键字的第i位进行分配和收集操作 */
    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位置上的字符
    获取到的字符会自动转换成大写形式。

	@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位置上的字符
    获取到的字符区分大小写，保持原值不变。

	@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;
}

/**	获取整数的第uKeyIndex位数字，以16进制为单位
    因此获取到的数字最大为0xf，对整数作基数排序时，
    基数为16，最大关键词长度为8

	@param	void *pData - 整数值	
	@param	UINT uKeyIndex - 整数的第多少位	
	@return	UINT - 返回第uKeyIndex位的数字	
*/
UINT GetIntKey( void *pData, UINT uKeyIndex )
{
    UINT    uData;

    if ( uKeyIndex > 8 )
    {
        return 0;
    }

    uData = (UINT)pData;

    uData = (uData >> (uKeyIndex - 1)) & 0xf;

    return uData;   
}