singlelist.c

操作系统中的一个例子

                    pSingleList->pCur = pNode->pNext;
                }
            }

            /* 释放节点数据和节点占用的内存 */
            if ( DestroyFunc != NULL && pNode->pData != NULL )
            {
                (*DestroyFunc)( pNode->pData );
            }
            free( pNode );

            break;
        }
        pPrevNode = pNode;
        pNode = pNode->pNext;
    }

    return CAPI_SUCCESS;
}


/**	单向链表的获取指定位置数据的函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@param	UINT uIndex - 要获取的索引位置，索引从0开始计算	
	@return	void * - 索引位置节点的数据指针	
*/
void *  SingleList_GetAt( SINGLELIST *pSingleList, UINT uIndex )
{
    UINT        i;
    SINGLENODE  *pNode;

    if ( pSingleList == NULL || pSingleList->uCount >= uIndex )
    {
        return NULL; 
    }

    pNode = pSingleList->pHead;
    for ( i = 0; i < uIndex; i++ )
    {
        pNode = pNode->pNext;
    }

    return pNode->pData;
}


/**	单向链表的获取链表节点数量函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@return	UINT - 链表节点数量，为0表示链表是空的没有节点在链表里面或者参数非法	
*/
UINT    SingleList_GetCount(SINGLELIST *pSingleList)
{
    if ( pSingleList == NULL )
    {
        return 0;
    }
    return pSingleList->uCount;
}


/**	单向链表的获取头节点函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@return	void * - 头节点的数据指针	
*/
void *	SingleList_GetHead( SINGLELIST *pSingleList )
{
    if ( pSingleList == NULL )
    {
        return NULL;
    }

    if ( pSingleList->pHead == NULL )
    {
        return NULL;
    }

    return pSingleList->pHead->pData;
}


/**	单向链表的获取当前节点函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针 	
	@return	void * - 当前节点的数据指针	
*/
void *	SingleList_GetCursor( SINGLELIST *pSingleList )
{
    if ( pSingleList == NULL )
    {
        return NULL;
    }

    if ( pSingleList->pCur == NULL )
    {
        return NULL;
    }

    return pSingleList->pCur->pData;
}


/**	单向链表的获取尾节点函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@return	void * - 尾节点的数据指针	
*/
void * 	SingleList_GetTail( SINGLELIST *pSingleList )
{
    if ( pSingleList == NULL )
    {
        return NULL;
    }

    if ( pSingleList->pTail != NULL )
    {
        return pSingleList->pTail->pData;
    }
    else
    {
        return NULL;
    }
}


/**	单向链表的枚举初始化函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针
	@return	void - 无	
*/
void SingleList_EnumBegin( SINGLELIST *pSingleList )
{
    pSingleList->pCur = pSingleList->pHead;

    return;
}


/**	单向链表枚举下一个节点的函数，第一次调用此函数前必须
    先调用SingleList_EnumBegin()函数

	@param	SINGLELIST *pSingleList - 要操作的单向链表的指针	
	@return	void * - 枚举到的节点数据指针	
*/
void *  SingleList_EnumNext( SINGLELIST *pSingleList )
{
    SINGLENODE  *pCur;

    pCur = pSingleList->pCur;
    if ( pCur != NULL )
    {
        pSingleList->pCur = pCur->pNext;

        return pCur->pData;
    }
    return NULL;
}



/**	单向链表的遍历函数

	@param	SINGLELIST *pSingleList - 要操作单向链表指针	
	@param	TRAVERSEFUNC TraverseFunc - 节点数据的遍历操作函数	
	@return	INT - 成功返回CAPI_SUCCESS，失败返回CAPI_FAILED	
*/
INT SingleList_Traverse( SINGLELIST *pSingleList, TRAVERSEFUNC TraverseFunc )
{
    SINGLENODE  *pNode;

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

    pNode = pSingleList->pHead;
    
    /* 开始遍历链表 */
    while ( pNode != NULL )
    {
        (*TraverseFunc)( pNode->pData ); /* 调用遍历回调函数处理数据 */
        pNode = pNode->pNext;
    }

    return CAPI_SUCCESS;
}


