?? singlelist.c

?? 多任務下的數據結構和算法這本書的全部源代碼
?? C
?? 第 1 頁 / 共 3 頁
字號:
12 3 下一頁
/*
 * Copyright (c) 2000-2008
 * Author: Weiming Zhou
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  
 */

#include <stdlib.h>
#include <string.h>
#include "CapiGlobal.h"
#include "SingleList.h"

 
/**	單向鏈表的創建函數，創建完后鏈表還是空的沒有節點在里面

	@param	void - 無	
	@return	SINGLELIST * - 失敗返回NULL, 成功時返回一個單向鏈表結構體指針	
*/
SINGLELIST * SingleList_Create( void )
{
    SINGLELIST  *pSingleList;

    /* 分配內存操作 */
    pSingleList = (SINGLELIST *)malloc(sizeof(SINGLELIST));
    if ( pSingleList != NULL )
    {
        /* 初始化鏈表結構體各指針成員為空，鏈表節點個數為0 */
        pSingleList->pCur = NULL;
        pSingleList->pHead = NULL;
        pSingleList->pTail = NULL;
        pSingleList->uCount = 0;
    }

    return pSingleList;
}


/**	單向鏈表的釋放函數

	@param	SINGLELIST *pSingleList - 要釋放的單向鏈表的指針	
	@param	DESTROYFUNC pDestroyFunc - 鏈表節點數據釋放回調函數	
	@return	void - 無	
*/
void SingleList_Destroy( SINGLELIST *pSingleList, DESTROYFUNC DestroyFunc )
{
    SINGLENODE  *pNode;

    if ( pSingleList )
    {
        /* 從頭節點開始，一個接一個釋放鏈表節點及節點數據 */
        pNode = pSingleList->pHead;
        while ( pNode != NULL )
        {
            SINGLENODE  *pDelNode;

            pDelNode = pNode;
            pNode = pNode->pNext;

            if ( DestroyFunc != NULL && pDelNode->pData != NULL )
            {
                /* 釋放數據 */
                (*DestroyFunc)( pDelNode->pData );
            }
            free( pDelNode ); /* 釋放節點 */
        }
        /* 釋放鏈表結構體 */ 
        free( pSingleList );
    }
}


/**	單向鏈表的添加節點函數，添加的節點放在單向鏈表的頭部

	@param	SINGLELIST *pSingleList - 要添加的單向鏈表指針	
	@param	void *pData - 要添加的節點的數據指針	
	@return	INT - 失敗返回CAPI_FAILED，成功返回CAPI_SUCCESS	
*/
INT	SingleList_InsertHead( SINGLELIST *pSingleList, void *pData )
{
    SINGLENODE  *pNode;

    /* 參數校驗 */
    if ( pSingleList == NULL || pData == NULL )
    {
        return CAPI_FAILED;
    }

    /* 新建一個節點 */
    pNode = (SINGLENODE *)malloc( sizeof(SINGLENODE) );
    if ( pNode == NULL )
    {
        return CAPI_FAILED;
    }
    pNode->pData = pData;  /* 將節點數據指針指向傳進來的數據 */

    /* 將新建節點的下一節點指針指向頭節點，并將頭節點改為新建的節點 */
    pNode->pNext = pSingleList->pHead;
    pSingleList->pHead = pNode;

    /*
     * 判斷是否尾節點指針為空，如果為空表示原來鏈表中沒有節點，
     * 此時應該將尾節點指向新加入的節點 
     */
    if ( pSingleList->pTail == NULL )
    {
        pSingleList->pTail = pNode;
    }

    /* 將鏈表節點數據加1 */
    pSingleList->uCount++;
    
    return CAPI_SUCCESS;
}


