程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C語言實現雙向非循環鏈表（帶頭結點尾結點）的操作方法

C語言實現雙向非循環鏈表（帶頭結點尾結點）的操作方法

編輯：關於C

我在之前一篇博客中詳細實現了不帶頭尾節點的雙向非循環鏈表的很多操作。其實同單鏈表一樣，不帶頭結點的鏈表很多操作都是比較麻煩的，常常需要對第一個節點做額外的判斷，提高了出錯的成本。今天我們要來實現帶頭結點尾結點的雙向非循環鏈表的操作，雖然額外維護了兩個節點，但是操作的簡便性大大提高了。代碼上傳至 https://github.com/chenyufeng1991/DoubleLinkedList_HeadList 。

（1）定義帶頭結點尾結點的非循環雙向鏈表的節點類型

typedef int elemType;
typedef struct NodeList{

    int element;
    struct NodeList *prior;
    struct NodeList *next;
}Node;

（2）初始化雙鏈表

//1.初始化帶頭結點和尾結點的非循環雙向鏈表
void InitialList(Node **pHead,Node **pTail){

    *pHead = (Node *)malloc(sizeof(Node));
    *pTail = (Node *)malloc(sizeof(Node));

    if (*pHead == NULL || *pTail == NULL) {
        printf("%s函數執行，內存分配失敗，初始化雙鏈表失敗\n",__FUNCTION__);
    }else{
        //這個裡面是關鍵，也是判空的重要條件
        (*pHead)->prior = NULL;
        (*pTail)->next = NULL;

        //鏈表為空的時候把頭結點和尾結點連起來
        (*pHead)->next = *pTail;
        (*pTail)->prior = *pHead;

        printf("%s函數執行，帶頭結點和尾節點的雙向非循環鏈表初始化成功\n",__FUNCTION__);
    }
}

（3）尾插法創建雙鏈表

//2.創建帶頭結點和尾結點的雙向非循環鏈表
void CreateList(Node *pHead,Node *pTail){

    Node *pInsert;
    Node *pMove;
    pInsert = (Node*)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->prior = NULL;
    pInsert->next = NULL;

    scanf("%d",&(pInsert->element));
    pMove = pHead;
    while (pInsert->element > 0) {

        pMove->next = pInsert;
        pInsert->prior = pMove;
        pInsert->next = pTail;
        pTail->prior = pInsert;
        pMove = pInsert;

        pInsert = (Node *)malloc(sizeof(Node));
        memset(pInsert, 0, sizeof(Node));
        pInsert->prior = NULL;
        pInsert->next = NULL;

        scanf("%d",&(pInsert->element));
    }

    printf("%s函數執行完成，帶頭節點和尾結點的雙向非循環鏈表創建成功\n",__FUNCTION__);

}

（4）正序打印鏈表

//3.正序打印鏈表
void PrintList(Node *pHead,Node *pTail){

    Node *pMove;
    pMove = pHead->next;
    while (pMove != pTail) {
        printf("%d ",pMove->element);
        pMove = pMove->next;
    }

    printf("\n%s函數執行，正序打印帶頭結點尾結點的雙向非循環鏈表創建成功\n",__FUNCTION__);
}

（5）逆序打印鏈表

//4.逆序打印鏈表
void PrintReverseList(Node *pHead,Node *pTail){

    Node *pMove;
    pMove = pTail->prior;
    while (pMove != pHead) {
        printf("%d ",pMove->element);
        pMove = pMove->prior;
    }

    printf("\n%s函數執行，逆序打印帶頭結點尾結點的雙向非循環鏈表創建成功\n",__FUNCTION__);
}

（6）清空節點，使成為空表

//5.清除鏈表中的所有元素，使成為空表
void ClearList(Node *pHead,Node *pTail){

    Node *pMove;
    pMove = pHead->next;

    while (pMove != pTail) {

        pHead->next = pMove->next;
        pMove->next->prior = pHead;
        free(pMove);
        pMove = pHead->next;
    }

    printf("%s函數執行，雙向非循環鏈表清空成功\n",__FUNCTION__);
}

（7）計算鏈表長度

//6.計算鏈表的長度
int SizeList(Node *pHead,Node *pTail){

    int i = 0;
    Node *pMove;
    pMove = pHead->next;
    while (pMove != pTail) {
        i++;
        pMove = pMove->next;
    }
    printf("%s函數執行，鏈表的長度為%d\n",__FUNCTION__,i);

    return i;
}

