雙向鏈表

一、雙向鏈表結(jié)構(gòu)

雙向鏈表結(jié)點(diǎn)結(jié)構(gòu)

typedef struct DualNode
{
    ElemType data;
    struct DualNode *prior;  //前驅(qū)結(jié)點(diǎn)
    struct DualNode *next;   //后繼結(jié)點(diǎn)
} DualNode, *DuLinkList;

雙向鏈表結(jié)點(diǎn)結(jié)構(gòu).png

既然單鏈表可以有循環(huán)鏈表，那么雙向鏈表當(dāng)然也可以有。

非空的雙循環(huán)鏈表.png

由于這是雙向鏈表，那么對(duì)于鏈表中的某一個(gè)結(jié)點(diǎn)p，它的后繼結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)是它本身。

二、雙向鏈表的插入操作

插入操作.jpg

代碼實(shí)現(xiàn)：

s->next = p;    
s->prior = p->prior;    
p->prior->next = s; 
p->prior = s;

關(guān)鍵在于交換的過程中不要出現(xiàn)矛盾，例如第四步先被執(zhí)行了，那么p->prior就會(huì)提前變成s，使得插入的工作出錯(cuò)。

三、雙向鏈表的刪除操作

刪除操作.png

代碼實(shí)現(xiàn)：

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

雙向鏈表可以有效提高算法的時(shí)間性能，說白了就是用空間來換取時(shí)間。

四、雙向鏈表的實(shí)踐

要求實(shí)現(xiàn)用戶輸入一個(gè)數(shù)使得26個(gè)字母的排列發(fā)生變化，例如用戶輸入3，輸出結(jié)果：
DEFGHIJKLMNOPQRSTUVWXYZABC
同時(shí)需要支持負(fù)數(shù)，例如用戶輸入-3，輸出結(jié)果：
XYZABCDEFGHIJKLMNOPQRSTUVW

代碼實(shí)現(xiàn)：

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

#define OK 1
#define ERROR 0

typedef char ElemType;
typedef int Status;
typedef struct DualNode{
    ElemType data;
    struct DualNode *prior;
    struct DualNode *next;
}DualNode,*DuLinkList;

Status 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 = (DualNode *)malloc(sizeof(DualNode));
        if(!q){
            return ERROR;
        }

        q->data = 'A'+i;
        q->prior = p;
        q->next = p->next;
        
        p = q;

    }

    p->next = (*L)->next;
    (*L)->next->prior = p;

    return OK;
}

void Caesar(DuLinkList *L,int i){
    if(i>0){
        do{
            (*L) = (*L)->next;
        }while(--i);
    }

    if(i<0){
        do{
            (*L) = (*L)->next;
        }while(++i);
    }
}

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

    InitList(&L);

    printf("請(qǐng)輸入一個(gè)整數(shù)：");
    scanf("%d",&n);
    printf("\n");
    Caesar(&L,n);
    
    for(i=0;i<26;i++){
        L = L->next;
        printf("%c",L->data);
    }
    printf("\n");
    return 0;
}