雙向循環連結清單

雙向循環連結清單的實作方式及執行個體

• 1.雙向連結清單的介紹
• • （1）雙向連結清單節點結構
  • （2）插入結點
  • （3）删除結點
• 2.雙向循環連結清單實踐

1.雙向連結清單的介紹

（1）雙向連結清單節點結構

typedef struct DualNode
{
	ElemType data;
	struct DaulNode *prior;  //前驅結點；
	struct DaulNode	*next;   //後繼結點
}DualNode;
           

非空的雙循環連結清單

（2）插入結點

插入操作不複雜，不過順序很重要，千萬不能寫反，思路就是這樣

• 先處理插入結點的前後指向
• 再讓前面的指向自己，讓後面的指向自己

s->next = p;   //讓結點指向插入位置的後面結點
s->prior = p->prior;  //讓結點指向插入位置前面的結點
p->prior->next = s;  //讓前面的結點指向自己
p->prior = s;   //讓後面的結點指向自己
           

（3）删除結點

思路如下：

• 讓上一個指向結點的下一個
• 讓結點的下一個再指向節點的上一個

p->prior->next = p->next; 
p->next->prior = p->prior;
free(p);
           

2.雙向循環連結清單實踐

實驗要求：

要求輸入一個數字，使得26個字母排列發生變化，例如：

• 輸入3，向左移3位DEFGHIJKLMNOPQRSTUVWXYZABC
• 輸入-3，向右移3位XYZABCDEFGHIJKLMNOPQRSTUVW

示意圖：

p指針先指向頭結點，此後不斷标記新建立結點的位置；最後的Z結點的後繼指向A，A的前驅指向Z完成循環

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

#define OK      1
#define ERROR   0   

typedef char    ElemType;

typedef struct DaulNode
{
    ElemType    data;
    struct DaulNode *prior;
    struct DaulNode *next;
}DualNode, *DuLinkList;

int InitList(DuLinkList *L)
{
    DualNode    *p, *q;
    int         i;

    *L = (DuLinkList)malloc(sizeof(DualNode)); //生成頭結點
    if(!(*L))
    {
        return ERROR;
    }

    (*L)->next = (*L)->prior = NULL; //形成空雙向循環連結清單
    p = (*L);  //标記位置

    for(i = 0; i < 26; i++)
    {
        q = (DuLinkList)malloc(sizeof(DualNode)); //建立插入節點
        if(!q)
        {
            return ERROR;
        }

        q->data = 'A' + i; //指派ABCD...
        q->prior = p;   //讓q指向上一個， 就是頭結點（p就是頭結點的标記）
        q->next = p->next; //讓q指向下一個，就是頭結點指向的下一個
        p->next = q; //最後讓上一個結點指向自己q

        p = q; //标記新建立結點的位置
    }

    p->next = (*L)->next;  //這兩步就是形成循環，A Z相接
    (*L)->next->prior = p;

    (*L) = p;//為後面i<0做準備
    return OK;
}
void Case(DuLinkList *L, int i)
{
    if(i>0)
    {
        do
        {
            (*L) = (*L)->next; //頭結點不斷右移，整個連結清單向左移動（DFF...ABC）
        }while(--i);
    }

    if(i<0)
    {

        do
        {
            (*L) = (*L)->prior;//p的前驅變成了（*L）的前驅，原本頭結點沒有前驅的，這樣頭結點的前驅就可以指向ZYX...
        }while(++i);    //整個頭結點不斷左移，整個連結清單向右移動（XYZABC）
    }
}


int main()
{
    DuLinkList L;
    int        i, n;

    InitList(&L);

    printf("請輸入一個整數\n");
    scanf("%d", &n);
    printf("\n");
    Case(&L, n);

    for(i=0; i<26; i++)
    {
        L = L->next;
        printf("%c", L->data);
    }
    printf("\n");

    return OK;
           

列印結果