/**	單向鏈表的添加節點函數，添加的節點放在單向鏈表的尾部

	@param	SINGLELIST *pSingleList - 要添加的單向鏈表指針	
	@param	void *pData - 要添加的節點的數據指針
	@return	INT - 失敗返回CAPI_FAILED，成功返回CAPI_SUCCESS	
*/
INT	SingleList_InsertTail( SINGLELIST *pSingleList, void *pData )
{
    SINGLENODE  *pNode;

    /* 參數校驗 */
    if ( pSingleList == NULL || pData == NULL )
    {
        return CAPI_FAILED;
    }

    /* 新建一個節點 */
    pNode = (SINGLENODE *)malloc( sizeof(SINGLENODE) );
    if ( pNode == NULL )
    {
        return CAPI_FAILED;
    }
    pNode->pData = pData;  /* 將節點數據指針指向傳進來的數據 */
    pNode->pNext = NULL;   /* 將節點的下一節點賦為空指針NULL */

    /*
     * 判斷是否尾節點指針為空，如果為空表示原來鏈表中沒有節點，
     * 此時應該將尾節點指向新加入的節點, 并且頭節點指針也應該指向新節點 
     */
    if ( pSingleList->pTail == NULL )
    {
        pSingleList->pTail = pNode;
        pSingleList->pHead = pNode;
    }
    else
    {
        /*
         * 如果尾節點指針不為空，此時應該將尾節點下一節點指針指向新加入的節點, 
         * 并且尾節點指針也應該指向新節點 
         */
        pSingleList->pTail->pNext = pNode;
        pSingleList->pTail = pNode;
    }

    /* 將鏈表節點數據加1 */
    pSingleList->uCount++;
    
    return CAPI_SUCCESS;
}


/**	單向鏈表的彈出頭節點函數

	@param	SINGLELIST *pSingleList - 要操作的單向鏈表指針	
	@return	void * - 失敗返回NULL, 成功返回要彈出的頭節點的數據指針	
*/
void *	SingleList_PopHead( SINGLELIST *pSingleList )
{
	SINGLENODE	*pPopNode;   /* 用來指向要彈出數據的節點的指針 */
	void		*pPopData;   /* 用來指向要彈出的數據的指針 */

    /* 參數校驗 */
    if ( pSingleList == NULL || pSingleList->pHead == NULL ) 
    {
		return NULL;
    }

    /* 將要彈出數據的節點指針指向鏈表頭節點，彈出數據指針指向頭節點的數據 */
    pPopNode = pSingleList->pHead;
    pPopData = pPopNode->pData;

    /* 
     * 判斷當前節點指針是否指向頭節點，如果指向頭節點的話則需要將其
     * 指向頭節點的下一節點 
     */
    if ( pSingleList->pCur == pSingleList->pHead )
    {
        pSingleList->pCur = pSingleList->pHead->pNext;
    }

    /* 將頭節點指針指向頭節點的下一節點 */
    pSingleList->pHead = pSingleList->pHead->pNext;
	
    /* 將鏈表節點數量減1 */
    pSingleList->uCount--;

    /* 如果鏈表的節點數量已經為0則表示原來只有一個節點，彈出頭節點后，
     * 此時鏈表已經為空，沒有節點在里面，此時應該將尾節點指針賦空
     * 當前節點指針由于前面已經處理過了，如果只有一個節點的話肯定為空
     * 所以這里不需要處理當前節點指針
     */
    if ( pSingleList->uCount == 0 ) {
		pSingleList->pTail = NULL;
	}
	
    /* 釋放彈出的節點, 注意這里并沒有釋放節點數據指針 */
    free( pPopNode );

    return pPopData;    /* 返回頭節點的數據指針 */
}


/** 單向鏈表的彈出尾節點函數
    這個函數由于要查找尾節點的前一節點，因此效率很低

    @param	SINGLELIST *pSingleList - 要操作的單向鏈表指針	
    @return	void * -  失敗返回NULL, 成功返回要彈出的尾節點的數據指針	
*/
void *	SingleList_PopTail( SINGLELIST *pSingleList )
{
    SINGLENODE	*pPopNode;   /* 用來指向要彈出數據的節點的指針 */
    SINGLENODE	*pTailPrevNode;   /* 用來指向尾節點的上一節點的指針 */
    void		*pPopData;   /* 用來指向要彈出的數據的指針 */

    /* 參數校驗 */
    if ( pSingleList == NULL || pSingleList->pHead == NULL ) 
    {
        return NULL;
	}

    /* 將要彈出數據的節點指針指向鏈表頭節點，彈出數據指針指向頭節點的數據 */
    pPopNode = pSingleList->pTail;
    pPopData = pPopNode->pData;

    pTailPrevNode = pSingleList->pHead;

    /* 如果鏈表的頭節點和尾節點相同則表示原來只有一個節點，彈出尾節點后，
     * 此時鏈表已經為空，沒有節點在里面，此時應該將頭節點指針賦空
     * 當前節點指針由于前面已經處理過了，如果只有一個節點的話肯定為空
     * 所以這里不需要處理當前節點指針
     */
    if ( pSingleList->pTail == pSingleList->pHead )
    {
        pTailPrevNode = NULL;
	    pSingleList->pHead = NULL;
    }
    else 
    {
        while ( pTailPrevNode != NULL )
        {
            if ( pTailPrevNode->pNext == pSingleList->pTail )
            {
                break;
            }
            pTailPrevNode = pTailPrevNode->pNext;
        }
    }

    /* 
     * 判斷當前節點指針是否指向尾節點，如果指向頭節點的話則需要將其
     * 指向尾節點的前一節點 
     */
    if ( pSingleList->pCur == pSingleList->pTail )
    {
        pSingleList->pCur = pTailPrevNode;
    }

    /* 將尾節點指針指向尾節點的前一節點 */
    pSingleList->pTail = pTailPrevNode;

    if ( pTailPrevNode != NULL )
    {
        pTailPrevNode->pNext = NULL;
    }
    
    /* 將鏈表節點數量減1 */
    pSingleList->uCount--;

    /* 釋放彈出的節點, 注意這里并沒有釋放節點數據指針 */
    free( pPopNode );

    return pPopData;    /* 返回頭節點的數據指針 */    
}


