資料結構——循環連結清單的那些事

目錄

一、循環單連結清單

二、循環雙連結清單

三、插入與删除

四、總結

一、循環單連結清單

單連結清單：表尾結點的next指針指向NULL

循環單連結清單：表尾結點的next指針指向頭結點

typedef struct LNode{    //定義單連結清單結點類型
    ElemType data;        //每個節點存放一個資料元素
    struct LNode *next;        //指針指向下一個節點
}LNode, *LinkList;

//初始化一個循環單連結清單
bool InitList(LinkList &L){        
    L = (LNode *)malloc(sizeof(LNode));    //配置設定一個頭結點
    if(L == NULL)        
        return false;
    L->next = L;        //頭結點next指向頭結點
    return true;
}
           

思路：

和單連結清單初始化類似，差別在于頭結點next指向自己，形成循環

單連結清單和循環連結清單的對比：

單連結清單：從一個結點出發隻能找到後續的各個結點

循環單連結清單：從一個結點出發可以找到其他任何一個結點

二、循環雙連結清單

雙連結清單：表頭結點的prior指向NULL，表尾結點的next指向NULL

循環雙連結清單：表頭結點的prior指向表尾結點，表尾結點的next指向頭結點

//初始化空的循環雙連結清單
bool InitDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode));        //配置設定一個頭結點
    if(L == NULL)        //記憶體不足，配置設定失敗
        return false;
    L->prior = L;        //頭結點的prior指向頭結點
    L->next = L;        //頭結點的next指向頭結點
    return true;
}

void testDLinkList(){
    //初始化循環雙連結清單
    DLinklist L;
    InitDLinkList(L);
}

//判斷循環雙連結清單是否為空
bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
}
           

思路：

初始化時，頭結點的前驅和後繼指針指向自己

三、插入與删除

1.插入

bool InsertNextDNode(DNode *p,DNode *s){
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}
           

2.删除

bool DeleteNextDNode(DNode *p,DNode *s){
    p->next = q->next;
    q->next->prior = p;
    free(q);
}
           

四、總結