（8）判斷鏈表是否為空

//7.判斷帶頭結點尾結點的雙向非循環鏈表是否為空,為空返回1，否則返回0
int IsEmptyList(Node *pHead,Node *pTail){
    if (pHead->next == pTail) {

        printf("%s函數執行，當前鏈表為空\n",__FUNCTION__);
        return 1;
    }

    printf("%s函數執行，當前鏈表不為空\n",__FUNCTION__);
    return 0;
}

（9）返回鏈表中pos位置的元素

//8.返回鏈表中第pos個結點中的元素，若返回-1，表示沒有找到
int GetElement(Node *pHead,Node *pTail,int pos){

    int i = 1;
    Node *pMove;
    pMove = pHead->next;
    while (pMove != pTail) {
        if (i == pos) {
            printf("%s函數執行，第pos=%d位置的元素為%d\n",__FUNCTION__,pos,pMove->element);
            return pMove->element;
        }
        i++;
        pMove = pMove->next;
    }

    printf("%s函數執行，查找第pos=%d位置元素失敗\n",__FUNCTION__,pos);

    return -1;
}

（10）查找值為x的節點，如果存在則返回地址

//9.從鏈表中查找給定值x的第一個元素，並返回data域的內存地址，否則返回NULL
int *GetElemAddr(Node *pHead,Node *pTail,int x){

    Node *pMove;
    pMove = pHead->next;
    while (pMove != pTail) {
        if (pMove->element == x) {
            printf("%s函數執行，值為%d的元素內存地址為0x%x\n",__FUNCTION__,x,&(pMove->element));
            return &(pMove->element);
        }
        pMove = pMove->next;
    }

    printf("%s函數執行，查找值為%d的元素地址失敗\n",__FUNCTION__,x);

    return NULL;
}

（11）把pos節點的值改為x

//10.把鏈表中第pos個節點的值修改為x
int ModifyElem(Node *pHead,Node *pTail,int pos,int x){

    int i = 1;
    Node *pMove;
    pMove = pHead->next;
    while (pMove != pTail) {
        if (i == pos) {

            pMove->element = x;
            printf("%s函數執行，修改pos=%d位置值為%d成功\n",__FUNCTION__,pos,x);
            return 1;
        }
        i++;
        pMove = pMove->next;
    }

    printf("%s函數執行，修改pos=%d位置元素失敗\n",__FUNCTION__,pos);

    return -1;
}

（12）表頭插入一個元素

//11.向鏈表的表頭插入一個元素
int InsertHeadList(Node *pHead,Node *pTail,int x){

    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->element = x;
    pInsert->prior = NULL;
    pInsert->next = NULL;

    pInsert->next = pHead->next;
    pHead->next->prior = pInsert;
    pHead->next = pInsert;
    pInsert->prior = pHead;

    printf("%s函數執行，在表頭插入%d成功\n",__FUNCTION__,x);
    return 1;
}

（13）表尾插入一個元素

//12.向鏈表的表尾插入一個元素
int InsertTailList(Node *pHead,Node *pTail,int x){

    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->element = x;
    pInsert->prior = NULL;
    pInsert->next = NULL;

    pTail->prior->next = pInsert;
    pInsert->prior = pTail->prior;
    pInsert->next = pTail;
    pTail->prior = pInsert;

    printf("%s函數執行，在表尾插入%d成功\n",__FUNCTION__,x);

    return 1;
}

（14）測試代碼

int main(int argc, const char * argv[]) {

    Node *pHead;//頭結點
    Node *pTail;//尾結點

    InitialList(&pHead, &pTail);

    CreateList(pHead, pTail);
    PrintList(pHead, pTail);
    PrintReverseList(pHead,pTail);

    SizeList(pHead, pTail);

    IsEmptyList(pHead,pTail);

    GetElement(pHead, pTail, 2);

    GetElemAddr(pHead, pTail, 5);

    ModifyElem(pHead, pTail, 2, 111);
    PrintList(pHead, pTail);
    
    InsertHeadList(pHead,pTail,100);
    PrintList(pHead, pTail);

    InsertTailList(pHead,pTail,900);
    PrintList(pHead, pTail);
    
    ClearList(pHead,pTail);
    PrintList(pHead, pTail);
    IsEmptyList(pHead,pTail);
    
    return 0;
}