频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
AMPS:单向链表源码解读
2013-01-20 13:23:00      个评论      
收藏   我要投稿
像单向链表、双向链表、堆、栈等这些基本的数据结构在大型软件中均有很广泛的使用,所以今天看一下AMPS中单向链表的操作函数库,其定义了单向链表的非常多的操作API,且提供了回调函数接口,从而使链表结构用于不同类型的结点,且可以使用户自定义的函数来实现链表排序、结点操作。所以这部分的代码可以做为常用的工具代码,可以在其他项目中广泛应用。

 

 先看看AMPS提供的单链表操作接口有哪些?如下,由函数名称就可以看出,有非常丰富的函数。

 

 

 

最后,看一下单向链表的实现源代码:

 

AMPS_LinkList.h

 

 

 

[cpp]  

#ifndef __HEADER_AMPS_LINKLIST_H__   

#define __HEADER_AMPS_LINKLIST_H__   

  

#ifdef __cplusplus   

extern "C"  

{  

#endif   

  

#include "AMPS_API.h"   

#include "AMPS_Defines.h"   

  

int SList_InsertSortedPrepend(void** r_ppvList, void* r_pvKey, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);  

int SList_InsertSortedAppend(void** r_ppvList, void* r_pvKey, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);  

void SList_SortPrepend(void** r_ppvList, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);  

void SList_SortAppend(void** r_ppvList, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);  

int SList_Traverse(void* r_ppvList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvArg);  

int SList_Copy(void** r_ppvDest, void* r_pvSrc, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback, AMPS_LListCloneCallback r_pfAMPS_LListCloneCallback);  

int SList_RemoveKey(void** r_ppvList, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);  

void* SList_FindData (void* r_pvList, void* r_pvData);  

void* SList_GetNextNode(void* r_pvList);  

void* SList_GetNodeData(void* r_pvNode);  

void SList_AppendGivenNode(void** r_ppvList, void* r_pvSListNode);  

void SList_PrependGivenNode(void** r_ppvList, void* r_pvGivenNode, void* r_pvNewNode);  

t_AMPSSList* SList_Prepend(t_AMPSSList** r_ppoSList, void* r_pvData);  

t_AMPSSList* SList_AppendEx(t_AMPSSList** r_ppoSList, void* r_pvData);  

int SList_Append(void** r_ppvList, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);  

t_AMPSSList* SList_Last(t_AMPSSList* r_poSList);  

void* SList_Alloc(void* r_pvData);  

t_AMPSSList* SList_Search(t_AMPSSList* r_poSList, AMPS_LListCompareLinkDataCallback r_pfAMPS_LListCompareCallback, void* r_pvSrcData);  

t_AMPSSList* SList_Find (t_AMPSSList* r_poSList, t_AMPSSList* r_poSListNode);  

int SList_Remove(t_AMPSSList** r_ppoSList, t_AMPSSList* r_poSListNode, AMPS_LListFreeLinkDataCallback r_pfAMPS_LListFreeLinkDataCallback);  

int SList_Free(t_AMPSSList** r_ppoSList, AMPS_LListFreeLinkDataCallback r_pfAMPS_LListFreeLinkDataCallback);  

int SList_FreeEx(t_AMPSSList** r_ppoSList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvData);  

unsigned int SList_Count(const t_AMPSSList* r_cpoSList);  

int SList_Concat(t_AMPSSList** r_ppoSListSrc, t_AMPSSList* r_poSListDst);  

#ifdef __cplusplus   

  

}  

#endif   

  

#endif /* __HEADER_AMPS_LINKLIST_H__ */  

 

#ifndef __HEADER_AMPS_LINKLIST_H__

#define __HEADER_AMPS_LINKLIST_H__

 

#ifdef __cplusplus

extern "C"

{

#endif

 

#include "AMPS_API.h"

#include "AMPS_Defines.h"

 

int SList_InsertSortedPrepend(void** r_ppvList, void* r_pvKey, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);

int SList_InsertSortedAppend(void** r_ppvList, void* r_pvKey, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);

void SList_SortPrepend(void** r_ppvList, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);

void SList_SortAppend(void** r_ppvList, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);

int SList_Traverse(void* r_ppvList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvArg);

int SList_Copy(void** r_ppvDest, void* r_pvSrc, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback, AMPS_LListCloneCallback r_pfAMPS_LListCloneCallback);

int SList_RemoveKey(void** r_ppvList, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);

void* SList_FindData (void* r_pvList, void* r_pvData);

void* SList_GetNextNode(void* r_pvList);

void* SList_GetNodeData(void* r_pvNode);

void SList_AppendGivenNode(void** r_ppvList, void* r_pvSListNode);

void SList_PrependGivenNode(void** r_ppvList, void* r_pvGivenNode, void* r_pvNewNode);

t_AMPSSList* SList_Prepend(t_AMPSSList** r_ppoSList, void* r_pvData);

t_AMPSSList* SList_AppendEx(t_AMPSSList** r_ppoSList, void* r_pvData);

int SList_Append(void** r_ppvList, void* r_pvData, AMPS_LListCompareCallback r_pfAMPS_LListCompareCallback);

t_AMPSSList* SList_Last(t_AMPSSList* r_poSList);

void* SList_Alloc(void* r_pvData);

t_AMPSSList* SList_Search(t_AMPSSList* r_poSList, AMPS_LListCompareLinkDataCallback r_pfAMPS_LListCompareCallback, void* r_pvSrcData);

t_AMPSSList* SList_Find (t_AMPSSList* r_poSList, t_AMPSSList* r_poSListNode);

int SList_Remove(t_AMPSSList** r_ppoSList, t_AMPSSList* r_poSListNode, AMPS_LListFreeLinkDataCallback r_pfAMPS_LListFreeLinkDataCallback);

int SList_Free(t_AMPSSList** r_ppoSList, AMPS_LListFreeLinkDataCallback r_pfAMPS_LListFreeLinkDataCallback);

int SList_FreeEx(t_AMPSSList** r_ppoSList, AMPS_LListProcessCallback r_pfAMPS_LListProcessCallback, void* r_pvData);

unsigned int SList_Count(const t_AMPSSList* r_cpoSList);

int SList_Concat(t_AMPSSList** r_ppoSListSrc, t_AMPSSList* r_poSListDst);

#ifdef __cplusplus

 

}

#endif

 

#endif /* __HEADER_AMPS_LINKLIST_H__ */

 

AMPS_LinkList.c

 

 

 

[cpp]  

/***************************************************************** 

文件名称: AMPS_LinkList.c 

功能描述: 链表操作API函数(单向链表和双向链表) 

 

*****************************************************************/  

  

#include "AMPS_LinkList.h"   

#include "AMPS_MemMgt.h"   

  

/***************************************************************** 

函数名称: SList_Append 

功能描述: 在链表后追加结点 

入参:: 

      void **list 原链表 

      void* pvData 待追加的结点 

      AMPS_LListCompareCallback compare 链表比较回调,此函数中没有使用 

 

出参: 

      void **list 追加后的链表 

返回值: 

      int 

 

*****************************************************************/  

int SList_Append(void **list, void* pvData, AMPS_LListCompareCallback compare)  

{  

    t_AMPSSList** slist = (t_AMPSSList**)list;  

  

    {  

        t_AMPSSList *new_list = NULL;  // pointer to newly created node   

        t_AMPSSList *last = NULL;      // pointer to last node of link list    

        t_AMPSSList *list_ptr = *slist;  

  

        /*在链表中分配新结点所要使用的内存空间*/  

        new_list = SList_Alloc(pvData);  

        if (NULL == new_list)  

        {  

            return -1;  

        }  

        if (list_ptr)  

        {  

            /*找到当前链表结束*/  

            last = SList_Last(list_ptr);  

            if (NULL == last)  

            {  

                free(new_list);  

                return -1;  

            }  

  

            /*将待追加的结点连接到当前链表结尾*/  

            last->poAMPSSListNext = new_list;  

            new_list->poAMPSSListPrev = last;  

        }  

        else  

        {  

            /*如果当前链表为空,则待追加结点做为链表头结点*/  

            *slist = new_list;  

        }  

        return 0;  

    }  

}  

  

/***************************************************************** 

函数名称: SList_InsertSortedPrepend 

功能描述: 在有序链表中前向插入新结点 

入参:: 

      void **list 原链表 

      void* key 未使用 

      void* pvData 待插入结点 

      AMPS_LListCompareCallback compare 结点比较回调函数,由调用者实现 

 

出参: 

      void **list 追加后的链表 

返回值: 

      int 

 

*****************************************************************/  

int SList_InsertSortedPrepend(void **list, void* key, void* pvData, AMPS_LListCompareCallback compare)  

{  

  

    t_AMPSSList** slist = (t_AMPSSList**)list;  

  

    /*判断要添加的结点是否已在链表中存在,已存在,直接返回成功*/  

    if(NULL != SList_FindData(*slist,pvData) )  

    {  

       printf("slist_insert_sorted: node already found in list\n");  

       return 0;  

    }  

  

    {  

        t_AMPSSList *new_node = NULL;  // pointer to newly created node   

        t_AMPSSList *list_ptr = *slist, *curr;  

        new_node = SList_Alloc(pvData);  

        if (NULL == new_node)  

        {  

            return -1;  

        }  

          

        if (list_ptr)  

        {  

            /*遍历链表*/  

            while (list_ptr)  

            {  

                /*如果当前链表结点不大于待插入结点,将其插入此结点之后*/  

                if (AMPS_LLIST_KEY_IS_GREATER != compare(list_ptr->pvData, pvData))  

                {  

                   break;  

                }  

                curr = list_ptr;  

                list_ptr = list_ptr->poAMPSSListNext;  

            }  

              

            if(!list_ptr)  

            {  

                /*如果已到链表结尾,刚将新结点插入到最后*/  

                SList_AppendGivenNode((void **)&curr, (void*)new_node);  

            }  

            else   

            {  

                /*未到结尾已找到插入位置,刚插入到链表中间*/  

                SList_PrependGivenNode(list, (void*)list_ptr,(void*)new_node);  

            }  

        }  

        else  

        {  

            *slist = new_node;  

        }  

        return 0;  

    }  

}  

  

/***************************************************************** 

函数名称: SList_InsertSortedAppend 

功能描述: 在递增的有序链表中插入新结点 

入参:: 

      void **list 原链表 

      void* key 未使用 

      void* pvData 待插入结点 

      AMPS_LListCompareCallback compare 结点比较回调函数,由调用者实现 

 

出参: 

      void **list 追加后的链表 

返回值: 

      int 

 

*****************************************************************/  

int SList_InsertSortedAppend(void **list, void* key, void* pvData, AMPS_LListCompareCallback compare)  

{  

  

    t_AMPSSList** slist = (t_AMPSSList**)list;  

      

    if(NULL != SList_FindData(*slist,pvData) )  

    {  

       printf("slist_insert_sorted: node already found in list\n");  

       return 0;  

    }  

  

    {  

        t_AMPSSList *new_node = NULL;  // pointer to newly created node   

        t_AMPSSList *list_ptr = *slist, *curr;  

        new_node = SList_Alloc(pvData);  

        if (NULL == new_node)  

        {  

            return -1;  

        }  

          

        if (list_ptr)  

        {  

            while (list_ptr)  

            {  

                if (AMPS_LLIST_KEY_IS_SMALLER == compare(list_ptr->pvData, pvData))  

                {  

                   break;  

                }  

                curr = list_ptr;  

                list_ptr = list_ptr->poAMPSSListNext;  

            }  

            if(!list_ptr)  

            {  

                SList_AppendGivenNode((void **)&curr, (void*)new_node);  

            }  

            else   

            {  

                SList_PrependGivenNode(list, (void*)list_ptr,(void*)new_node);  

            }  

        }  

        else  

        {  

            *slist = new_node;  

        }  

        return 0;  

    }  

}  

  

/***************************************************************** 

函数名称: SList_SortPrepend 

功能描述: 链表排序 

入参:: 

      void **list 原链表 

      AMPS_LListCompareCallback compare 结点比较回调函数,由调用者实现 

 

出参: 

      void **list 排序后的链表 

返回值: 

      void 

 

*****************************************************************/  

void SList_SortPrepend(void** list,AMPS_LListCompareCallback compare)  

{  

  t_AMPSSList** slist = (t_AMPSSList**)list;  

  t_AMPSSList *list_ptr = *slist;  

  

    if (list_ptr)  

    {  

        while (list_ptr)  

        {     

           t_AMPSSList* poAMPSSListNext = list_ptr->poAMPSSListNext;  

             

           /*保存待删除结点的内容*/  

           void* pvData = list_ptr->pvData;  

             

           /*从链表中删除结点*/  

           SList_Remove(slist,list_ptr,NULL);  

             

           /*将已删除结点的内容插入到排序后的链表*/  

           SList_InsertSortedPrepend((void **)slist,NULL,pvData,compare);   

           list_ptr = poAMPSSListNext;   

        }  

          

    }  

}  

  

/***************************************************************** 

函数名称: SList_SortAppend 

功能描述: 链表排序(严格递增) 

入参:: 

      void **list 原链表 

      AMPS_LListCompareCallback compare 结点比较回调函数,由调用者实现 

 

出参: 

      void **list 排序后的链表 

返回值: 

      void 

 

*****************************************************************/  

void SList_SortAppend(void** list,AMPS_LListCompareCallback compare)  

{  

  t_AMPSSList** slist = (t_AMPSSList**)list;  

  t_AMPSSList *list_ptr = SList_Last(*slist);  

  

    if (list_ptr)  

    {  

        while (list_ptr)  

        {     

           t_AMPSSList* poAMPSSListPrev = list_ptr->poAMPSSListPrev;  

           void* pvData = list_ptr->pvData;  

           SList_Remove(slist,list_ptr,NULL);  

           SList_InsertSortedAppend((void **)slist,NULL,pvData,compare);  

           list_ptr = poAMPSSListPrev;   

        }  

    }  

}  

  

/***************************************************************** 

函数名称: SList_Traverse 

功能描述: 遍历并通过用户自定义的回调函数处理各结点 

入参:: 

      void **list 原链表 

      AMPS_LListProcessCallback compare 结点处理回调函数,由调用者实现 

      void* arg  回调函数参数 

 

出参: 

      void **list 处理之后的链表 

返回值: 

      int 

 

*****************************************************************/  

int SList_Traverse(void* list,AMPS_LListProcessCallback func,void* arg)  

{  

   t_AMPSSList *slist = (t_AMPSSList*)list,*tempList = NULL;  

     

   if(!slist)  

   {  

      return 0;  

   }  

  

   for(tempList = slist;tempList;tempList = tempList->poAMPSSListNext)  

   {  

      func(tempList->pvData,arg);      

   }  

     

   return 0;   

}  

  

/***************************************************************** 

函数名称: SList_Traverse 

功能描述: 复制一份原链表,在复制过程中可以处理各结点,以实现对于不同类型 

          结点的操作。 

入参:: 

      void** dest 目标链表 

      void* src   源链表 

      AMPS_LListCompareCallback compare  结点比较回调,没有使用 

      AMPS_LListCloneCallback clone 结点处理函数回调 

 

出参: 

      void** dest 处理之后的链表 

返回值: 

      int 

 

*****************************************************************/  

int SList_Copy(void** dest,void* src,AMPS_LListCompareCallback compare,AMPS_LListCloneCallback clone)  

{  

  

   t_AMPSSList* srcList = (t_AMPSSList*)src;  

   void* pvData;  

  

   if(!srcList)  

   {  

      return 0;  

   }  

  

   for(;srcList;srcList = srcList->poAMPSSListNext)  

   {  

     /*逐一处理各结点,比如结点数据为char*,则需要strcpy,如为int,直接赋值*/  

     pvData = clone(srcList->pvData);  

  

     /*将处理后的结点插入目标链表,最后,两链表长度相同,但结点内容可以不同*/  

     SList_Append(dest,pvData,NULL);  

   }  

     

   return 0;  

}  

  

  

/***************************************************************** 

函数名称: SList_AppendEx 

功能描述: 向链表后追加结点,返回最终链表 

入参:: 

      t_AMPSSList** list 原链表 

      void* pvData       待追加结点 

 

出参: 

      NA 

返回值: 

      t_AMPSSList*  处理之后的链表 

 

*****************************************************************/  

t_AMPSSList* SList_AppendEx(t_AMPSSList** list, void* pvData)  

