雙向循環鏈表

循環雙向鏈表如下圖所示：

 大家通過圖來看與循環單鏈表基本是一樣，代碼的套路也基本一樣，除了每個節點都多一個前驅。
 很多和我一樣的初學者都很困惑，單鏈表，雙鏈表，還有循環鏈表為什么搞那么復雜，很簡單因為需求。
 學編程你不得不時刻容納新知識，很多人沒有去深入去學習，就像沒有驅動一樣。有單向就有雙向，有雙向就有循環，更多的需求讓大家進步，就像人不懂得滿足。
 有些人問我，為什么別人能夠把代碼邏輯寫的清晰，為什么如何別人能夠那么優秀，很多人說：練習的多，敲代碼量大，不得不否認確實有這方面因素，但是我認為思考更為重要。大量的思考讓這些編程員中腦子可以浮動出任何的算法與數據結構，這也許才是真正的靈魂。
 扯遠了，再來一張構造雙向鏈表的圖，因為與單鏈表不同，所以格外做了一張圖讓剛學習的朋友們刪除等參考，分享更多的知識。

代碼如下：

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node *next;
    struct Node *prior;
}Node,*PNode;

void ControlLinkList(PNode PHead);                      //控制函數
PNode CreateLinkList(void);                             //構造雙向循環鏈表
int PositionLinkList(PNode PHead);                      //正向遍歷
void ReverseLinkList(PNode PHead);                      //逆向遍歷
void InsertLinkList(PNode PHead, int pos, int len);     //插入某節點
void DeleteLinkList(PNode PHead, int pos);              //刪除某節點
void FindDLinkList(PNode PHead, int pos);               //查詢某節點
void ReleaseLinkList(PNode PHead);                      //釋放鏈表
void ReversesLinkList(PNode PHaed);                     //反轉鏈表--對于循環雙向鏈表反轉沒有太大意義

int main(void)
{

    PNode PHead = CreateLinkList();
    ControlLinkList(PHead);
    return 0;
}

PNode CreateLinkList(void)
{
    int len = 0;
    int i;
    PNode PHead = (PNode)malloc(sizeof(Node));
    PNode r;
    if( NULL == PHead )
    {
        printf("分配內存失敗\n");
        exit(EXIT_FAILURE);
    }
    //初始化頭
    PHead->data = 0;
    PHead->prior = PHead;
    PHead->next = PHead;
    r = PHead;

    printf("請輸入構造幾個節點: ");
    scanf("%d",&len);

    for( i = 0; i < len; i++ )
    {
        PNode p = (PNode)malloc(sizeof(Node));
        if( NULL == p )
        {
            printf("分配內存失敗\n");
            exit(EXIT_FAILURE);
        }

        printf("Please input of data: ");
        scanf("%d",&p->data);

        p->next = NULL;                             //后驅為NULL
        p->prior = r;                               //前驅指向r也就是PHead頭節點
        r->next = p;                                //然后r的后驅也就PHead的后驅指向p
        r = p;                                      //最后r = p;
    }
    r->next = PHead;
    PHead->prior = r;                               //這兩步完成了鏈表循環，頭尾想指
    return PHead;                                   //循環雙向鏈表返回頭指針既可以正向反向遍歷
}

int PositionLinkList(PNode PHead)
{
    int i = 0;
    PNode p = PHead->next;                          //PHead->next才是鏈表第一個元素
    while( NULL != p && PHead != p )
    {
        i++;
        printf("No.%d of Data = %d\n",i,p->data);
        p = p->next;
    }
    printf("正向遍歷成功");
    return i;
}

void ReverseLinkList(PNode PHead)
{
    int i = 0;
    PNode p = PHead->prior;                         //指向了鏈表尾部r
    while( NULL != p && p != PHead )
    {
        i++;
        printf("No.%d of Data = %d\n",i,p->data);
        p = p->prior;
    }
    printf("逆向遍歷成功\n");
}

void InsertLinkList(PNode PHead, int pos, int data)
{
    int i = 1;
    PNode p = PHead->next;
    PNode PNew = (PNode)malloc(sizeof(Node));
    if( NULL == p )
    {
        printf("內存分配失敗\n");
        exit(EXIT_FAILURE);
    }

    while( p != NULL && i != pos-1 )
    {
        i++;
        p = p->next;
    }

    PNew->data = data;
    p->next->prior = PNew;
    PNew->next = p->next;
    p->next = PNew;
    PNew->prior = p;

    printf("插入成功\n");
}

void FindLinkList(PNode PHead, int pos)
{
    PNode p = PHead->next;
    int i = 1;
    while( NULL !=p && i != pos )
    {
        i++;
        p = p->next; 
    }
    printf("No.%d of Data = %d\n", i, p->data);
}

void DeleteLinkList(PNode PHead, int pos)
{
    int i = 1;
    PNode p = PHead->next;
    PNode temp;
    while( NULL !=p && i != pos )
    {
        i++;
        p = p->next;
    }

    temp = p->next;                     //temp指向刪除的節點
    p->next = p->next->next;            //p->next節點指向刪除節點的next
    p->next->next->prior = p;   
    free(temp);
    printf("刪除節點成功\n");
}

void ReleaseLinkList(PNode PHead)
{
    PNode p,q;
    p = PHead;
    q = p->next;
    while( q != PHead )
    {
        p = q;
        q = p->next;
        free(p);
    }
    free(PHead);
    printf("釋放內存成功");
}

void ControlLinkList(PNode PHead)
{
    int len = 0;
    int pos = 0;
    len = PositionLinkList(PHead);
    ReverseLinkList(PHead);
    printf("請輸入pos節點:  ");
    scanf("%d",&pos);
    InsertLinkList(PHead, pos, 10);
    PositionLinkList(PHead);
    printf("請輸入查詢的節點:  ");
    scanf("%d",&pos);
    FindLinkList(PHead, pos);
    printf("請輸入刪除的節點:  ");
    scanf("%d",&pos);
    DeleteLinkList(PHead, pos);
    PositionLinkList(PHead);
    ReleaseLinkList(PHead);
}