c++雙向鏈表操作示例(創(chuàng)建雙向鏈、雙向鏈表中查找數(shù)據(jù)、插入數(shù)據(jù)等)

更新時間：2014年05月07日 10:46:27 作者：

這篇文章主要介紹了c++雙向鏈表操作示例，包括創(chuàng)建雙向鏈、刪除雙向鏈表、雙向鏈表中查找數(shù)據(jù)、插入數(shù)據(jù)等,需要的朋友可以參考下

雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)造雙向循環(huán)鏈表。

（1）定義雙向鏈表的基本結(jié)構(gòu)

復制代碼代碼如下:

typedef struct _DOUBLE_LINK_NODE  
{  
    int data;  
    struct _DOUBLE_LINK_NODE* prev;  
    struct _DOUBLE_LINK_NODE* next;  
}DOUBLE_LINK_NODE;  

（2）創(chuàng)建雙向鏈表節(jié)點

復制代碼代碼如下:

DOUBLE_LINK_NODE* create_double_link_node(int value)
{
    DOUBLE_LINK_NODE* pDLinkNode = NULL;
    pDLinkNode = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
    assert(NULL != pDLinkNode);

    memset(pDLinkNode, 0, sizeof(DOUBLE_LINK_NODE));
    pDLinkNode->data = value;
    return pDLinkNode;
}

（3）刪除雙向鏈表

復制代碼代碼如下:

void delete_all_double_link_node(DOUBLE_LINK_NODE** pDLinkNode)
{
    DOUBLE_LINK_NODE* pNode;
    if(NULL == *pDLinkNode)
        return ;

    pNode = *pDLinkNode;
    *pDLinkNode = pNode->next;
    free(pNode);
    delete_all_double_link_node(pDLinkNode);
}

（4）在雙向鏈表中查找數(shù)據(jù)

復制代碼代碼如下:

DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data)
{
    DOUBLE_LINK_NODE* pNode = NULL;
    if(NULL == pDLinkNode)
        return NULL;

    pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
    while(NULL != pNode){
        if(data == pNode->data)
            return pNode;
        pNode = pNode ->next;
    }

return NULL;
}

（5）雙向鏈表中插入數(shù)據(jù)

復制代碼代碼如下:

STATUS insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
DOUBLE_LINK_NODE* pNode;
DOUBLE_LINK_NODE* pIndex;

if(NULL == ppDLinkNode)
return FALSE;

    if(NULL == *ppDLinkNode){
        pNode = create_double_link_node(data);
        assert(NULL != pNode);
        *ppDLinkNode = pNode;
        (*ppDLinkNode)->prev = (*ppDLinkNode)->next = NULL;
        return TRUE;
    }

if(NULL != find_data_in_double_link(*ppDLinkNode, data))
return FALSE;

pNode = create_double_link_node(data);
assert(NULL != pNode);

    pIndex = *ppDLinkNode;
    while(NULL != pIndex->next)
        pIndex = pIndex->next;

    pNode->prev = pIndex;
    pNode->next = pIndex->next;
    pIndex->next = pNode;
    return TRUE;
}

（6）雙向鏈表中刪除數(shù)據(jù)

復制代碼代碼如下:

STATUS delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data)
{
    DOUBLE_LINK_NODE* pNode;
    if(NULL == ppDLinkNode || NULL == *ppDLinkNode)
        return FALSE;

    pNode = find_data_in_double_link(*ppDLinkNode, data);
    if(NULL == pNode)
        return FALSE;

    if(pNode == *ppDLinkNode){
        if(NULL == (*ppDLinkNode)->next){
            *ppDLinkNode = NULL;
        }else{
            *ppDLinkNode = pNode->next;
            (*ppDLinkNode)->prev = NULL;
        }

    }else{
        if(pNode->next)
            pNode->next->prev = pNode->prev;
        pNode->prev->next = pNode->next;
    }

free(pNode);
return TRUE;
}

（7）統(tǒng)計雙向鏈表中數(shù)據(jù)的個數(shù)

復制代碼代碼如下:

int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode)
{
int count = 0;
DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

    while(NULL != pNode){
        count ++;
        pNode = pNode->next;
    }
    return count;
}

（8）打印雙向鏈表中數(shù)據(jù)

復制代碼代碼如下:

void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode)
{
DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;

    while(NULL != pNode){
        printf("%d\n", pNode->data);
        pNode = pNode ->next;
    }
}

今天我們討論的雙向鏈表是非循環(huán)的，大家可以考慮一下如果改成循環(huán)雙向鏈表，應該怎么寫？如果是有序的循環(huán)雙向鏈表，又該怎么寫？

您可能感興趣的文章: