线性表 — 链表存储

链表存储

链表存储特点：不连续的，数据与数据的关系通过指针域连接。
链表存储方式：单链表、循环链表、双向链表、双向循环链表。

• 结点：
  链表是由一个个结点组成，结点包括数据域和指针域两部分，数据域是存储数据的地方，指针域是存储指针的地方。
  

一、单链表

• 单链表逻辑状态：
  有一个指针L指向链表，链表的第一个结点叫做首元结点，最后一个结点的指针域为空。并且单链表的特点只能从前往后查找，从后往前是无法查找到的。下面是单链表的两种操作方案：
  没有头结点的单链表

增加头结点的单链表

链表头部增加头结点的好处：
1. 便于首元结点处理
2. 便于空表和非空表的处理统一

---

• 准备

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */

• 定义结点

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList; // 每次创建结构体很麻烦，所以重定义

• 初始化

// 初始化并增加头结点
Status InitList(LinkList *L){
    // 产生头结点，并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node)); // 头结点
    // 存储空间分配失败
    if(*L == NULL) return ERROR;
    // 将头结点的指针域置空
    (*L)->next = NULL;
    
    return OK;
}

• 遍历单链表

/* 
初始条件：顺序线性表L已存在
操作结果：依次对L的每个数据元素输出
*/
Status ListTraverse(LinkList L)
{
    LinkList p=L->next;
    while(p)
    {
        printf("%d, ", p->data);
        p=p->next;
    }
    printf("\n");
    return OK;
}

• 单链表插入

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1
 */
Status ListInsert(LinkList *L,int i,ElemType e){
 
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    
    // 寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    // 第i个元素不存在
    if(!p || j>i) return ERROR;
    
    // 生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    // 将e赋值给s的数值域
    s->data = e;
    // 将p的后继结点赋值给s的后继
    s->next = p->next;
    // 将s赋值给p的后继
    p->next = s;
    
    return OK;
}

• 取值

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
    
    // j: 计数.
    int j;
    // 声明结点p;
    LinkList p;
    
    // 将结点p 指向链表L的第一个结点;
    p = L->next;
    // j计算=1;
    j = 1;
    
    // p不为空，且计算j不等于i，则循环继续
    while (p && j<i) {
        //p指向下一个结点
        p = p->next;
        ++j;
    }
    
    // 如果p为空或者j>i，则返回error
    if(!p || j > i) return ERROR;
    
    // e = p所指的结点的data
    *e = p->data;

    return OK;
}

• 删除元素

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */
Status ListDelete(LinkList *L,int i,ElemType *e){
    
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    
    //查找第i-1个结点,p指向该结点
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    
    return OK;
}

• 清空单链表

/* 
初始条件：顺序线性表L已存在
操作结果：将L重置为空表
*/
Status ClearList(LinkList *L)
{
    LinkList p, q;

    // p指向第一个结点
    p=(*L)->next;           

    while(p) // 没到表尾，一直循环
    {
        q=p->next;
        free(p);
        p=q;
    }

    // 头结点指针域为空
    (*L)->next=NULL;

    return OK;
}

• 单链表前插法

/* 
随机产生n个元素值，建立带表头结点的单链线性表L(前插法)
*/
void CreateListHead(LinkList *L, int n){
    
    LinkList p;
    
    // 建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    // 循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        // 生成新结点
        p = (LinkList)malloc(sizeof(Node));
       
        // i赋值给新结点的data
        p->data = i;
        // p->next = 头结点的L->next
        p->next = (*L)->next;
        
        // 将结点P插入到头结点之后;
        (*L)->next = p;
    }
}

• 单链表后插法

