?? singlelist.c
字號:
/*
* 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相同，表明刪除的是當前節點
* 此時需要將當前節點指針指向要刪除節點的下一個節點
*/
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -