个双向链表的例子

cpubbs

/**
* 模块名称 : BiArray.c
* 时    间 :
* 作    者 :
* 说    明 : 实现一个双向链表
* 依 赖 型 : None
*
* 功    能
* 本模块以模板<template>的形式实现了一个双向链表的功能
* 模块使用结构BIDIRECT_ARRAY_S来管理双向链表, BIDIRECT_ARRAY_S中存在一个头
* 节点<HeadItem>, 一个尾节点<TailItem>和一个当前节点指针<pCurrentItem>. 其
* 中头尾两个节点只是起管理作用, 并不能存储数据.
* 此双向链表可以实现在头部, 尾部和当前节点后加入节点. 并可以删除最先, 最后
* 和当前节点.
*
* 本模块使用一个通用的数据类型BIDIRECT_ARRAY_S来达到作为模本的效果, 如果必
* 要, BIDIRECT_ARRAY_S类型可以定义为任意的结构类型. 但注意结构中必须包含两
* 个成员: pFrontItem, pRearItem.  分别为指向前一个节点的指针和指向后一个节
* 点的指针. 另外还需注意在引用此模板的模块中需要定义一个(或多个)
BIDIRECT_ARRAY_S
* 的实例管理双向链表.
*
* 本模本可以灵活应用最为队列, 堆栈, 链表来处理
* 使用本模块请定义ARRAY_ITEM_TYPE和P_ARRAY_ITEM, 分别为队列项和队列项指针
**/
#include <stdio.h>
#include "BiArray.H"

/*****************************************************
* 函 数 名 : initBiArray()
* 功    能 : 初始化一个双向队列
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
* 输出参数 : None
* 返 回 值 :
* 描    述 :
*******************************************************/
void initBiArray( BIDIRECT_ARRAY_S * pBidirectArray )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    pBidirectArray->HeadItem->pFrontItem = NULL;
    pBidirectArray->HeadItem->pRearItem  = & pBidirectArray->TailItem;

    pBidirectArray->TailItem->pFrontItem = & pBidirectArray->HeadItem;
    pBidirectArray->TailItem->pRearItem  = NULL;

    pBidirectArray->pCurrentItem = & ( pBidirectArray->HeadItem );
}

/*****************************************************
* 函 数 名 : ResetItem()
* 功    能 : 重新启动一个队列
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
* 输出参数 : None
* 返 回 值 :
* 描    述 : 定义为一个宏庚好?
*******************************************************/
void ResetItem( BIDIRECT_ARRAY_S * pBidirectArray )
{
    pBidirectArray->pCurrentItem = &pBidirectArray->HeadItem;
}

/*****************************************************
* 函 数 名 : AddCurrItem()
* 功    能 : 在双向链表的但前位置加入一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
*            pArrayItem     被加入的节点
* 输出参数 : None
* 返 回 值 :
* 描    述 : 在当前位置<pCurrentItem后>加入一个节点
*******************************************************/
void AddCurrItem( BIDIRECT_ARRAY_S *pBidirectArray, P_ARRAY_ITEM pArrayItem )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    if( NULL == pArrayItem )
    {
        return;
    }

    /* 尾部后不能再加数据 */
if( pBidirectArray->pCurrentItem == & ( pBidirectArray->TailItem ) )
{
    return; /* 加入容错处理更为恰当?*/
}
    pArrayItem->pRearItem = pBidirectArray->pCurrentItem->pRearItem ;
    pBidirectArray->pCurrentItem->pRearItem = pArrayItem;
    pArrayItem->pFrontItem = pBidirectArray->pCurrentItem;
    pArrayItem->pRearItem->pFrontItem = pArrayItem;
}


/*****************************************************
* 函 数 名 : AddHeadItem()
* 功    能 : 在双向链表的头位置加入一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
*            pArrayItem     被加入的节点
* 输出参数 : None
* 返 回 值 :
* 描    述 : 在HeadItem位置后加入一个节点
*******************************************************/
void AddHeadItem( BIDIRECT_ARRAY_S *pBidirectArray, P_ARRAY_ITEM pArrayItem )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    if( NULL == pArrayItem )
    {
        return;
    }

    pArrayItem->pRearItem = pBidirectArray->HeadItem.pRearItem ;
    pBidirectArray->HeadItem.pRearItem = pArrayItem;
    pArrayItem->pFrontItem = & ( pBidirectArray->HeadItem );
    pArrayItem->pRearItem->pFrontItem = pArrayItem;
}

/*****************************************************
* 函 数 名 : AddTailItem()
* 功    能 : 在双向链表的头位置加入一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
*            pArrayItem     被加入的节点
* 输出参数 : None
* 返 回 值 :
* 描    述 : 在TailItem位置前加入一个节点
*******************************************************/
void AddTailItem( BIDIRECT_ARRAY_S *pBidirectArray, P_ARRAY_ITEM pArrayItem )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    if( NULL == pArrayItem )
    {
        return;
    }

    pArrayItem->pRearItem  = & ( pBidirectArray->TailItem );
    pArrayItem->pFrontItem = pBidirectArray->TailItem.pFrontItem;
    pArrayItem->pFrontItem->pRearItem = pArrayItem;
    pBidirectArray->TailItem.pFrontItem = pArrayItem;
}