/* 
随机产生n个元素值,建立带表头结点的单链线性表L(后插法)
*/
void CreateListTail(LinkList *L, int n){
    
    LinkList p, r;
 
    // 建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    // r指向尾部的结点
    r = *L;
    
    for (int i=0; i<n; i++) {
        // 生成新结点
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        // 将表尾终端结点的指针指向新结点
        r->next = p;
        // 将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾指针的next = null
    r->next = NULL;
}

• 主函数

// L1与L2两种创建方式是等价的
int main(int argc, const char * argv[]) {
    
    Status iStatus;
    LinkList L1, L; 
    struct Node *L2;
    ElemType e;

    // 单链表初始化
    iStatus = InitList(&L);
    printf("L 是否初始化成功?(0:失败,1:成功) %d\n",iStatus);
    
    // 单链表插入数据
    for(int j = 1;j<=10;j++)
    {
        iStatus = ListInsert(&L, 1, j);
    }
    printf("L 插入后\n");
    ListTraverse(L);
    
    // 单链表获取元素
    GetElem(L,5,&e);
    printf("第5个元素的值为：%d\n",e);
    
    // 删除第5个元素
    iStatus = ListDelete(&L, 5, &e);
    printf("删除第5个元素值为:%d\n",e);
    ListTraverse(L);
    
    // 前插法整理创建链表L
    iStatus = ClearList(&L);
    CreateListHead(&L, 20);
    printf("整理创建L的元素(前插法):\n");
    ListTraverse(L);
    
    // 后插法整理创建链表L
    iStatus = ClearList(&L);
    CreateListTail(&L, 20);
    printf("整理创建L的元素(后插法):\n");
    ListTraverse(L);   
}

/*
L 是否初始化成功?(0:失败,1:成功) 1
L 插入后
10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 
第5个元素的值为：6
删除第5个元素值为:6
10, 9, 8, 7, 5, 4, 3, 2, 1, 
整理创建L的元素(前插法):
19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 
整理创建L的元素(后插法):
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 
*/

---

二、 单向循环链表

a) 什么是单向循环链表？
单向循环链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表，通俗讲就是把尾节点的指针指向头结点。
b) 为什么要使用单向循环链表？
在单链表中，头指针是相当重要的，因为单链表的操作都需要头指针，所以如果头指针丢失或者破坏，那么整个链表都会遗失，并且浪费链表内存空间，因此我们引入了单向循环链表这种数据结构。

单向循环链表

---

• 准备

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 // 存储空间初始分配量

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int ElemType; // ElemType类型根据实际情况而定，这里假设为int

• 定义结点

//定义结点
typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList; // 每次创建结构体很麻烦，所以重定义

• 创建单向循环链表

/*
 循环链表创建：
 2种情况: ①第一次开始创建，②已经创建，往里面新增数据
 判断是否第一次创建链表  
 YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
 NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
 */
Status CreateList(LinkList *L) { // 此处解释一下：想修改L就传*L，不需要修改直接传L即可
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    printf("输入节点的值，输入0结束\n");
    while(1)
    {
        scanf("%d",&item); // 输入
        if(item==0) break; // 输入0结束
          // 如果输入的链表是空。则创建一个新的节点，使其next指针指向自己  (*head)->next=*head;
        if (*L==NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if(!L)exit(0);
            (*L)->data=item;
            (*L)->next=*L;
        } else {
            /*
            输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
            */
            // 寻找链表的尾节点
            for (target = *L; target->next != *L; target = target->next); 
            temp=(LinkList)malloc(sizeof(Node));
            
            if(!temp) return ERROR;

            temp->data=item;
            temp->next=*L;  // 新节点的next指向头节点
            target->next=temp;// 尾节点的next指向新节点
        }
    }
    return OK;
}

