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

一步一步寫算法(之循環單向鏈表)

編輯:關於C

 

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

 

 

 

 

    前面的博客中,我們曾經有一篇專門講到單向鏈表的內容。那麼今天討論的鏈表和上次討論的鏈表有什麼不同呢?重點就在這個"循環"上面。有了循環,意味著我們可以從任何一個鏈表節點開始工作,可以把root定在任何鏈表節點上面,可以從任意一個鏈表節點訪問數據,這就是循環的優勢。

 

    那麼在實現過程中,循環單向鏈表有什麼不同?

 

    1)打印鏈表數據

 

 

void print_data(const LINK_NODE* pLinkNode) 

    LINK_NODE* pIndex = NULL; 

    if(NULL == pLinkNode) 

        return; 

 

    printf("%d\n", pLinkNode->data); 

    pIndex = pLinkNode->next; 

    while(pLinkNode != pIndex){ 

        printf("%d\n", pIndex->data); 

        pIndex = pIndex ->next; 

    } 

void print_data(const LINK_NODE* pLinkNode)

{

       LINK_NODE* pIndex = NULL;

       if(NULL == pLinkNode)

              return;

 

       printf("%d\n", pLinkNode->data);

       pIndex = pLinkNode->next;

       while(pLinkNode != pIndex){

              printf("%d\n", pIndex->data);

              pIndex = pIndex ->next;

       }

}    以往,我們發現打印數據的結束都是判斷指針是否為NULL,這裡因為是循環鏈表所以發生了變化。原來的條件(NULL != pLinkNode)也修改成了這裡的(pLinkNode != pIndex)。同樣需要修改的函數還有find函數、count統計函數。

 

 

 

 

    2)插入數據

 

 

STATUS insert_data(LINK_NODE** ppLinkNode, int data) 

    LINK_NODE* pNode; 

    if(NULL == ppLinkNode) 

        return FALSE; 

 

    if(NULL == *ppLinkNode){ 

        pNode = create_link_node(data); 

        assert(NULL != pNode); 

 

        pNode->next = pNode; 

        *ppLinkNode = pNode; 

        return TRUE; 

    } 

 

    if(NULL != find_data(*ppLinkNode, data)) 

        return FALSE; 

 

    pNode = create_link_node(data); 

    assert(NULL != pNode); 

 

    pNode->next = (*ppLinkNode)->next; 

    (*ppLinkNode)->next = pNode; 

    return TRUE; 

STATUS insert_data(LINK_NODE** ppLinkNode, int data)

{

       LINK_NODE* pNode;

       if(NULL == ppLinkNode)

              return FALSE;

 

       if(NULL == *ppLinkNode){

              pNode = create_link_node(data);

              assert(NULL != pNode);

 

              pNode->next = pNode;

              *ppLinkNode = pNode;

              return TRUE;

       }

 

       if(NULL != find_data(*ppLinkNode, data))

              return FALSE;

 

       pNode = create_link_node(data);

       assert(NULL != pNode);

 

       pNode->next = (*ppLinkNode)->next;

       (*ppLinkNode)->next = pNode;

       return TRUE;

}這裡的insert函數在兩個地方發生了變化:

 

    a)如果原來鏈表中沒有節點,那麼鏈表節點需要自己指向自己

 

    b)如果鏈表節點原來存在,那麼只需要在當前的鏈表節點後面添加一個數據,同時修改兩個方向的指針即可

 

 

 

 

    3) 刪除數據

 

 

STATUS delete_data(LINK_NODE** ppLinkNode, int data) 

    LINK_NODE* pIndex = NULL; 

    LINK_NODE* prev = NULL; 

    if(NULL == ppLinkNode || NULL == *ppLinkNode) 

        return FALSE; 

 

    pIndex = find_data(*ppLinkNode, data); 

    if(NULL == pIndex) 

        return FALSE; 

 

    if(pIndex == *ppLinkNode){ 

        if(pIndex == pIndex->next){ 

            *ppLinkNode = NULL; 

        }else{ 

            prev = pIndex->next; 

            while(pIndex != prev->next) 

                prev = prev->next; 

 

            prev->next = pIndex->next; 

            *ppLinkNode = pIndex->next; 

        } 

    }else{ 

        prev = pIndex->next; 

        while(pIndex != prev->next) 

            prev = prev->next; 

        prev->next = pIndex->next; 

    } 

 

    free(pIndex); 

    return TRUE; 

STATUS delete_data(LINK_NODE** ppLinkNode, int data)

{

       LINK_NODE* pIndex = NULL;

       LINK_NODE* prev = NULL;

       if(NULL == ppLinkNode || NULL == *ppLinkNode)

              return FALSE;

 

       pIndex = find_data(*ppLinkNode, data);

       if(NULL == pIndex)

              return FALSE;

 

       if(pIndex == *ppLinkNode){

              if(pIndex == pIndex->next){

                     *ppLinkNode = NULL;

              }else{

                     prev = pIndex->next;

                     while(pIndex != prev->next)

                            prev = prev->next;

 

                     prev->next = pIndex->next;

                     *ppLinkNode = pIndex->next;

              }

       }else{

              prev = pIndex->next;

              while(pIndex != prev->next)

                     prev = prev->next;

              prev->next = pIndex->next;

       }

 

       free(pIndex);

       return TRUE;

}和添加數據一樣,刪除數據也要在兩個方面做出改變:

 

    a)如果當前鏈表節點中只剩下一個數據的時候,刪除後需要設置為NULL

 

 

    b)刪除數據的時候首先需要當前數據的前一個數據,這個時候就可以從當前刪除的數據開始進行遍歷

 

    c) 刪除的時候需要重點判斷刪除的數據是不是鏈表的頭結點數據

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