{  

    t_AMPSSList** slist = (t_AMPSSList**)list;  

    t_AMPSSList* new_list = NULL;  // pointer to newly created node   

    t_AMPSSList* last = NULL;      // pointer to last node of link list    

    t_AMPSSList* list_ptr = *slist;  

      

    new_list = SList_Alloc(pvData);  

    if(NULL == new_list)  

    {  

        return NULL;  

    }  

    if(list_ptr)  

    {  

        last = SList_Last(list_ptr);  

        if(NULL == last)  

        {  

            free(new_list);  

            return NULL;  

        }  

        last->poAMPSSListNext = new_list;  

        new_list->poAMPSSListPrev = last;  

    }  

    else  

    {  

        *slist = new_list;  

    }  

    return new_list;  

}  

  

/***************************************************************** 

函数名称: SList_Prepend 

功能描述: 向链表头追加结点,返回最终链表 

入参:: 

      t_AMPSSList** list 原链表 

      void* pvData       待追加结点 

 

出参: 

      NA 

返回值: 

      t_AMPSSList*  处理之后的链表 

 

*****************************************************************/  

t_AMPSSList* SList_Prepend(t_AMPSSList **list, void* pvData)  

{  

    t_AMPSSList *new_list = NULL;  

    t_AMPSSList *list_ptr = *list;  

  

    new_list = (t_AMPSSList*)SList_Alloc(pvData);  

    if (NULL == new_list)  

    {  

        return NULL;  

    }  

    new_list->poAMPSSListNext = list_ptr;  

    new_list->poAMPSSListPrev = NULL;  

  

    if (list_ptr)  

    {  

        list_ptr->poAMPSSListPrev = new_list;    

    }  

  

    *list = new_list;  

  

    return new_list;  

}  

  

/***************************************************************** 

函数名称: SList_Last 

功能描述: 查找链表结尾 

入参:: 

      t_AMPSSList** list 原链表 

 

出参: 

      NA 

返回值: 

      t_AMPSSList*  处理之后的链表 

 

*****************************************************************/  

t_AMPSSList* SList_Last(t_AMPSSList *list)  

{/* 

    if (NULL != list) 

    {   */  

    if (list)  

    {  

        while (list->poAMPSSListNext)  

        {  

            list = list->poAMPSSListNext;  

        }  

    }  

    //}   

    return list;  

}  

  

/***************************************************************** 

函数名称: SList_Alloc 

功能描述: 分配新的链表结点,并赋值 

入参:: 

      void* pvData 结点 

 

出参: 

      NA 

返回值: 

      void*  处理之后的链表 

 

*****************************************************************/  

void* SList_Alloc(void* pvData)  

{  

    t_AMPSSList* new_list = NULL;  

    new_list = AMPS_InternalMalloc(sizeof(t_AMPSSList));  

    if(NULL == new_list)  

    {  

        printf("=>>>>>>>>>>>>>>>>>>>>> malloc failed.\n\n\n\n\n\n\n\n");  

        return NULL;  

    }  

    new_list->pvData = pvData;  

    new_list->poAMPSSListNext = NULL;  

    new_list->poAMPSSListPrev = NULL;  

    return (void*)new_list;  

}  

  

/***************************************************************** 

函数名称: SList_RemoveKey 

功能描述: 删除链表中的指定结点 

入参:: 

      void** list 原链表 

      void* pvData 待删除结点 

      AMPS_LListCompareCallback compare 结点比较回调函数 

 

出参: 

      void** list 

返回值: 

      int 

 

*****************************************************************/  

int SList_RemoveKey(void** list,void* pvData,AMPS_LListCompareCallback compare)  

{  

    t_AMPSSList** slist = (t_AMPSSList**)list;  

  

    t_AMPSSList *list_ptr = (t_AMPSSList*)*slist;  

    while (list_ptr)  

    {  

        /*使用用户自定义的回调函数比较结点,相等,则从链表中删除*/  

        if (AMPS_LLIST_KEYS_ARE_EQUAL == compare(list_ptr->pvData,pvData))  

        {  

            SList_Remove(slist, (void*)list_ptr, NULL);  

            break;  

        }  

        list_ptr = list_ptr->poAMPSSListNext;  

    }  

    return 0;  

}  

  

/***************************************************************** 

函数名称: SList_Search 

功能描述: 在链表中查找符合条件的结点 

入参:: 

      t_AMPSSList *list 原链表 

      AMPS_LListCompareCallback func_ptr 结点查找回调函数 

      void *src_data 指定的查找条件 

 

出参: 

      void** list 

返回值: 

      t_AMPSSList* 找到的结点指针 

 

*****************************************************************/  