// 第二种方法：记住尾结点方式创建单向循环链表
Status CreateList(LinkList *L) {
    int item;
    LinkList temp = NULL;
    LinkList target = NULL;
    LinkList last = NULL; // 记住尾结点
    printf("请输入新的结点, 当输入0时结束!\n");
    while (1) {
        scanf("%d",&item);
        if (item == 0) {
            break;
        }
        //第一次创建
        if (*L == NULL) {
            *L = (LinkList)malloc(sizeof(Node));
            if(!*L) return ERROR;
            (*L)->data = item;
            (*L)->next = *L;
            last = *L;
        } else {            
            temp = (LinkList)malloc(sizeof(Node));
            if(!temp) return  ERROR;
            temp->data = item;
            temp->next = *L;
            last->next = temp;
            last = temp; // 每次添加后更新尾结点
        }   
    }
    return OK;
}

看如下打印，可明显看出单向链表循环指向：3.next ->6 6.next -> 9 9.next -> 3。

• 遍历单向循环链表

/*
遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值
*/ 
void show(LinkList p)
{
    //如果链表是空
    if (p == NULL) {
        printf("打印的链表为空!\n");
        return;
    } else {
        LinkList temp;
        temp = p;
        do {
            printf("%5d",temp->data);
            temp = temp->next;
        } while (temp != p);
        printf("\n");
    }
}

• 单向循环链表插入数据

Status ListInsert(LinkList *L, int place, int num){
    LinkList temp ,target;
    int i;
    if (place == 1) {
        /* 
        如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
        1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        2. 找到链表最后的结点_尾结点,
        3. 让新结点的next 执行头结点.
        4. 尾结点的next 指向新的头结点;
        5. 让头指针指向temp(临时的新结点)
        */
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        
        for (target = *L; target->next != *L; target = target->next);
        
        temp->next = *L;
        target->next = temp;
        *L = temp;
    } else {
        /* 
        如果插入的位置在其他位置;
        1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
        2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
        3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
        4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
        */
        temp = (LinkList)malloc(sizeof(Node));
        if (temp == NULL) {
            return ERROR;
        }
        temp->data = num;
        
        for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
        
        temp->next = target->next;
        target->next = temp;
    }
    
    return OK;
}

• 单向循环链表删除元素

Status  LinkListDelete(LinkList *L,int place) {
    LinkList temp,target;
    int i;
    // temp 指向链表首元结点
    temp = *L;
    if(temp == NULL) return ERROR;
    
    if (place == 1) { 
        //①.如果删除到只剩下首元结点了,则直接将*L置空;
        if((*L)->next == (*L)){
            (*L) = NULL;
            return OK;
        }

        /*
        ②.链表还有很多数据,但是删除的是首结点;
        1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
        2. 新结点做为头结点,则释放原来的头结点
        */
        for (target = *L; target->next != *L; target = target->next);
        temp = *L;
        
        *L = (*L)->next;
        target->next = *L;
        free(temp);
    } else {
        /*
        如果删除其他结点--其他结点
        1. 找到删除结点前一个结点target
        2. 使得target->next 指向下一个结点
        3. 释放需要删除的结点temp
        */
        for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
            temp = target->next;
            target->next = temp->next;
            free(temp);
        }
    return OK;
}

• 单向循环链表查询值

int findValue(LinkList L,int value) {
    int i = 1;
    LinkList p;
    p = L;
    
    //寻找链表中的结点 data == value
    while (p->data != value && p->next != L) {
        i++;
        p = p->next;
    }
    
    //当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
    if (p->next == L && p->data != value) {
        return  -1;
    }
    return i;
}

• 删除链表，释放内存

void FreeList(LinkList *L)
{
    LinkList pt = NULL;
 
    while (*L != NULL)
    {
        // 如果只有头节点
        if (*L == (*L)->next) {
            free(*L);
            *L = NULL;
        } else { // 如果不止头节点
            pt = (*L)->next->next;
            free((*L)->next);
            (*L)->next = pt;
        }
    }
}

• 主函数

