C語言線性表之雙連結串列詳解

2022-02-10 19:00:21

定義

連結串列是通過一組任意的儲存單元來儲存線性表中的資料元素，每一個結點包含兩個域：存放資料元素資訊的域稱為資料域，存放其後繼元素地址的域稱為指標域。因此n個元素的線性表通過每個結點的指標域連線成了一個“鏈條”，稱為連結串列。若此連結串列的每個結點中包含兩個指標域，則被稱為雙連結串列。

雙連結串列的結點結構定義如下：

typedef struct node
{
    DataType data;
    struct node *llink;
    struct node *rlink;
} DLinkList;

像單連結串列一樣，需要一個類似於“頭結點”一樣的結點（記為rear），其資料域為空，指標域的llink指標指向表頭結點，rlink指標指向表尾結點。而表頭結點的llink指標指向NULL，表尾結點的rlink指標指向NULL。

1.刪除

假設結點p是待刪除結點，我們只需讓p的前一個結點的rlink指標（p->llink->rlink）指向p的後一個結點（p->rlink)，並讓p的後一個結點的llink指標（p->rlink->llink）指向p的前一個指標（p->llink），然後釋放p所佔記憶體空間，即可完成刪除操作。因為這是雙連結串列的刪除演演算法，因此待刪除結點在表頭或表尾會有略微的區別，但只要抓住核心演演算法：

p->llink->rlink = p->rlink; p->rlink->llink = p->llink; free(p);

再對錶頭表尾結點進行特殊處理（改變rear指標的指標域）即可。

雙連結串列刪除演演算法範例如下：

int DeleteDLinkList(DLinkList *rear, DLinkList *p)
/*在雙連結串列刪除結點p，成功返回1，否則返回0*/
{
    DLinkList *q = p->rlink, *s = p->llink;/*q指向p的後繼，s指向p的前繼*/
    if (s!=NULL && q==NULL)/*刪除的是最後一個結點*/
    {
        rear->rlink = p->llink;
        p->llink->rlink = p->rlink;
        free(p);
        return 1;
    }
    if (s==NULL && q!=NULL)/*刪除的是第一個結點*/
    {
        rear->llink = p->rlink;
        p->rlink->llink = p->llink;
        free(p);
        return 1;
    }
    if (s==NULL & q==NULL)/*雙連結串列只有一個結點*/
    {
        rear->rlink = rear->llink = NULL;
        free(p);
        return 1;
    }
    if (s!=NULL && q!=NULL)
    {
        p->llink->rlink = p->rlink;
        p->rlink->llink = p->llink;
        free(p);
        return 1;
    }
    return 0;
}

2.插入

假設要把結點q插入到結點p與p的後一個結點之間，需要①先令q的llink指標（q->llink）和rlink指標（q->rlink）分別指向p和p的後一個結點（p->rlink），②再令p的後一個結點的llink指標（p->rlink->llink）指向q，③p的rlink指標（p->rlink）指向q。稍加分析可知，若①②③三個步驟順序錯誤，則無法完成插入。用程式碼錶示就是：

q->llink = p; q->rlink = p->rlink; p->rlink->llink = q; p->rlink = q;

同樣地，若要在表頭或表尾插入元素，則緊抓住核心演演算法稍作改變，並改變rear的指標域即可。

雙連結串列插入演演算法範例如下：

int Insert(DLinkList *rear, DLinkList *p, DataType x)
{
    DLinkList *q = (DLinkList *)malloc(sizeof(DLinkList));
    if (q == NULL)
        return 0;
    q->data = x;/*資料域賦值*/
    if (p->rlink == NULL)/*在表尾插入元素*/
    {
        rear->rlink = q;
        q->llink = p;
        q->rlink = p->rlink;
        p->rlink = q;
        return 1;
    }
    if (p == rear)/*若p為rear，認為在表頭插入元素*/
    {
        q->llink = rear->llink->llink;
        q->rlink = rear->llink;
        rear->llink->llink = q;
        rear->llink = q;
        return 1;
    }
    q->llink = p;
    q->rlink = p->rlink;
    p->rlink->llink = q;
    p->rlink = q;
    return 1;
}

3.建立

利用前面所講在表尾插入元素的辦法，我們可以每建立一個新結點就將其插入到表尾。當剛開始建立雙連結串列時，讓rear的llink指標（rear->llink）指向表頭結點，並讓表頭結點指向NULL；當建立結束時，讓rear的rlink指標（rear->rlink）指向最後一個結點，即可完成雙連結串列的建立。

DLinkList *CreateDLinkList(){    DLinkList *rear, *p, *q;    rear = (DLinkList *)malloc(sizeof(DLinkList));    p = (DLinkList *)malloc(sizeof(DLinkList));    if (rear==NULL || p==NULL)    {        free(rear);        free(p);        return NULL;    }    DataType x;    scanf(&x);    p->data = x;    rear->llink = p;    p->llink = NULL;    p->rlink = NULL;    scanf(&x);    while (x != flag)/*flag為建立結束的標誌*/    {        q = (DLinkList *)malloc(sizeof(DLinkList));        if (q == NULL)        {            DLinkList *pr;            p = rear->llink;            while (p != NULL)            {                pr = p->rlink;                free(p);                p = pr;            }            free(rear);            return NULL;        }        q->data = x;        q->llink = p;        q->rlink = NULL;        p->rlink = q;        scanf(&x);    }    rear->rlink = q;    return rear;}DLinkList *CreateDLinkList()
{
    DLinkList *rear, *p, *q;
    rear = (DLinkList *)malloc(sizeof(DLinkList));
    p = (DLinkList *)malloc(sizeof(DLinkList));
    if (rear==NULL || p==NULL)
    {
        free(rear);
        free(p);
        return NULL;
    }
    DataType x;
    scanf(&x);
    p->data = x;
    rear->llink = p;
    p->llink = NULL;
    p->rlink = NULL;
    scanf(&x);
    while (x != flag)/*flag為建立結束的標誌*/
    {
        q = (DLinkList *)malloc(sizeof(DLinkList));
        if (q == NULL)
        {
            DLinkList *pr;
            p = rear->llink;
            while (p != NULL)
            {
                pr = p->rlink;
                free(p);
                p = pr;
            }
            free(rear);
            return NULL;
        }
        q->data = x;
        q->llink = p;
        q->rlink = NULL;
        p->rlink = q;
        scanf(&x);
    }
    rear->rlink = q;
    return rear;
}

4.查詢

相對於單連結串列，雙連結串列的優勢是可以實現雙向的查詢。假設讓指標p和指標q分別從表頭和表尾向中間遍歷雙連結串列的每一個結點，當p==q或p->llink==q時認為已遍歷結束。

DLinkList *SearchDLinkList(DLinkList *rear, DataType x)
{
    DLinkList *p = rear->llink, *q = rear->rlink;
    while (p->data!=x && q->data!=x)
    {
        p = p->rlink;
        q = q->llink;
        if (p==q || p->llink==q)
            break;
    }
    if (p->data == x)
        return p;
    else if (q->data == x)
        return q;
    else
        return NULL;
}

總結

本篇文章就到這裡了，希望能夠給你帶來幫助，也希望您能夠多多關注it145.com的更多內容

C語言線性表之雙連結串列詳解

目錄

定義

1.刪除

2.插入

3.建立

4.查詢

總結

熱門文章