t_AMPSSList* SList_Search (t_AMPSSList *list, AMPS_LListCompareLinkDataCallback func_ptr, void *src_data)  

{  

    while (list)  

    {  

        if (!func_ptr(src_data, list->pvData))  

        {  

            break;  

        }  

        list = list->poAMPSSListNext;  

    }  

    return list;  

}  

  

/***************************************************************** 

函数名称: SList_Find 

功能描述: 在链表中查找指定的结点 

入参:: 

      t_AMPSSList *list 原链表 

      t_AMPSSList *node 指定的结点 

 

出参: 

      t_AMPSSList *list 

返回值: 

      t_AMPSSList* 找到的结点指针 

 

*****************************************************************/  

t_AMPSSList* SList_Find (t_AMPSSList *list, t_AMPSSList *node)  

{  

    while (list)  

    {  

        if (list == node)  

        {  

            return list;  

        }  

        list = list->poAMPSSListNext;  

    }  

    return NULL;  

}  

  

/***************************************************************** 

函数名称: SList_Find 

功能描述: 在链表中查找指定的结点内容 

入参:: 

      void *list 原链表 

      void *pvData 指定的结点内容 

 

出参: 

      t_AMPSSList *list 

返回值: 

      void* 找到的结点指针 

 

*****************************************************************/  

void* SList_FindData (void *list, void *pvData)  

{  

    t_AMPSSList *slist = (t_AMPSSList*)list;  

    while (slist)  

    {  

        if (slist->pvData == pvData)  

        {  

            return slist;  

        }  

        slist = slist->poAMPSSListNext;  

    }  

    return NULL;  

}  

  

/***************************************************************** 

函数名称: SList_Free 

功能描述: 释放链表 

入参:: 

      void *list 原链表 

      AMPS_LListFreeLinkDataCallback func_ptr 结点处理回调函数,如果结点 

      的内存需要显式释放,使用此函数达到目的。 

 

出参: 

      t_AMPSSList *list 

返回值: 

      int 

 

*****************************************************************/  

int SList_Free(t_AMPSSList **list, AMPS_LListFreeLinkDataCallback func_ptr)  