int main(int argc, const char * argv[]) {    
    LinkList head;
    int place,num;
    int iStatus;
    
    iStatus = CreateList(&head);
    printf("原始的链表：\n");
    show(head);
    
    printf("输入要插入的位置和数据用空格隔开：");
    scanf("%d %d",&place,&num);
    iStatus = ListInsert(&head,place,num);
    show(head);

    printf("输入要删除的位置：");
    scanf("%d",&place);
    LinkListDelete(&head,place);
    show(head);
        
    printf("输入你想查找的值:");
    scanf("%d",&num);
    place=findValue(head,num);
    if(place!=-1)
        printf("找到的值的位置是place = %d\n",place);
    else
        printf("没找到值\n");    

    FreeList(&head);

    return 0;
}

---

三、双向链表

双向链表的每个结点需要连接前一个结点和后一个结点，所以需要定义两个指针域，分别指向前一个结点（前驱）和后一个结点（后继）。

结点结构

---

• 准备

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 // 存储空间初始分配量

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int ElemType; // ElemType类型根据实际情况而定，这里假设为int

• 定义结点

typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

• 创建双向链接

Status createLinkList(LinkList *L) {
    //*L 指向头结点
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) return ERROR;
    
    (*L)->prior = NULL;
    (*L)->next = NULL;
    (*L)->data = -1;
    
    // 新增数据
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->prior = NULL;
        temp->next = NULL;
        temp->data = i;
        
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;
    }
    return OK;
}

• 打印循环链表的元素

