程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 一步一步寫算法(之雙向鏈表)

一步一步寫算法(之雙向鏈表)

編輯:關於C語言

 

【 聲明:版權所有,歡迎轉載,請勿用於商業用途。  聯系信箱:feixiaoxing @163.com】

 

 

 

 

    前面的博客我們介紹了單向鏈表。那麼我們今天介紹的雙向鏈表,顧名思義,就是數據本身具備了左邊和右邊的雙向指針。雙向鏈表相比較單向鏈表,主要有下面幾個特點:

 

    (1)在數據結構中具有雙向指針

 

    (2)插入數據的時候需要考慮前後的方向的操作

 

    (3)同樣,刪除數據的是有也需要考慮前後方向的操作

 

    那麼,一個非循環的雙向鏈表操作應該是怎麼樣的呢?我們可以自己嘗試一下:

 

    (1)定義雙向鏈表的基本結構

 

 

typedef struct _DOUBLE_LINK_NODE 

    int data; 

    struct _DOUBLE_LINK_NODE* prev; 

    struct _DOUBLE_LINK_NODE* next; 

}DOUBLE_LINK_NODE; 

typedef struct _DOUBLE_LINK_NODE

{

       int data;

       struct _DOUBLE_LINK_NODE* prev;

       struct _DOUBLE_LINK_NODE* next;

}DOUBLE_LINK_NODE;    (2)創建雙向鏈表節點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; 

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); 

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)在雙向鏈表中查找數據

 

 

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; 

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)雙向鏈表中插入數據

 

 

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; 

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)雙向鏈表中刪除數據

 

 

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; 

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)統計雙向鏈表中數據的個數

 

 

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; 

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)打印雙向鏈表中數據

 

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; 

    } 

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;

       }

}    注意:

 

        今天我們討論的雙向鏈表是非循環的,大家可以考慮一下如果改成循環雙向鏈表,應該怎麼寫?如果是有序的循環雙向鏈表,又該怎麼寫?

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved