美文网首页
# 数据结构之循环链表（四）

# 数据结构之循环链表（四）

作者: 大橘猪猪侠 | 来源:发表于2020-04-04 19:18 被阅读0次

在上一篇博客中，我讲了有关于单循环链表的一些基本操作。
在这篇博客中，我来讲述一下双向链表和双向循环链表。

截屏2020-04-04下午7.04.36.png

循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。

一、双向链表
定义：双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

图为一个带头节点的双向链表和一个不带头节点的双向链表

截屏2020-04-04下午6.27.55.png 截屏2020-04-04下午6.28.03.png

接下来我们来对双向链表做一些基本的操作
1、创建
在创建链表之间，先进行一些设置，这个设置凭个人习惯的不同可以自己自定义。

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

//存储分配空间初始分量
#define MAXSIZE 20
//定义的一个值
typedef int Elemtype;
//状态码，返回函数状态
typedef int Status;
typedef struct Node{
    Elemtype data;
    struct Node *prior;
    struct Node *next;
}Node;

typedef struct Node *Linklist;

创建链表
//1、创建双向链表

    //创建头节点
    *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<MAXSIZE; i++) {
        //创建一个新节点
        Linklist temp = (Linklist)malloc(sizeof(Node));
        temp -> prior = NULL;
        temp -> next = NULL;
        temp -> data = i;
        //为新节点增加建立双向链表关系
        //temp的后继是p
        p->next = temp;
        //temp的前驱是p
        temp->prior = p;
        //p要记录最后节点的位置，方便下一次插入。
        p = p->next;
    }
    return OK;
}

2、遍历

