双向链表

一、双向链表结构

双向链表结点结构

typedef struct DualNode
{
    ElemType data;
    struct DualNode *prior;  //前驱结点
    struct DualNode *next;   //后继结点
} DualNode, *DuLinkList;

双向链表结点结构.png

既然单链表可以有循环链表，那么双向链表当然也可以有。

非空的双循环链表.png

由于这是双向链表，那么对于链表中的某一个结点p，它的后继结点的前驱结点是它本身。

二、双向链表的插入操作

插入操作.jpg

代码实现：

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

关键在于交换的过程中不要出现矛盾，例如第四步先被执行了，那么p->prior就会提前变成s，使得插入的工作出错。

三、双向链表的删除操作

删除操作.png

代码实现：

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

双向链表可以有效提高算法的时间性能，说白了就是用空间来换取时间。

四、双向链表的实践

要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，输出结果：
DEFGHIJKLMNOPQRSTUVWXYZABC
同时需要支持负数，例如用户输入-3，输出结果：
XYZABCDEFGHIJKLMNOPQRSTUVW

代码实现：

#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("请输入一个整数：");
    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;
}