void display(LinkList L){
    LinkList temp = L->next;
    
    if(temp == NULL){
        printf("打印的双向链表为空!\n");
        return;
    }
    
    while (temp) {
        printf("%d  ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

• 双向链表插入元素

双向链表插入元素

Status ListInsert(LinkList *L, int i, ElemType data){
    //1. 插入的位置不合法 为0或者为负数
    if(i < 1) return ERROR;
    
    //2. 新建结点
    LinkList temp = (LinkList)malloc(sizeof(Node));
    temp->data = data;
    temp->prior = NULL;
    temp->next = NULL;
    
    //3.将p指向头结点!
    LinkList p = *L;
    
    //4. 找到插入位置i直接的结点
    for(int j = 1; j < i && p;j++)
        p = p->next;
    
    //5. 如果插入的位置超过链表本身的长度
    if(p == NULL){
        return  ERROR;
    }
    
    //6. 判断插入位置是否为链表尾部;
    if (p->next == NULL) {
        p->next = temp;
        temp->prior = p;
    } else {
        //1️⃣ 将p->next 结点的前驱prior = temp
        p->next->prior = temp;
        //2️⃣ 将temp->next 指向原来的p->next
        temp->next = p->next;
        //3️⃣ p->next 更新成新创建的temp
        p->next = temp;
        //4️⃣ 新创建的temp前驱 = p
        temp->prior = p;
    }
    return  OK;
}

• 删除双向链表指定位置上的结点

Status ListDelete(LinkList *L, int i, ElemType *e){
    
    int k = 1;
    LinkList p = (*L);
    
    //1.判断双向链表是否为空,如果为空则返回ERROR;
    if (*L == NULL) {
        return ERROR;
    }

    //2. 将指针p移动到删除元素位置前一个
    while (k < i && p != NULL) {
        p = p->next;
        k++;
    }
    
    //3.如果k>i 或者 p == NULL 则返回ERROR
    if (k>i || p == NULL) {
        return  ERROR;
    }
    
    //4.创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
    LinkList delTemp = p->next;
    *e = delTemp->data;
    
    //5. p->next 等于要删除的结点的下一个结点
    p->next = delTemp->next;
    
    //6. 如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
    if (delTemp->next != NULL) {
        delTemp->next->prior = p;
    }
    
    //7.删除delTemp结点
    free(delTemp);
    
    return OK;
}

• 删除双向链表指定的元素

Status LinkListDeletVAL(LinkList *L, int data){
    
    LinkList p = *L;
    
    //1.遍历双向循环链表
    while (p) {
        //2.判断当前结点的数据域和data是否相等,若相等则删除该结点
        if (p->data == data) {
            //修改被删除结点的前驱结点的后继指针,参考图上步骤1️⃣
            p->prior->next = p->next;
            //修改被删除结点的后继结点的前驱指针,参考图上步骤2️⃣
            if(p->next != NULL){
                p->next->prior = p->prior;
            }
            //释放被删除结点p
            free(p);
            // 退出循环
            break;
        }
        //没有找到该结点,则继续移动指针p
        p = p->next;
    }
    return OK;
}

• 在双向链表中查找元素

int selectElem(LinkList L,ElemType elem){
    LinkList p = L->next;
    int i = 1;
    while (p) {
        if (p->data == elem) {
            return i;
        }        
        i++;
        p = p->next;
    }    
    return  -1;
}

• 在双向链表中更新结点

Status replaceLinkList(LinkList *L,int index,ElemType newElem) {
    LinkList p = (*L)->next;
    
    for (int i = 1; i < index; i++) {
        p = p->next;
    }
    
    p->data = newElem;
    return OK;
}

• main函数

int main(int argc, const char * argv[]) {
    Status iStatus = 0;
    LinkList L;
    int temp,item,e;
    
    iStatus =  createLinkList(&L);
    printf("iStatus = %d\n",iStatus);
    printf("链表创建成功,打印链表:\n");
    display(L);
    
    printf("请输入插入的位置\n");
    scanf("%d %d",&temp,&item);
    iStatus = ListInsert(&L, temp, item);
    printf("插入数据,打印链表:\n");
    display(L);
    
    printf("请输入删除的位置\n");
    scanf("%d",&temp);
    iStatus = ListDelete(&L, temp, &e);
    printf("删除元素: 删除位置为%d,data = %d\n",temp,e);
    printf("删除操作之后的,双向链表:\n");
    display(L);

    printf("请输入你要查找的内容\n");
     scanf("%d",&temp);
    ElemType index = selectElem(L, temp);
    printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",temp,index);

    printf("请输入你要更新的结点以及内容\n");
    scanf("%d %d",&temp,&item);
    iStatus = replaceLinkList(&L, temp, item);
    printf("更新结点数据后的双向链表:\n");
    display(L);

    return 0;
}

iStatus = 1
链表创建成功,打印链表:
0 1 2 3 4 5 6 7 8 9
请输入插入的位置

5
11
插入数据,打印链表:
0 1 2 3 11 4 5 6 7 8 9
请输入删除的位置
6
删除元素: 删除位置为6,data = 4
删除操作之后的,双向链表:
0 1 2 3 11 5 6 7 8 9
请输入你要查找的内容
6
在双向链表中查找到数据域为6的结点,位置是:7
请输入你要更新的结点以及内容
5
4
更新结点数据后的双向链表:
0 1 2 3 4 5 6 7 8 9

---

四、双向循环链表

双向循环链表和双向链表的最大的不同在于：
双向链表头结点的前驱是null，尾结点的next是null。
双向循环链表头结点的前驱prior指向最后一个结点，尾结点的next指向头结点。

• 准备

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

#define MAXSIZE 20 // 存储空间初始分配量

typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int ElemType; // ElemType类型根据实际情况而定，这里假设为int

• 定义结点

typedef struct Node{
    ElemType data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

• 双向循环链表初始化

Status creatLinkList(LinkList *L){
    
    *L = (LinkList)malloc(sizeof(Node));
    if (*L == NULL) {
        return ERROR;
    }
    
    (*L)->next = (*L);
    (*L)->prior = (*L);
    
    //新增数据
    LinkList p = *L;
    for(int i=0; i < 10;i++){
        
        //1.创建1个临时的结点
        LinkList temp = (LinkList)malloc(sizeof(Node));
        temp->data = i;
        
        //2.为新增的结点建立双向链表关系
        //① temp 是p的后继
        p->next = temp;
        //② temp 的前驱是p
        temp->prior = p;
        //③ temp的后继是*L
        temp->next = (*L);
        //④ p 的前驱是新建的temp
        p->prior = temp;
        //⑤ p 要记录最后的结点的位置,方便下一次插入
        p = p->next;   
    }
    return OK;
}

• 双向循环链表插入元素

/*当插入位置超过链表长度则插入到链表末尾*/
Status LinkListInsert(LinkList *L, int index, ElemType e){
   
    //1. 创建指针p,指向双向链表头
    LinkList p = (*L);
    int i = 1;
    
    //2.双向循环链表为空,则返回error
    if(*L == NULL) return ERROR;
   
    //3.找到插入前一个位置上的结点p
    while (i < index && p->next != *L) {
        p = p->next;
        i++;
    }
    
    //4.如果i>index 则返回error
    if (i > index)  return ERROR;
    
    //5.创建新结点temp
    LinkList temp = (LinkList)malloc(sizeof(Node));
    
    //6.temp 结点为空,则返回error
    if (temp == NULL) return ERROR;
    
    //7.将生成的新结点temp数据域赋值e.
    temp->data = e;
    
    //8.将结点temp 的前驱结点为p;
    temp->prior = p;
    //9.temp的后继结点指向p->next;
    temp->next = p->next;
    //10.p的后继结点为新结点temp;
    p->next = temp;
    
    //如果temp 结点不是最后一个结点
    if (*L != temp->next) {
        
        //11.temp节点的下一个结点的前驱为temp 结点
        temp->next->prior = temp;
    } else {
        (*L)->prior = temp;   
    }
    return OK;
}

• 遍历双向循环链表

Status Display(LinkList L){
    
    if (L == NULL) {
        printf("打印的双向循环链表为空!\n\n");
        return ERROR;
    }
    printf("双向循环链表内容:  ");
    
    LinkList p = L->next;
    while (p != L) {
        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n\n");
    return OK;
}

• 双向循环链表删除结点

Status LinkListDelete(LinkList *L,int index,ElemType *e){
    
    int i = 1;
    LinkList temp = (*L)->next;
    
    if (*L == NULL) {
        return  ERROR;
    }
    
    //①.如果删除到只剩下首元结点了,则直接将*L置空;
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    
    //1.找到要删除的结点
    while (i < index) {
        temp = temp->next;
        i++;
    }

    //2.给e赋值要删除结点的数据域
    *e = temp->data;
    
    //3.修改被删除结点的前驱结点的后继指针 图1️⃣
    temp->prior->next = temp->next;
    //4.修改被删除结点的后继结点的前驱指针 图2️⃣
    temp->next->prior = temp->prior;
    //5. 删除结点temp
    free(temp);
    
    return OK;
}

• main函数

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    
    LinkList L;
    Status iStatus;
    ElemType temp,item;
    
    iStatus = creatLinkList(&L);
    printf("双向循环链表初始化是否成功(1->YES)/ (0->NO):  %d\n\n",iStatus);
    Display(L);
    
    printf("输入要插入的位置和数据用空格隔开：");
    scanf("%d %d",&temp,&item);
    iStatus = LinkListInsert(&L,temp,item);
    Display(L);

    printf("输入要删除位置：");
    scanf("%d",&temp);
    iStatus = LinkListDelete(&L, temp, &item);
    printf("删除链表位置为%d,结点数据域为:%d\n",temp,item);
    Display(L);

    return 0;
}

打印：
双向循环链表初始化是否成功(1->YES)/ (0->NO): 1
双向循环链表内容: 0 1 2 3 4 5 6 7 8 9
输入要插入的位置和数据用空格隔开：5 11
双向循环链表内容: 0 1 2 3 11 4 5 6 7 8 9
输入要删除位置：5
删除链表位置为5,结点数据域为:11
双向循环链表内容: 0 1 2 3 4 5 6 7 8 9