循環(huán)鏈表與雙向鏈表

循環(huán)鏈表：

循環(huán)鏈表也是一種線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其實他和單鏈表很像，其特點是它是一個環(huán)，也就是指單鏈表的最后一個結(jié)點的指針域不為空，而是指向頭結(jié)點或是第一個結(jié)點，這樣整個鏈表就形成了一個環(huán)。循環(huán)鏈表一般可以分為單循環(huán)鏈表和多循環(huán)鏈表，多循環(huán)鏈表也就是將表中的結(jié)點鏈在多個環(huán)上。

這種方式在單向和雙向鏈表中皆可實現(xiàn)，其轉(zhuǎn)換方法是，選擇從任一結(jié)點開始沿著列表的任一方向直到返回開始的結(jié)點。

除此之外，還有一種模擬的循環(huán)鏈表，就是在訪問最后一結(jié)點之后的時候，手工跳轉(zhuǎn)到第一個結(jié)點，訪問第一個結(jié)點之前的結(jié)點也一樣。通過這樣的方式也可以實現(xiàn)循環(huán)鏈表的功能，在直接運(yùn)用循環(huán)鏈表比較麻煩或者可能會出現(xiàn)問題的時候可以用。

循環(huán)鏈表的操作：

下面主要講單循環(huán)鏈表，單循環(huán)鏈表的操作和單鏈表的操作沒什么區(qū)別，只是循環(huán)結(jié)束的條件判斷不再是判斷指針p或p->next是否為空，而是判斷他們是否等于頭結(jié)點。

有時候，循環(huán)鏈表中會設(shè)置一個指向表尾的尾指針，這樣對某些操作會很方便

代碼實現(xiàn)

其實絕大部分操作和單鏈表都很相像，這里就不在描述，下面可以講講
兩個單循環(huán)鏈表的合并操作

/*
假設(shè)現(xiàn)在有兩個單循環(huán)鏈表AB，將其合并的思路如下
A B分別為單循環(huán)鏈表的尾指針
q = B->next;            //q指向B的頭結(jié)點
B->next = A->next;      //B的指針指向A的頭結(jié)點
A->next = q->next;      //A的尾指針指向B的第一個結(jié)點，即B鏈接到A上
A = B;                  //A指向B，作為合并后鏈表的尾指針
free(q);                //釋放B的頭結(jié)點
                                                        */
LinkList ConnectList(LinkList headA,LinkList headB)
{
    Node *p;
    Node *tailA,*tailB;
    tailA = headA->next;
    tailB = headB->next;
    //分別找到兩個鏈表的尾結(jié)點
    while(tailA->next != headA)     
        tailA = tailA->next;
    while(tailB->next != headB)
        tailB = tailB->next;
    
    p = tailB->next;
    tailB->next = tailA->next;
    tailA->next = p->next;
    tailA = tailB;
    free(p);
    return headA;
}   

雙向鏈表：

在單鏈表中，訪問任一結(jié)點，如果訪問的是后繼結(jié)點，直接通過后繼指針就可以輕松完成此操作（O（1）），如果是訪問其前驅(qū)結(jié)點，就必須從表頭結(jié)點順鏈查找，其實時間復(fù)雜度為O（n），顯然這樣十分不方便，但如果加多一個指針域呢，這樣無論是前驅(qū)結(jié)點還是后繼結(jié)點訪問起來就比較容易了，這種鏈表就是雙向鏈表。

雙向聯(lián)表的描述：

typedef struct dualnode
{
    ElemType data;
    struct dualnode *prior;         //指向前驅(qū)結(jié)點的指針域
    struct dualnode *next;          //指向后繼結(jié)點的指針域
}DNode;
typedef DNode* DLinkList;   

對于帶有頭結(jié)點的雙向鏈表來說，其頭結(jié)點的prior域為NULL，尾結(jié)點的next域為NULL，所以如果是一個空的雙向鏈表的話，兩個指針域都為空。

雙向鏈表轉(zhuǎn)化為循環(huán)鏈表時，雙向循環(huán)鏈表的頭結(jié)點的前驅(qū)指針prior指向表尾結(jié)點，尾結(jié)點的后繼指針指向頭結(jié)點，所以對于一個空的雙向循環(huán)鏈表，頭結(jié)點的兩個指針均指向自身。

雙向鏈表的基本操作：

對于一些向計算表長，獲取元素位置和獲取元素等只涉及一個方向的指針的操作，與單鏈表的操作相同。但是對于插入刪除操作來說比起單鏈表就有較大的差異。

//插入操作
Status ListInsert(DLinkList l,int i,ElemType e)
{
    int k = 1;
    DNode *p,*s;
    p = l->next;
    while(p->next && k<i)
    {
        k++;
        p  = p->next;
    }
    if(k>i || !p)                     //插入位置無效
        return ERROR;
    s = (DNode*)malloc(sizeof(DNode));//為新結(jié)點開辟空間
    s->data = e;
    s->prior = p->prior;              //新結(jié)點的前驅(qū)指針指向p的前驅(qū)結(jié)點
    p->prior->next = s;               //p的前驅(qū)結(jié)點的后繼指針指向新結(jié)點
    s->next = p;                      //新結(jié)點的后繼指針指向p
    p->prior = s;                     //p的前驅(qū)指針指向s
    return OK;
}
//刪除操作
Status DeleteList(DLinkList l,int i,ElemType *e)
{
    int k = 1;
    DNode *p;
    p = l->next;
    while(p->next && k<i)
    {
        p = p->next;
        k++;
    }
    if(!p || k>i)                   //刪除位置無效
        return ERROR;
    *e = p->data;
    p->prior->next = p->next;       //將P的前驅(qū)結(jié)點的后繼指針指向p的后繼結(jié)點
    p->next->prior = p->prior;      //將p的后繼結(jié)點的前驅(qū)指針指向p的前驅(qū)結(jié)點
    free(p);                        //釋放結(jié)點p
    return OK;
}