void showLinklist(Linklist L){
    //忽略头节点，从头节点的下一节点开始遍历
    Linklist temp = L->next;
    if(temp == NULL){
        printf("链表为空\n");
        return;
    }
    //遍历链表
    while (temp) {
        printf("%d  ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}

3、插入

通过下面这张图，可以很好的理解插入的原理。


截屏2020-04-04下午6.51.05.png 
Status InsertLinklist(Linklist *L,int place,Elemtype e){
    //判断插入的位置合不合法
    if(place<1) return ERROR;
    //新建节点
    Linklist temp = (Linklist)malloc(sizeof(Node));
    //判断是否创建成功
    if(temp == NULL)    return ERROR;
    temp->prior = NULL;
    temp->next = NULL;
    //设置插入的值
    temp ->data = e;
    
    //将temp指向L
    Linklist p = *L;
    //找到插入位置的前一个节点
    for (int i = 1; i<place; i++) {
        p = p->next;
    }
    //判断插入的位置是否超过链表数量
    if(p == NULL)   return ERROR;
    //判断插入的位置是不是链表尾部
    if(p->next == NULL){
        p->next = temp;
    }else{
        //1、先将p的next的前驱指向temp
        p->next->prior = temp;
        //2、再将temp的next指向原来的p的next
        temp->next = p ->next;
        //3、p的next 指向新节点
        p->next = temp;
        //4、让temp的前驱指向p
        temp->prior = p;
    }
    return OK;
}

4、删除

通过一张图，来理解双向链表的删除


截屏2020-04-04下午6.57.14.png 
//4、删除双向链表指定位置上的元素
Status deleteLinklistPlace(Linklist *L,int place,Elemtype *e){
    //判断链表是否为空
    if(*L == NULL) return ERROR;
    int i=1;
    Linklist p = *L;
    //将指针p移动道删除元素的位置前一个
    while (i<place&&p!=NULL) {
        p = p->next;
        i++;
    }
    //判断删除的位置是否大于i或者p是否为空
    if(place>i||p==NULL)    return ERROR;
    
    //创建临时指针delTemp 指向要删除的结点,并将要删除的结点的data 赋值给*e,带回到main函数
    Linklist temp = p -> next;
    *e = temp->data;
    
    //p->next 等于要删除的结点的下一个结点
    p->next = temp->next;
    //如果删除结点的下一个结点不为空,则将将要删除的下一个结点的前驱指针赋值p;
    if(temp ->next !=NULL){
        temp->next->prior = p;
    }
    printf("删除的节点位置:%d,值为:%d\n",place,*e);
    free(temp);
    return OK;
}

5、删除指定元素

//5、删除双向链表指定的元素
Status deleteLinklist(Linklist *L,int data){
    Linklist p = *L;
    //遍历双向循环链表
    while (p) {
        //判断是否等于data
        if(p->data == data){
            p->prior->next = p->next;
            //判断删除的是否为最后一个节点
            if(p->next != NULL){
                p->next->prior = p->prior;
            }
            //释放节点
            free(p);
            break;
        }
        p = p->next;
    }
    
    return OK;
}

6、查询

1、在双向链表指定位置上查找元素

//6、在双向链表指定位置上查找元素
int selectLinklistPlace(Linklist *L,int place){
    //判断链表是否为空
    if(*L == NULL)  return -1;
    int i = 1;
    Linklist p = (*L)->next;
    int e;
    //查找查询的位置
    while (i<place && p != NULL) {
        p = p->next;
        i++;
    }
    if(place>i || p == NULL)    return -1;
    
    e = p->data;
    return e;
}

2、在双向链表查找元素

//7、在双向链表查找元素
int selectLinklist(Linklist L,Elemtype e){
    Linklist p = L->next;
    int i = 1;
    while (p) {
        if(p->data == e){
            return i;
        }
        i++;
        p = p->next;
    }
    return -1;
}

7、更改

//8、更新位置
Status replaceLinklist(Linklist *L,int place,Elemtype e){
    Linklist p = (*L)->next;
    int i = 1;
    //查找需要更新的位置
    while (i<place && p !=NULL) {
        p = p->next;
        i++;
    }
    if(p == NULL) return ERROR;
    p->data = e;
    return OK;
}

8、 main函数调用

isStatus = CreateLinklsit(&L);
    printf("isStatus = %d\n",isStatus);
    printf("创建成功,打印链表:\n");
    showLinklist(L);
    
    printf("请输入插入的位置\n");
    scanf("%d %d",&temp,&item);
    isStatus = InsertLinklist(&L, temp, item);
    printf("插入数据,打印链表:\n");
    showLinklist(L);
    
    printf("请输入删除的位置\n");
    scanf("%d",&temp);
    isStatus = deleteLinklistPlace(&L, temp, &item);
    printf("删除元素: 删除位置为%d,data = %d\n",temp,e);
    printf("删除操作之后的,双向链表:\n");
    showLinklist(L);
    
    printf("请输入要删除的内容\n");
    scanf("%d",&temp);
    isStatus = deleteLinklist(&L, temp);
    printf("删除操作之后的,双向链表:\n");
    showLinklist(L);
    
    printf("请输入你要查找位置的内容\n");
    scanf("%d",&temp);
    Elemtype x = selectLinklistPlace(&L, temp);
    printf("查找的元素位置:%d,值为:%d\n",temp,x);
    
    printf("请输入你要查找的内容\n");
    scanf("%d",&temp);
    Elemtype index= selectLinklist(L, temp);
    printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",temp,index);
    
    printf("请输入你要更新的结点以及内容\n");
    scanf("%d %d",&temp,&item);
    isStatus = replaceLinklist(&L, temp, item);
    printf("更新结点数据后的双向链表:\n");
    showLinklist(L);

9、打印结果

截屏2020-04-04下午6.46.32.png

二、双向循环链表
双向链表和双线循环链表很相似，只是双向链表最后一个节点的next指向为空，而双向循环链表最后一个节点的指向为头节点。
因此，双向循环链表，这里就不在过多的描述，直接上代码。

先对双向循环链表进行一些基本操作的描述
1、创建

Status CreateLinklsit(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.为新增的结点建立双向链表关系
        //1、 temp 是p的后继
        p->next = temp;
        //2、 temp 的前驱是p
        temp->prior = p;
        //3、 temp的后继是*L
        temp->next = (*L);
        //4、 将temp的后继的前驱指向temp
        temp->next->prior = temp;
        //5、 p 要记录最后的结点的位置,方便下一次插入
        p = p->next;
    }
    return OK;
}

2、插入

//双向循环链表插入元素
/*当插入位置超过链表长度则插入到链表末尾*/
Status InsertLinklist(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;
}

3、删除

// 双向循环链表删除结点
Status LinkListDeleteplace(LinkList *L,int place,ElemType *e){
    
    int i = 1;
    LinkList temp = (*L)->next;
    
    if (*L == NULL || i>place) {
        return  ERROR;
    }
    //如果删除到只剩下首元结点了,则直接将*L置空;
    if(temp->next == *L){
        free(*L);
        (*L) = NULL;
        return OK;
    }
    
    //1.找到要删除的结点
    while (i < place) {
        temp = temp->next;
        i++;
    }
    //2.给e赋值要删除结点的数据域
    *e = temp->data;
    
    //3.修改被删除结点的前驱结点的后继指针
    temp->prior->next = temp->next;
    //4.修改被删除结点的后继结点的前驱指针
    temp->next->prior = temp->prior;
    //5. 删除结点temp
    free(temp);
    return OK;
}
//删除指定的元素
Status LinkListdelete(LinkList *L,int data){
    LinkList p = (*L)->next;
    while (p != *L) {
        if(p->data == data){
            p -> prior->next = p->next;
            if(p->next != *L){
                p->next->prior = p->prior;
            }
            free(p);
            break;
        }
        p = p->next;
    }
    return OK;
}

4、遍历

// 遍历双向循环链表
Status showLinklist(LinkList L){
    
    if (L == NULL) {
        printf("打印的双向循环链表为空!\n");
        return ERROR;
    }
    printf("双向循环链表内容: \n");
    
    LinkList p = L->next;
    while (p != L) {

        printf("%d  ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

5、查找

//6、在双向链表指定位置上查找元素
int selectLinklistPlace(LinkList *L,int place){
    if(*L == NULL)  return -1;
    int i = 1;
    LinkList p = (*L)->next;
    int e;
    while (i<place && p != *L) {
        p = p->next;
        i++;
    }
    if(place>i || p == *L)    return -1;
    e = p->data;
    return e;
}
//7、在双向循环链表查找元素
int selectLinklist(LinkList *L,ElemType e){
    LinkList p = (*L)->next;
    int i = 1;
    while (p != *L) {
        if(p->data == e){
            return i;
        }
        i++;
        p = p->next;
    }
    return -1;
}

6、更新

//8、更新位置
Status replaceLinklist(LinkList *L,int place,ElemType e){
    LinkList p = (*L)->next;
    int i = 1;
    while (i<place && p->next != (*L)) {
        p = p->next;
        i++;
    }
    if(p->next == (*L)||i>place)  return ERROR;
    p->data = e;
    return OK;
}

7、main函数方法的调用

 isStatus = CreateLinklsit(&L);
     printf("isStatus = %d\n",isStatus);
     printf("创建成功,打印链表:\n");
     showLinklist(L);
     
     printf("请输入插入的位置\n");
     scanf("%d %d",&temp,&item);
     isStatus = InsertLinklist(&L, temp, item);
     printf("插入数据,打印链表:\n");
     showLinklist(L);
     
     printf("请输入删除的位置\n");
     scanf("%d",&temp);
     isStatus = LinkListDeleteplace(&L, temp, &item);
     printf("删除元素: 删除位置为%d,data = %d\n",temp,item);
     printf("删除操作之后的,双向链表:\n");
     showLinklist(L);
     
     printf("请输入要删除的内容\n");
     scanf("%d",&temp);
     isStatus = LinkListdelete(&L, temp);
     printf("删除操作之后的,双向链表:\n");
     printf("删除元素:data = %d\n",temp);
     showLinklist(L);
     
     printf("请输入你要查找位置的内容\n");
     scanf("%d",&temp);
     ElemType x = selectLinklistPlace(&L, temp);
    if(x>0){
        printf("查找的元素位置:%d,值为:%d\n",temp,x);
    }else{
        printf("位置超出链表数量\n");
    }
     
     
     printf("请输入你要查找的内容\n");
     scanf("%d",&temp);
     ElemType index= selectLinklist(&L, temp);
    if(index>0){
        printf("在双向链表中查找到数据域为%d的结点,位置是:%d\n",temp,index);
    }else{
        printf("没有查到\n");
    }
     
     printf("请输入你要更新的结点以及内容\n");
     scanf("%d %d",&temp,&item);
     isStatus = replaceLinklist(&L, temp, item);
     printf("更新结点数据后的双向链表:\n");
     showLinklist(L);

8、运行结果


截屏2020-04-04下午7.12.12.png

感谢观看，如果一些地方存在问题或者代码错误，请留言提醒我。
另外，今天是一个特殊的清明节，让我们永远铭记哪些永远冲在一线奋斗勇士们，感谢他们为社会作出重大贡献。

相关文章

  • iOS 数据结构之链表

    iOS 数据结构之链表 iOS 数据结构之链表

  • 常见的数据结构

    常见的数据结构有： 数组 链表单链表、双向链表、循环链表、双向循环链表、静态链表 栈顺序栈、链式栈 队列普通队列、...

  • # 数据结构之循环链表（四）

    在上一篇博客中，我讲了有关于单循环链表的一些基本操作。在这篇博客中，我来讲述一下双向链表和双向循环链表。 循环链表...

  • 线性表-单向循环链表

    单向循环链表 单向循环链表示意图如下： 数据结构定义（同普通链表） 单向循环链表初始化与赋值 在上面循环遍历查找尾...

  • 数据结构笔记

    数据结构课程概览 ================== 1.顺序表 2.链表：单链表，单向循环链表，双链表...

  • 集合-LinkedList解析

    一、概要 Java中底层数据结构是链表、双端链表，Android中数据结构是双向循环链表 非线程安全数据结构,允许...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据结构与算法相关

    第二章 数据结构与算法相关 1.常用的数据结构有哪些？ 数组、栈、队列、链表（单链表、双向链表、循环链表）、树、散...

  • 数据结构 | 其二 链表

    冰河winner - 数据结构之链表 2.1 单向链表 数据结构(一) 单链表的实现-JAVA 2.2 双端链表 ...

  • Java 数据结构 循环链表

    Java 数据结构 循环链表 简介 循环链表与前两篇文章所提及的单向链表及双向链表也并没有太多不同的地方，只是其尾...

网友评论

      本文标题：# 数据结构之循环链表（四）

      本文链接：https://www.haomeiwen.com/subject/xzfsphtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|# 数据结构之循环链表（四）|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！