{  

    t_AMPSSList *curr = NULL;  // pointer to current node    

    t_AMPSSList *poAMPSSListPrev = NULL;  // pointer to previous node    

  

    curr = *list;  

    while (curr)  

    {  

        poAMPSSListPrev = curr;  

        curr = (t_AMPSSList*)curr->poAMPSSListNext;  

        if (func_ptr)  

        {  

            /*释放结点*/  

            if (func_ptr(&(poAMPSSListPrev->pvData)))  

            {  

                return AMPS_ERROR_FAILURE;  

            }  

        }  

        /*if (poAMPSSListPrev->pvData) 

        { 

            AMPS_InternalFree(poAMPSSListPrev->pvData); 

        }*/  

        AMPS_InternalFree(poAMPSSListPrev);  

    }  

  

    *list = NULL;  

  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: SList_FreeEx 

功能描述: 释放链表 

入参:: 

      void *list 原链表 

      AMPS_LListFreeLinkDataCallback func_ptr 结点处理回调函数,如果结点 

      的内存需要显式释放,使用此函数达到目的。 

      void* r_pvData 回调函数入参,通过它可以进行在释放前的一些结点操作 

 

出参: 

      t_AMPSSList *list 

返回值: 

      int 

 

*****************************************************************/  

int SList_FreeEx(t_AMPSSList **list, AMPS_LListProcessCallback func_ptr, void* r_pvData)  

{  

    t_AMPSSList *curr = NULL;  // pointer to current node    

    t_AMPSSList *poAMPSSListPrev = NULL;  // pointer to previous node    

  

    curr = *list;  

    while (curr)  

    {  

        poAMPSSListPrev = curr;  

        curr = (t_AMPSSList*)curr->poAMPSSListNext;  

        if (func_ptr)  

        {  

            func_ptr(poAMPSSListPrev->pvData, r_pvData);  

        }  

        AMPS_InternalFree(poAMPSSListPrev);  

    }  

  

    *list = NULL;  

  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: SList_FreeEx 

功能描述: 删除链表中指定的结点 

入参:: 

      t_AMPSSList **list 原链表 

      t_AMPSSList *node  待删除结点 

      AMPS_LListFreeLinkDataCallback func_ptr 结点处理回调函数,如果结点 

      的内存需要显式释放,使用此函数达到目的。 

 

出参: 

      t_AMPSSList *list 

返回值: 

      int 

 

*****************************************************************/  

int SList_Remove(t_AMPSSList **list, t_AMPSSList *node, AMPS_LListFreeLinkDataCallback func_ptr)  

{  

    if ((list == NULL) || (*list == NULL) || (node == NULL))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

  

    if (func_ptr)  

    {  

        /*处理待删除结点*/  

        if (AMPS_ERROR_FAILURE == func_ptr(&(node->pvData)))  

        {  

            return AMPS_ERROR_FAILURE;  

        }  

    }  

  

    /*待删除结点为头结点*/  

    // If first element is found to be the element to be deleted   

    if (NULL == node->poAMPSSListPrev)  

    {  

        /*待删除结点不是头结点,则返回失败*/  

        if (*list != node)  

        {  

            printf("SList_Remove: list corrupted: poAMPSSListPrev pointer NULL but node is not the first element in list\n");  

            return AMPS_ERROR_FAILURE;  

        }  

        *list = node->poAMPSSListNext;  

        if (*list) // We have deleted the last element in the list   

            (*list)->poAMPSSListPrev = NULL;  

        AMPS_InternalFree(node);  

        return AMPS_SUCCESS;        

    }  

  

    /*待删除结点不是头结点*/  

    node->poAMPSSListPrev->poAMPSSListNext = node->poAMPSSListNext;  

    if (node->poAMPSSListNext)  

    {  

        node->poAMPSSListNext->poAMPSSListPrev = node->poAMPSSListPrev;  

    }  

  

    AMPS_InternalFree(node);  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: SList_Count 

功能描述: 计算链表中的结点个数 

入参:: 

      const t_AMPSSList* list 原链表 

 

出参: 

      NA 

返回值: 

      int 结点数目 

 

*****************************************************************/  

unsigned int SList_Count(const t_AMPSSList* list)  

{  

    unsigned int uchCount = 0;  

    t_AMPSSList* cur_ptr = (t_AMPSSList*)list;  

  

    while (cur_ptr)  

    {  

        uchCount++;  

        cur_ptr = cur_ptr->poAMPSSListNext;  

    }  

  

    return uchCount;  

}  

  

/***************************************************************** 

函数名称: SList_Concat 

功能描述: 连接两个链表 

入参:: 

      t_AMPSSList** src 原链表 

      t_AMPSSList* dst  待连接的链表 

 

出参: 

      NA 

返回值: 

      int  

 

*****************************************************************/  

int SList_Concat(t_AMPSSList** src, t_AMPSSList* dst)  

{  

    t_AMPSSList *last = NULL;  

    if (src == NULL || dst == NULL)  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

    if (*src == NULL)  

    {  

        *src = dst;  

    } else  

    {  

        last = SList_Last(*src);  

        last->poAMPSSListNext = dst;  

        dst->poAMPSSListPrev = last;  

    }  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: SList_AppendGivenNode 

功能描述: 在链表头结点后插入指定结点 

入参:: 

      void **list 原链表 

      void* sListNode  待插入结点 

 

出参: 

      void **list 

返回值: 

      void  

 

*****************************************************************/  

void SList_AppendGivenNode(void **list, void* sListNode)  

{  

    t_AMPSSList **slist = (t_AMPSSList**)list;  

    t_AMPSSList* list_ptr = (t_AMPSSList*)*slist;  

    t_AMPSSList* snode = (t_AMPSSList*)sListNode;  

      

    if(!list_ptr)  

    {  

       *slist = snode;  

       return;  

    }  

  

    snode->poAMPSSListNext = list_ptr->poAMPSSListNext;  

    snode->poAMPSSListPrev = list_ptr;  

    list_ptr->poAMPSSListNext = snode;  

}  

  

/***************************************************************** 

函数名称: SList_AppendGivenNode 

功能描述: 在指定的结点后插入指定新结点 

入参:: 

      void **list 原链表 

      void* givenNode  指定的结点 

      void* newNode 待插入结点 

 

出参: 

      void **list 

返回值: 

      void  

 

*****************************************************************/  

void SList_PrependGivenNode(void **list, void* givenNode, void* newNode)  

{  

    t_AMPSSList **slist = (t_AMPSSList**)list;  

    t_AMPSSList* node_ptr = (t_AMPSSList*)givenNode;  

    t_AMPSSList* snode = (t_AMPSSList*)newNode;  

  

    if(!node_ptr)  

    {  

       *slist = snode;  

       return;  

    }  

  

    snode->poAMPSSListNext = node_ptr;  

    snode->poAMPSSListPrev = node_ptr->poAMPSSListPrev;  

    if(NULL == node_ptr->poAMPSSListPrev)  

    {  

        *slist = snode;  

    }  

    else  

    {  

        node_ptr->poAMPSSListPrev->poAMPSSListNext = snode;  

    }  

    node_ptr->poAMPSSListPrev = snode;  

      

}  

  

/***************************************************************** 

函数名称: SList_RemoveWithOutFree 

功能描述: 删除链表中指定的结点,但不释放结点内容 

入参:: 

      t_AMPSSList** r_ppoAMPSSListHead 原链表 

      t_AMPSSList* r_poAMPSSListNode 待删除结点 

       

出参: 

      t_AMPSSList** r_ppoAMPSSListHead 

返回值: 

      int 

 

*****************************************************************/  

  

int SList_RemoveWithOutFree(t_AMPSSList** r_ppoAMPSSListHead, t_AMPSSList* r_poAMPSSListNode)  

{  

    if((NULL == r_ppoAMPSSListHead) || (NULL == *r_ppoAMPSSListHead) || (NULL == r_poAMPSSListNode))  

    {  

        return AMPS_ERROR_FAILURE;  

    }  

  

    /*待删除结点为头结点*/  

    // If first element is found to be the element to be deleted   

    if(NULL == r_poAMPSSListNode->poAMPSSListPrev)  

    {  

        if(*r_ppoAMPSSListHead != r_poAMPSSListNode)  

        {  

            printf("SList_RemoveWithOutFree: list corrupted: head's previous pointer is NULL but node is not the first element in the list\n");  

            return AMPS_ERROR_FAILURE;  

        }  

  

        *r_ppoAMPSSListHead = r_poAMPSSListNode->poAMPSSListNext;  

        if(NULL != *r_ppoAMPSSListHead) // Is the last element in the list deleted?   

        {  

            (*r_ppoAMPSSListHead)->poAMPSSListPrev = NULL;  

        }  

    }  

    else  

    {  

        r_poAMPSSListNode->poAMPSSListPrev->poAMPSSListNext = r_poAMPSSListNode->poAMPSSListNext;  

        if(NULL != r_poAMPSSListNode->poAMPSSListNext)  

        {  

            r_poAMPSSListNode->poAMPSSListNext->poAMPSSListPrev = r_poAMPSSListNode->poAMPSSListPrev;  

        }  

    }  

  

    r_poAMPSSListNode->poAMPSSListNext = NULL;  

    r_poAMPSSListNode->poAMPSSListPrev = NULL;  

  

    return AMPS_SUCCESS;  

}  

  

/***************************************************************** 

函数名称: SList_GetNextNode 

功能描述: 取链表下一结点 

入参:: 

      void* list 原链表 

       

出参: 

      t_AMPSSList** r_ppoAMPSSListHead 

返回值: 

      void* list 

 

*****************************************************************/  

void* SList_GetNextNode(void* list)  

{  

    t_AMPSSList *slist = (t_AMPSSList*)list;  

    if(!slist)  

    {  

       return NULL;  

    }  

    return slist->poAMPSSListNext;  

}  

  

/***************************************************************** 

函数名称: SList_GetNodeData 

功能描述: 取指定结点内容 

入参:: 

      void* node 原链表 

       

出参: 

      NA 

返回值: 

      void* 结点内容 

 

*****************************************************************/  

void* SList_GetNodeData(void* node)  

{  

    t_AMPSSList *slist = (t_AMPSSList*)node;  

    if(!slist)  

    {  

       return NULL;  

    }  

    return slist->pvData;  

}  

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 单向 源码
上一篇:10进制数转二进制表示
下一篇:矩阵中的数学旋转公式 转换到 C++中函数 替换DirectX 9.0中D3DXMatrixRotationAxis函数
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站