/*****************************************************
* 函 数 名 : DelCurrItem()
* 功    能 : 删除双向链表当前位置的一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
* 输出参数 : pArrayItem     被删除的节点
* 返 回 值 :
* 描    述 : 删除当前位置<pCurrentItem指向的节点>的节点
*******************************************************/
void DelCurrItem( BIDIRECT_ARRAY_S *pBidirectArray, P_ARRAY_ITEM pArrayItem )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    if( pBidirectArray->HeadItem.pRearItem == & ( pBidirectArray->TailItem ) )
    {
        return;
    }

    /* 尾部和头部都不能删除 */
if( pBidirectArray->pCurrentItem == & ( pBidirectArray->TailItem ) ||
pBidirectArray->pCurrentItem == & ( pBidirectArray-
>HeadItem ) )
{
    return; /* 加入容错处理更为恰当?*/
}

pArrayItem = pBidirectArray->pCurrentItem;

pArrayItem->pFrontItem->pRearItem = pArrayItem->pRearItem;
pArrayItem->pRearItem->pFrontItem = pArrayItem->pFrontItem;

    pBidirectArray->pCurrentItem = pArrayItem->pFrontItem;
}

/*****************************************************
* 函 数 名 : DelHeadItem()
* 功    能 : 删除双向链表头位置的一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
* 输出参数 : pArrayItem     被删除的节点
* 返 回 值 :
* 描    述 : 删除节点HeadItem后的第一个节点
*******************************************************/
void DelHeadItem( BIDIRECT_ARRAY_S *pBidirectArray, P_ARRAY_ITEM pArrayItem )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

/* 如果队列中没有元素, 错误返回 */
    if( pBidirectArray->HeadItem.pRearItem == & ( pBidirectArray->TailItem ) )
    {
        return;
    }

    pArrayItem = pBidirectArray->HeadItem.pRearItem;
    pBidirectArray->HeadItem.pRearItem = pArrayItem->pRearItem;
    pArrayItem->pRearItem->pFrontItem = & ( pBidirectArray->HeadItem );

    if( pArrayItem == pBidirectArray->pCurrentItem )
    {
        pBidirectArray->pCurrentItem = & ( pBidirectArray->HeadItem );
    }
}

/*****************************************************
* 函 数 名 : DelHeadItem()
* 功    能 : 删除双向链表尾位置的一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
* 输出参数 : pArrayItem     被删除的节点
* 返 回 值 :
* 描    述 : 删除节点TailItem前的第一个节点
*******************************************************/
void DelTailItem( BIDIRECT_ARRAY_S *pBidirectArray, P_ARRAY_ITEM pArrayItem )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    if( pBidirectArray->HeadItem.pRearItem == & ( pBidirectArray->TailItem ) )
    {
        return;
    }

pArrayItem = pBidirectArray->TailItem.pFrontItem;
pBidirectArray->TailItem.pFrontItem = pArrayItem->pFrontItem;
pArrayItem->pFrontItem = & ( pBidirectArray->TailItem );

    if( pArrayItem == pBidirectArray->pCurrentItem )
    {
        pBidirectArray->pCurrentItem = pArrayItem->pFrontItem;
    }
}

/*****************************************************
* 函 数 名 : DelHeadItem()
* 功    能 : 当前节点移动置下一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
*            ucMoveStyle    移动风格, 见enuMoveStyle
* 输出参数 :
* 返 回 值 :
* 描    述 :
*******************************************************/
#if 0
void MoveToNext( BIDIRECT_ARRAY_S *pBidirectArray, uchar ucMoveStyle )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    /* 第2个条件说明到达队列尾部 */
    if ( NULL == pBidirectArray->pCurrentItem )
    {
        pBidirectArray->pCurrentItem = & ( pBidirectArray->HeadItem );
        return;
    }

    /* 回滚格式的移动, 如果超过最后一个节点指针将绕回第一个节点 */
    if ( NULL == pBidirectArray->pCurrentItem->pRearItem &&
      MOVE_ROLL_BACK == ucMoveStyle )
    {
        pBidirectArray->pCurrentItem = & ( pBidirectArray->HeadItem );
        return;
    }

    pBidirectArray->pCurrentItem = pBidirectArray->pCurrentItem->pRearItem;
}
#endif
/*****************************************************
* 函 数 名 : DelHeadItem()
* 功    能 : 当前节点移动置前一个节点
* 调    用 : None
* 输入参数 : pBidirectArray 需要初始化的队列成员数据
*            ucMoveStyle    移动风格, 见enuMoveStyle
* 输出参数 :
* 返 回 值 :
* 描    述 :
*******************************************************/
#if 0
void MoveToPrev( BIDIRECT_ARRAY_S *pBidirectArray, uchar ucMoveStyle )
{
    if( NULL == pBidirectArray )
    {
        return;
    }

    if ( NULL == pBidirectArray->pCurrentItem )
    {
        pBidirectArray->pCurrentItem = & ( pBidirectArray->TailItem );
        return;
    }

    /* 回滚格式的移动, 如果超过最前一个节点指针将绕回最后一个节点 */
    if ( NULL == pBidirectArray->pCurrentItem->pFrontItem &&
     MOVE_ROLL_BACK == ucMoveStyle )
    {
        pBidirectArray->pCurrentItem = & ( pBidirectArray->TailItem );
        return;
    }

    pBidirectArray->pCurrentItem = pBidirectArray->pCurrentItem->pFrontItem;
}
#endif