/**	单向链表的插入排序函数
    排序是按照从小到大进行排列，这里说的大小是由CompareFunc来决定的
    因此用户可以通过CompareFunc的返回值设置来决定使用顺序排序或逆序排序

	@param	SINGLELIST *pSingleList - 要操作的单向链表指针	
	@param	COMPAREFUNC CompareFunc - 节点数据比较函数	
	@return	INT - 成功返回CAPI_SUCCESS，失败返回CAPI_FAILED	
*/
INT SingleList_InsertSort( SINGLELIST *pSingleList, COMPAREFUNC CompareFunc )
{
    SINGLENODE  *pNode;     /* 用来遍历pSingleList的临时指针 */
    SINGLENODE  *pPrevNode; /* pNode的前一节点指针 */

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

    pNode = pSingleList->pHead;
    pPrevNode = NULL;

    if ( pNode == NULL )
    {
        /* 链表中没有节点，我们把它当作已经排好了序 */
        return CAPI_SUCCESS;
    }

    while ( pNode->pNext != NULL )
    {
        SINGLENODE  *pTempNode;

        pTempNode = pSingleList->pHead;
        pPrevNode = NULL;
        while ( pTempNode != pNode->pNext )
        {
            if ( (*CompareFunc)( pNode->pNext->pData, pTempNode->pData ) < 0 )
            {
                SINGLENODE  *pCurNode = pNode->pNext;

                /* 执行插入操作 */
                if ( pPrevNode != NULL ) /* 插入不在头节点前的情况 */
                {
                    /* 将pCurNode节点弹出来 */
                    pNode->pNext = pNode->pNext->pNext;

                    /* 将pNode->pNext插入pTempNode 之前 */
                    pPrevNode->pNext = pCurNode;
                    pCurNode->pNext = pTempNode;
                }
                else /* 插入在头节点前的情况 */
                {
                    /* 将pCurNode节点弹出来 */
                    pNode->pNext = pNode->pNext->pNext;

                    /* 将pNode->pNext节点变为头节点 */
                    pSingleList->pHead = pCurNode;
                    pCurNode->pNext = pTempNode;
                }

                /* 修改尾指针指向 */
                if ( pCurNode == pSingleList->pTail )
                {
                    pSingleList->pTail = pNode;
                }

                break;
            }

            pPrevNode = pTempNode;
            pTempNode = pTempNode->pNext;
        } /* while ( pTempNode != pNode->pNext ) */

        if ( pTempNode == pNode->pNext ) /* 没有插入的情况 */
        {
            pNode = pNode->pNext;
        }
        else /* 已经插入的情况 */
        {
            /* 已经插入后不需将pNode指针后移，因为前面操作过程中已经移动过了 */
        }
    }

    return CAPI_SUCCESS;
}


/**	将一个单向链表劈成两个单向链表
    只是从原来链表中间断开，劈完后原链表变成劈开后的第一条链表

	@param	SINGLELIST *pSingleList - 要被劈开的单向链表	
	@param	UINT nCount - 劈开后的第一个链表的节点个数	
	@return	SINGLELIST * - 成功时返回劈开后的第二条链表，失败返回NULL。	
*/
SINGLELIST * SingleList_Split(SINGLELIST *pSingleList, UINT uCount)
{
    SINGLENODE	*pNode;       /* 用来保存劈开处的节点的指针 */
	SINGLELIST  *pSecondList; /* 用来记录劈开后的第二条链表的指针 */
	UINT    	uIndex;       /* 临时循环体变量 */

	if ( pSingleList == NULL )
	{
		return NULL;
	}
	
    /* 参数校验 */
    if ( uCount == 0 || pSingleList->uCount <= uCount)
	{
		return NULL;
	}

    /* 创建一条空链表 */
    pSecondList = SingleList_Create();
    if ( pSecondList == NULL )
    {
        return NULL;
    }

	/* 获取要劈开的位置 */
    pNode = pSingleList->pHead;
    for ( uIndex = 1; uIndex < uCount; uIndex++ )
    {
        pNode = pNode->pNext;
    }
	
	/* 填充第二条链表的内容. */
    pSecondList->pHead = pNode->pNext;
    pSecondList->pTail = pSingleList->pTail;
    pSecondList->uCount = pSingleList->uCount - uCount;

	/* 修改第一条链表的内容. */
    pSingleList->pTail = pNode;
    pSingleList->uCount = uCount;

	/* 将第一条链表尾节点的pNext指针指向NULL */
    pSingleList->pTail->pNext = NULL;

    return pSecondList;
}


/**	将两个已经排好序的链表进行合并
    两个链表都必须是按从小到达进行排列，即尾节点最大
    合并后的链表也是从小到大进行排列

	@param	SINGLELIST *pSingleListA - 要合并的链表	
	@param	SINGLELIST *pSingleListB -要合并的链表	
	@param	COMPAREFUNC CompareFunc - 节点比较函数	
	@return	INT - CAPI_FAILED 表示失败，失败时，参数没有变化
                  CAPI_SUCCESS 表示成功，成功时pSingleListA是合并后的结果，
                  pSingleListB会被释放掉
*/
INT SingleList_Merge(SINGLELIST *pSingleListA, 
                     SINGLELIST *pSingleListB, 
                     COMPAREFUNC CompareFunc)
{
    SINGLENODE	*pNodeA; /* 用来指向链表pSingleListA的节点的临时指针 */
    SINGLENODE  *pNodeB; /* 用来指向链表pSingleListB的节点的临时指针 */
    SINGLENODE  *pPrevA; /* pNodeA的前一节点指针 */

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

    pNodeA = pSingleListA->pHead;