/**	鏈表的刪除節點函數，它將刪除和pMatchData參數有相同數據的節點
    如果有許多有相同數據的節點它將只刪除第一個有相同數據的節點

	@param	SINGLELIST *pSingleList - 要操作的單向鏈表指針	
	@param	void *pMatchData - 要刪除節點的匹配數據	
	@param	COMPAREFUNC CompareFunc - 數據比較函數用來比較pMatchData參數和鏈表
                                      節點參數是否相等	
	@param	DESTROYFUNC DestroyFunc - 鏈表節點的數據釋放函數	
	@return	INT (by default) - CAPI_FAILED表示失敗或鏈表中沒有匹配的數據，CAPI_SUCCESS表示成功刪除	
*/
INT	 SingleList_Delete( SINGLELIST *pSingleList,  
                        void *pMatchData, 
                        COMPAREFUNC CompareFunc, 
                        DESTROYFUNC DestroyFunc )
{
    SINGLENODE  *pNode;
    SINGLENODE  *pPrevNode;

    /* 參數校驗 */
    if ( pSingleList == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }

    pNode = pSingleList->pHead;
    pPrevNode = pNode;

    while ( pNode != NULL )
    {
        /* 比較節點數據是否和匹配數據匹配 */
        if ( (*CompareFunc)( pNode->pData, pMatchData ) == 0 )
        {
            if ( pPrevNode == pNode )
            {
                /* 頭節點匹配上了，需要刪除頭節點 */
                pSingleList->pHead = pNode->pNext;
                if ( pSingleList->pTail == pNode )
                {
                    /* 
                     * 如果尾節點和pNode相同，表明鏈表里只有一個節點
                     * 此時需要將鏈表尾節點指針和鏈表當前節點指針賦空
                     */
                    pSingleList->pTail = NULL;
                    pSingleList->pCur = NULL;
                }
            }
            else
            {
                pPrevNode->pNext = pNode->pNext;
                if ( pSingleList->pTail == pNode )
                {
                    /* 
                     * 如果尾節點和pNode相同，表明刪除的是尾節點
                     * 此時需要將尾節點指針指向要刪除節點的前一個節點
                     */
                    pSingleList->pTail = pPrevNode;
                }

                if ( pSingleList->pCur == pNode )
                {
                    /* 
                     * 如果鏈表當前節點和pNode相同，表明刪除的是當前節點
                     * 此時需要將當前節點指針指向要刪除節點的下一個節點
                     */
12 3 下一頁
?? 文件大小 111 K
?? 上傳用戶 focuslocus
?? 所屬分類數據結構
??? 相關標簽

#多任務 #數據結構 #算法 #源代碼
?? 快捷鍵說明

復制代碼 Ctrl + C
搜索代碼 Ctrl + F
全屏模式 F11
切換主題 Ctrl + Shift + D
顯示快捷鍵 ?
增大字號 Ctrl + =
減小字號 Ctrl + -
亚洲欧美第一页_禁久久精品乱码_粉嫩av一区二区三区免费野_久草精品视频

?? singlelist.c

?? 快捷鍵說明
