程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言實現非循環雙鏈表節點的刪除(不帶頭結點)

C語言實現非循環雙鏈表節點的刪除(不帶頭結點)

編輯:關於C語言

C語言實現非循環雙鏈表節點的刪除(不帶頭結點)


不帶頭結點的非循環雙鏈表在刪除節點的時候比價麻煩,因為同時要維護prior和next兩個指針。在處理第一個節點和最後一個節點的時候都要分別考慮,同時也需要考慮節點數量為1的情況。刪除情況分為下面兩類:

(1)刪除pos位置的節點;

(2)判斷x是否在鏈表中,若存在則刪除;

核心代碼如下:

//刪除pos位置的節點
Node *deletePosList(Node *pNode,int pos){
    //注意需要單獨考慮第一個節點和最後一個節點

    int i = 1;
    int size = sizeList(pNode);
    Node *pMove;
    pMove = pNode;

    //鏈表為空
    if (pNode == NULL) {
        printf("%s函數執行,鏈表為空,刪除節點失敗\n",__FUNCTION__);
        return pNode;
    }

    //鏈表只有一個節點,刪除第一個節點
    if (pos == 1 && size == 1) {

        free(pNode);
        pNode = NULL;
        printf("%s函數執行,刪除pos=%d位置的節點成功\n",__FUNCTION__,pos);
        return NULL;
    }

    //鏈表節點大於1,刪除第一個節點
    if (pos == 1) {

        pNode = pNode->next;
        pNode->prior = NULL;
        free(pMove);
        pMove = NULL;
        printf("%s函數執行,刪除pos=%d位置的節點成功\n",__FUNCTION__,pos);
        return pNode;
    }

    while (pMove != NULL) {
        if (i == pos && pos != size) {

            pMove->prior->next = pMove->next;
            pMove->next->prior = pMove->prior;
            free(pMove);
            pMove->next = NULL;

            printf("%s函數執行,刪除pos=%d位置的節點成功\n",__FUNCTION__,pos);
            return pNode;
        }

        if (i == pos && pos == size) {
            pMove->prior->next = NULL;
            free(pMove);
            pMove = NULL;
            printf("%s函數執行,刪除pos=%d位置的節點成功\n",__FUNCTION__,pos);
            return pNode;
        }

        i++;
        pMove = pMove->next;
    }

    printf("%s函數執行,刪除pos=%d位置的節點失敗\n",__FUNCTION__,pos);
    return pNode;
}

//判斷x是否在鏈表中,存在則刪除之
Node *deleteValueList(Node *pNode,int x){

    Node *pMove;
    pMove = pNode;
    int size = sizeList(pNode);

    //原鏈表為空
    if (pNode == NULL) {
        printf("%s函數執行,原鏈表為空,刪除節點失敗\n",__FUNCTION__);
        return NULL;
    }

    //刪除的是第一個節點,並且鏈表長度為1
    if (pNode->element == x && size == 1) {

        free(pNode);
        pNode = NULL;
        printf("%s函數執行,刪除值為%d節點成功\n",__FUNCTION__,x);
        return pNode;
    }

    //單獨考慮刪除第一個節點的情況,且鏈表長度大於1
    if (pNode->element == x) {
        pNode = pNode->next;
        free(pNode->prior);
        pNode->prior = NULL;

        printf("%s函數執行,刪除值為%d節點成功\n",__FUNCTION__,x);
        return pNode;
    }

    while (pMove != NULL) {
        //要刪除的節點不是最後一個
        if (pMove->element == x && pMove->next != NULL) {

            pMove->prior->next = pMove->next;
            pMove->next->prior = pMove->prior;
            free(pMove);
            pMove = NULL;
            printf("%s函數執行,刪除值為%d節點成功\n",__FUNCTION__,x);
            return pNode;
        }

        //要刪除的是最後一個節點
        if (pMove->element == x && pMove->next == NULL) {

            pMove->prior->next = NULL;
            free(pMove);
            pMove = NULL;
            printf("%s函數執行,刪除值為%d節點成功\n",__FUNCTION__,x);
            return pNode;
        }
        pMove = pMove->next;
    }

    printf("%s函數執行,刪除值為%d節點失敗\n",__FUNCTION__,x);
    return pNode;
}

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