精华内容
下载资源
问答
  • 双向循环链表
    千次阅读
    2022-01-21 12:22:35

    目录

    一、链表的概念

    1. 链表的概念

    2. 链表相邻结点不连续

    二、双向循环链表的相关函数

    1. 创建链表结点(增)

    (1)创建结点

    (2)尾插结点

    2. 删除链表结点(删)

    3. 查找链表结点(查)

    4. 修改链表结点(改)

    三、归纳总结

    四、源码链接


    一、链表的概念

    1. 链表的概念

    链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

    链表示意图
    双向循环链表示意图

    2. 链表相邻结点不连续

    由图可知,00A99740+12=00A9974C!=00A99788,即物理存储结构上相邻结点不连续

    	ListPushBack(Head, 1);//尾插法生成结点
    	ListPushBack(Head, 2);
    	ListPrint(Head);      //打印链表
    	ListFind(Head,1);     //查找结点
    	ListFind(Head,2);
    	printf("一个结点的内存大小为:%d\n",sizeof(ListNode));

    链表相邻结点地址不连续

    二、双向循环链表的相关函数

    1. 创建链表结点(增)

    (1)创建结点

    a. 在堆上申请空间

    	ListNode* Node = (ListNode*)malloc(sizeof(ListNode));
    	if (NULL == Node){//判断申请空间是否失败
    		assert(0);
    		return 0;
    	}

    b. 存储数据

    	Node->data= data;
    	Node->next = NULL;
    	Node->pre = NULL;

    c. 返回结点地址

    	return Node;

    (2)尾插结点

    假设结点newNode尾插在结点A后面

    a. newNode的next指针指向头结点Head

    newNode->next=Head ;

    b. newNode的prev指针指向结点Head的prev所指向的结点(即A)

    newNode->pre=Head->pre ;

    c. A的next(即Head->pre->next)指向结点neNode

    Head->pre->next = newNode;

    d. newHead的prev指向结点P

    Head->pre = newNode;
    尾插图解

    2. 删除链表结点(删)

    a. 创建temp指针,指向Head->next所指向的结点

    ListNode* temp = (*Head)->next;

    b. 通过循环删除temp所指向的结点

    	while (temp != *Head){
            //Head的next指向temp
    		(*Head)->next = temp->next;
    		free(temp);
    		temp = (*Head)->next;
    	}
            //删除temp所指向的结点后,temp再次指向Head->next所指向的结点

    c. 删除头结点

    	free(*Head);
    	*Head = NULL;

    3. 查找链表结点(查)

    a. 创建指针temp,指向头结点Head的下一个结点

    ListNode* temp = Head->next;

    b. 使用while循环寻找结点

    	while (temp!= Head){
    		temp = temp->next;
    	}

    c.创建flag变量判断是否找到结点

    若flag==0,则未找到结点;若flag==1,则未找到结点;

    		int flag = 0;
            //找到结点
            if (temp->data ==x){
    			printf("%d的地址为%p\n",x,temp);
    			flag = 1;
    			break;
    		}
            //未找到结点
            if (0 == flag){
    		    printf("%d不在链表中\n",x);
    	    }

    4. 修改链表结点(改)

    a. 找到结点

    ListNode* temp=ListFind(Head, x);

    b. 修改内容

    	LTDataType flag = 0;
    	printf("请输入你要修改的数字:");
    	scanf("%d",&flag);
    	temp->data = flag;

    三、归纳总结

    带头双向循环链表是链表中结构最复杂的,但使用代码实现以后会发现结构会带来很多优势,实现反而简单了。

    (1)链表在物理存储结构上不连续

    (2)链表尾插,请注意结点的链接顺序,避免断连。

    Head->prev先链接newNode,造成找不到结点A(即无法使用Head->prev找到结点A),出现A的next无法连接newNode的情况。

    结点指针断连
    结点指针断连

    四、源码链接

    小伙伴们,关于双向循环链表的源码就在这里了,请点击链接。欢迎关注,欢迎问答,我一定会尽力解答你们的疑惑的。
     

    更多相关内容
  • 本文实例讲述了Python双向循环链表实现方法。分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构。遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙。 我自己尝实现了一个...
  • 循环链表单向循环链表双向循环链表1. 双向循环链表——插入2. 双向循环链表——删除 单向循环链表 关于两个循环链表合并为一个循环链表 双向循环链表 在单链表L中,查找ai的后继Next(L,a;),耗时仅为O(1),因为...

    单向循环链表

    循环链表和单链表的区别

    1. 表中最后结点的指针不是NULL,而是改为指向头结点,从而整个链表形成了一个环。

    2. 循环单链表中没有指针域为NULL的结点,故判空条件为判断 *A (表尾节点) *A 的next是否为头指针

    3. 空表:if(A->next == H) { 空表 }

    在这里插入图片描述

    循环链表的特点

    • 循环单链表插入,删除算法于单链表几乎一样

    正是因为循环单链表是一个“环”在任何位置插入和删除操作都是等价的,无须判断是否是表全。循环链表可以从任意一个结点开始遍历整个链表循环链表不设头指针而仅设尾指针,若只设置尾指针A,A->next即为头指针,对表头,表尾进行操作都只要O(n).

    • 关于两个循环链表合并为一个循环链表
      在这里插入图片描述

    双向循环链表——概念

    在单链表L中,查找ai的后继Next(L,a;),耗时仅为O(1),因为取ai后继指针即可。
    但查找ai的直接前驱Prior(L,ai);则需从链表的头指针开始,找到结点ai前一结点即是。故运算Prior(L,ai)依赖表长n,耗时为O(n)。另外,若链表中有一指针值被破坏,则整个链表脱节。这是单链表的不足

    为此,引入双向链表。先定义双向链表中的结点:
    在这里插入图片描述
    其中,datanext同单链表,增加一指针域prior其指向本结点的直接前驱
    结点描述:

    typedef int data_t; 
    typedef struct dnode_t
    { 
            data_tdata;
            struct dnode_t *prior;
            struct dnode_t *next;
    }dlinknode_t , *dlinklist_t;
    
    • 表L=(a0·····an-1)(设n=2) 的双向循环链表如图:
      -
      设p为链表中某结点的指针,有对称性:
      (p->prior)->next = p =(p->next)->prior
    
    • 双向链表的查找等运算基本上和单链表类似。
    • 在双向循环链表中,某结点 *p 为尾结点时,p->next == H,当循环双链表尾空表时,某头结点的prior域next域都等于H

    下面我们学习一下双向循环链表的插入和删除运算

    1. 双向循环链表——插入

    插入: 即实现在链表L的第i结点前插入一结点x的运算,如图
    在这里插入图片描述

    ① q->prior = p->prior;(p->prior)->next = q;
    ③ q->next = p;
    ④ p->prior=q;
    
    • 算法思路:
      调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在,申请一q结点,存入元素x,然后修改指针,将q结点插入p结点之前
      此算法时间复杂度主要算在查找算法getlist(L,i);上,故T(n)=O(n);

    2. 双向循环链表——删除

    删除: 即实现删除链表L第i结点 的运算,如图
    在这里插入图片描述

    • 算法思路:
      调用查找算法Getlist(L,i);,获取结点ai的指针p,若p存在,则修改指针删除

    概念我们了解了,接下来我们要去实现双向链表的操作。

    双向链表的插入创建

    文件一:dlist.h 插入创建双向链表

    #ifndef __DLIST_H__
    #define __DLIST_H__
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node{
    
       int data;
       struct node *prior;
       struct node *next;
    
    }dlistnode;
    
    
    extern dlistnode *dlist_create();
    extern void dlist_show(dlistnode *H);
    #endif
    

    在这里插入图片描述
    文件二:dlist.c 插入创建双向链表

    #include"dlist.h"
    
    //创建双向链表
    dlistnode *dlist_create(){
       dlistnode *H,*p,*r;
       int num;
    
       if(( H =(dlistnode *)malloc(sizeof(dlistnode))) == NULL){
    	puts("malloc failed");
    	return NULL;
       }
       //建立空双向链表
       H->prior = H;   //头结点前驱后继都指向自己
       H->next = H;    
       r = H;          //指针r 指向头结点
       //用户输入
       while(1) {
           puts("please input(-1 exit):");
           scanf("%d",&num);
           if(num == -1){
    	       puts("-1 exit");
    	       break;
           }
    
           if((p = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
    	puts("malloc failed");
    	return NULL;
           }
           //新节点赋值
           p->data = num;
           
           //插入双向链表
           p->prior = r;
           p->next = r->next;
           r->next = p;
           H->prior = p;
           r = p;
    
       } 
       return H;
    }
    
    //遍历链表并输出链表数据
    void dlist_show(dlistnode *H){
    
       dlistnode *p;
       p = H->next;
    
       while(p != H){
           printf("%d ",p->data);
           p=p->next;
       }
       puts("");
    }
    
    

    文件三:test.c 插入创建双向链表

    #include"dlist.h"
    
    
    int main(){
    
       dlistnode *H;
    
       H=dlist_create();
    
       dlist_show(H);
    
       return 0;
    }
    
    

    在这里插入图片描述

    双向链表——查找

    查找:getlist(L,i);提供要查找结点ai的编号,返回指向该结点ai的指针
    在这里插入图片描述
    结点个数 n=3; i的范围【0,n-1】

    文件一:dlist.h 插入创建双向链表

    #ifndef __DLIST_H__
    #define __DLIST_H__
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node{
    
       int data;
       struct node *prior;
       struct node *next;
    
    }dlistnode;
    
    extern dlistnode *dlist_create();
    extern void dlist_show(dlistnode *H);
    extern dlistnode *dlist_get(dlistnode *H,int pos)#endif
    

    文件二:dlist.c 按位查找双向链表

    dlistnode *dlist_get(dlistnode *H,int pos){
        int i =-1;
        dlistnode *p = H;
    
        if(pos < 0){
            puts("pos < 0,invalid");
            return NULL;
        }
        
        while(i < pos){
    	   p = p->next;
    	   i++;
    	   if(p == H){
    	       puts("pos is invalid");
    	       return NULL;
    	   }
        }
        return p;
    }
    

    文件三:test.c 用户输入按位查找双向链表

    #include"dlist.h"
    
    
    int main(){
    
       dlistnode *H,*p;
       int pos;
    
       H=dlist_create();
    
       dlist_show(H);
       
       //用户输入按位查找
       while(1){
          puts("input pos");
          scanf("%d",&pos);
          p =  dlist_get(H,pos);
          if(p){
             printf("%d \n",p->data);
          }
       }
       return 0;
    }
    

    在这里插入图片描述

    双向链表——插入

    插入: 即实现在链表L的第i结点前插入一结点x的运算,如图
    在这里插入图片描述

    • 算法思路:
      调用查找算法Getlist(L,i);,获取结点ai的指针p。若存在,申请一q结点,存入元素x,然后修改指针,将q结点插入p结点之前
      此算法时间复杂度主要算在查找算法getlist(L,i);上,故T(n)=O(n);

    文件一:dlist.h 插入创建双向链表

    #ifndef __DLIST_H__
    #define __DLIST_H__
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node{
    
       int data;
       struct node *prior;
       struct node *next;
    
    }dlistnode;
    
    extern dlistnode *dlist_create();
    extern void dlist_show(dlistnode *H);
    extern dlistnode *dlist_get(dlistnode *H,int pos);
    extern int dlist_insert(dlistnode *H , int value ,int pos);
    #endif
    

    文件二:dlist.c 按位插入双向链表

    int dlist_insert(dlistnode *H , int value ,int pos){
    	dlistnode *p,*q;
    
    	p = dlist_get(H,pos);
    	if(p == NULL){
                return -1;
    	}
            
            if((q = (dlistnode *)malloc(sizeof(dlistnode))) == NULL){
    	   puts("malloc failed");
    	   return -1;
            } 
    	q->data = value;
    
    	q->prior = p->prior;
    	q->next = p;
    	p->prior->next = q;
    	q->prior = q;
    
    	return 0;
    }
    

    文件三:test.c 用户输入按位插入双向链表

    #include"dlist.h"
    
    
    int main(){
    
       dlistnode *H;
       int pos;
    
       H=dlist_create();
    
       dlist_show(H);
       
       //用户输入按位查找
         while(1){
          puts("input pos");
          scanf("%d",&pos);
          
          dlist_insert(H,100,pos);
          dlist_show(H);
          }
       return 0;
    }
    

    在这里插入图片描述

    双向链表——删除

    删除: 即实现删除链表L第i结点 的运算,如图
    在这里插入图片描述

     p->prior->next = p->next;
     p->next->prior = p-prior;
    
    • 算法思路:
      调用查找算法Getlist(L,i);,获取结点ai的指针p,若p存在,则修改指针删除
      文件一:dlist.h 插入创建双向链表
    #ifndef __DLIST_H__
    #define __DLIST_H__
    #include<stdio.h>
    #include<stdlib.h>
    
    typedef struct node{
    
       int data;
       struct node *prior;
       struct node *next;
    
    }dlistnode;
    
    extern dlistnode *dlist_create();
    extern void dlist_show(dlistnode *H);
    extern dlistnode *dlist_get(dlistnode *H,int pos);
    extern int dlist_insert(dlistnode *H , int value ,int pos);
    extern int dlist_delete(dlistnode *H ,int pos);
    #endif
    

    文件二:dlist.c 用户输入按位删除双向链表

    int dlist_delete(dlistnode *H ,int pos){
        dlistnode *p;
    
        p = dlist_get(H,pos);
        if(p == NULL){
                return -1;
        }
        
        p->prior->next = p->next;
        p->next->prior = p-prior;
    
        free(p);
        p=NULL;
        return 0;
    }
    

    文件三:test.c 用户输入按位删除双向链表

    #include"dlist.h"
    
    int main(){
    
       dlistnode *H;
       int pos;
    
       H=dlist_create();
    
       dlist_show(H);
    
        while(1){
          puts("input pos");
          scanf("%d",&pos);
          
          dlist_delete(H,pos);
          dlist_show(H);
        }
       return 0;
    }
    
    

    在这里插入图片描述

    -----------------------------------------很棒学习完了数据结构的 双向循环链表--------------------------------------------------

    在这里插入图片描述

    --------------------------------------------------------[下期预告:线性表的应用举例]------------------------------------------------------

    展开全文
  • 【数据结构算法】③、双向链表和双向循环链表的实现、双向链表的创建-遍历-插入-删除-删除指定元素-查询指定元素、双向循环链表的创建-遍历-插入删除

    【数据结构算法】③、双向链表和双向循环链表的实现

    数据结构与算法 总共分为19个系列
    ①、数据结构与算法[基础]+线性结构部分内容篇
    ②、单向循环链表的创建插入删除实现篇
    ③、双向链表和双向循环链表的实现篇

    请添加图片描述

    ③、双向链表和双向循环链表的实现篇

    ⭐️本文章知识点大纲

    双向链表

    1. 双向链表的介绍
    2. 双向链表的介绍-创建遍历
    3. 双向链表的插入
    4. 双向链表的删除
    5. 双向链表的删除指定元素
    6. 双向链表的查找指定元素

    双向循环链表

    1. 双向循环链表的介绍
    2. 双向循环链表的介绍-创建遍历
    3. 双向循环链表的插入
    4. 双向循环链表的删除

    ⭐️双向链表

    ①、线性表 - 双向链表的介绍

    双向链表(创建/插入/删除/查找/替换)

    双向链表的特点
    每个节点都包含3个部分

    1. 包含前驱 prior
    2. 包含数据源
    3. 包含后继 指针域

    1.1 流程图 - 双向链表 - 单个节点 结构

    请添加图片描述

    1.2 流程图 - 双向链表 整个链表

    双向链表 带有头节点 和不带有头节点的结构图
    链表最好不要使用头插法。因为头插法插入的数据是倒序的

    请添加图片描述


    ②、线性表 - 双向链表 创建

    2.1 流程图 - 双向链表 创建

    请添加图片描述

    双向链表的 头节点的前驱不是L,而是空,后继也是空。因为我们不知道后继有没有东西。所以后继也要是空的。

    2. 🌰案例 - 双向链表 - 创建、遍历 代码实现

    #include <stdio.h>
    #include "string.h"
    #include "ctype.h"
    #include "stdlib.h"
    #include "math.h"
    #include "time.h"
    
    #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;
    
    //5.1 创建双向链接
    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; // 创建一个临时变量 指向*L
        // 使用尾插法插入数据 插入10个数据    
        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;
    }
    
    //5.2 打印循环链表的元素
    void display(LinkList L){
        
        //  不需要把头结点打印出来 
        // 所以拿到L->next 也就是头结点的下一个结点
        LinkList temp = L->next;
        // 判断打印的结点是不是空
        if(temp == NULL){
            printf("打印的双向链表为空!\n");
            return;
        }
        // 循环打印
        while (temp) {
            printf("%d  ",temp->data);
            temp = temp->next;
        }
        printf("\n");
        
    }
    
    
    int main(int argc, const char * argv[]) {
        // insert code here...
        printf("Hello, World!\n");
        
        Status iStatus = 0;
        LinkList L;
        int temp,item,e;
        
        iStatus =  createLinkList(&L);
        printf("iStatus = %d\n",iStatus);
        printf("链表创建成功,打印链表:\n");
        display(L);
    
        return 0;
    }
    
    

    ③、线性表 - 双向链表 插入

    比如我要往AB中间插入一个C
    也就是ACB
    那么步骤流程就是
    1.1 先找到A结点§
    2.1 创建C结点 (temp)
    3.1 把B(p-next)的前驱指向C .
    3.2 把C结点(temp)的后继(next)指向B(p-next)。
    4.1 把A的后继(next)指向C(temp).
    4.2 把C结点的前驱指向A

    如果插入到尾部的时候情况
    比如从ABC
    插入一个D
    那么步骤就是
    1.1 先找到C结点§
    2.1 创建D结点(temp)(后继一开始就是空的)
    3.1 先把D的前驱 指向 C
    3.2 把C的后继(p->next)(之前是空的) 指向D

    3.1 流程图 - 双向链表 插入

    请添加图片描述

    3.2 结果图 - 双向链表 插入

    请添加图片描述

    3. 🌰案例 - 双向链表 - 插入 代码实现

    //5.3 双向链表插入元素
    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;
    }
    
    

    ④、线性表 - 双向链表 删除

    比如我要往ABC中间删除B
    删除的步骤

    1. 先找到A(变量p)
    2. 创建一个临时变量(delTemp)记录B
    3. 用A(变量p)的后继(next)
      指向
      B的前驱(deltemp的prior)的
      指向
      C的前驱(C的prior)
    4. 然后C的前驱指向A的后续
    5. 把B结点删除 释放掉

    4.2 结果图 - 双向链表 删除

    请添加图片描述

    4. 🌰案例 - 双向链表 - 删除 代码实现

    //5.4 删除双向链表指定位置上的结点
    // e表示删除的元素 可以返回回去
    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;
        
    }
    
    

    ⑤、线性表 - 双向链表 删除指定元素

    比如我从一个双向链表1-10
    我要删除5(变量p)
    步骤

    1. 找到p的前驱(prior) - 也就是4的(p->prior)
    2. 找到4的next 指向 6的前驱
      (p->next->prior)
    3. 没有找到 那么就将p=p->next

    5. 🌰案例 - 双向链表 - 删除指定元素 代码实现

    //5.5 删除双向链表指定的元素
    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;
        
    }
    

    ⑥、线性表 - 双向链表 查找元素

    6. 🌰案例 - 双向链表 - 删除指定元素 代码实现

    //5.6.1 在双向链表中查找元素
    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;
    }
    

    ⑦、线性表 - 双向链表 更新

    7. 🌰案例 - 双向链表 - 更新 代码实现

    //5.6.2 在双向链表中更新结点
    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;
    }
    
    

    💡⑧、双向链表end - 双向链表 - 综合代码

    #include <stdio.h>
    #include "string.h"
    #include "ctype.h"
    #include "stdlib.h"
    #include "math.h"
    #include "time.h"
    
    #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;
    
    //5.1 创建双向链接
    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;
    }
    
    //5.2 打印循环链表的元素
    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");
        
    }
    
    //5.3 双向链表插入元素
    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;
    }
    
    //5.4 删除双向链表指定位置上的结点
    // e表示删除的元素 可以返回回去
    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;
        
    }
    
    //5.5 删除双向链表指定的元素
    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;
        
    }
    
    //5.6.1 在双向链表中查找元素
    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;
    }
    
    //5.6.2 在双向链表中更新结点
    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;
    }
    
    int main(int argc, const char * argv[]) {
        // insert code here...
        printf("Hello, World!\n");
        
        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 %d",&temp,&item);
        iStatus = ListInsert(&L, temp, item);
        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);
        iStatus = LinkListDeletVAL(&L, temp);
        printf("删除指定data域等于%d的结点,双向链表:\n",temp);
        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;
    }
    
    

    ⭐️双向循环链表

    ①、线性表 - 双向循环链表的介绍

    双向循环链表特点是:
    最后一个结点的next指向链表的指针(*L)

    1.1 流程图 - 双向循环链表 - 整个链表结构

    请添加图片描述


    ②、线性表 - 双向循环链表 创建

    2. 🌰案例 - 双向循环链表 创建 代码实现

    //6.1 双向循环链表初始化
    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;
       
    }
    
    

    ③、线性表 - 双向循环链表 遍历

    3. 🌰案例 - 双向循环链表 遍历 代码实现

    //6.3 遍历双向循环链表
    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;
    }
    
    

    ④、线性表 - 双向循环链表 插入

    双向循环链表我们没有创建头结点
    双向循环我们创建了头结点
    因为有了头结点
    我们插入的时候 不需要判断是不是要添加到首元节点
    所以我们根本就不需要去判断*L 头部
    尾部还是要判断的

    🌰说明步骤
    比如在AB之间插入C
    A表示(变量p)
    C表示(temp)

    1. 先判断索引值的异常 也就是在链表哪个位置进行插入
    2. 先找到 A(变量p)
    3. 创建C结点(temp)
    4. 将C结点的(next) 指向 B(p->next)
    5. 将B结点(p->next)的前驱(p->next->prior)指向C
    6. 将A结点(变量p)next 指向C结点(temp)
    7. 将C结点的前驱(temp->prior) 指向A结点(变量p)

    4.1 结果图 - 双向循环链表 插入

    请添加图片描述

    4. 🌰案例 - 双向循环链表 插入 代码实现

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

    ⑤、线性表 - 双向循环链表 删除

    逻辑基本上是和双向链表基本相似
    考虑删除只有一个结点的情况(此时应该还有2个结点 包含头节点)

    5.1 结果图 - 双向循环链表 删除

    请添加图片描述

    5. 🌰案例 - 双向循环链表 删除 代码实现

    //6.4 双向循环链表删除结点
    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;
        
    }
    
    

    💡⑤、双向循环链表end - 双向链表 - 综合代码

    #include <stdio.h>
    #include "string.h"
    #include "ctype.h"
    #include "stdlib.h"
    #include "math.h"
    #include "time.h"
    
    #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;
    
    //6.1 双向循环链表初始化
    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;
       
    }
    
    //6.2 双向循环链表插入元素
    /*当插入位置超过链表长度则插入到链表末尾*/
    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;
    }
    
    
    //6.3 遍历双向循环链表
    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;
    }
    
    //6.4 双向循环链表删除结点
    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;
        
    }
    
    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.双向循环链表头文件及函数声明 2.初始化 1.结点构造 2.初始化函数 3.结点申请 4.数据插入 1.按位置插入 2.尾插 3.头插 5.查找 6.数据删除 1.按位置删除 2.按值删除 3.尾...

    目录

    前言

     一、双向循环链表

    循环结构

    1.双向循环链表头文件及函数声明

    2.初始化

    1.结点构造

    2.初始化函数

    3.结点申请

     4.数据插入

    1.按位置插入

    2.尾插

    3.头插

     5.查找

     6.数据删除

    1.按位置删除

     2.按值删除

    3.尾删 

    4.头删 

    7.清空与销毁 

    1.清空

    2.销毁

    8.双向循环链表源文件及整体函数实现 

    总结


    前言

    这次我们将学习双向循环链表,首先了解双向链表和循环链表的定义和讲解。

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点,是单链表的进阶,比单链表的结点结构多出一个指向前驱的指针域,如下图所示:

    循环链表是一种链式储存结构,它的最后一个结点指向头结点,形成一个环。因此,从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致,差别仅仅在于算法中的循环条件有所不同。方法是将尾结点中的指针域进行使用,指向首结点,如下图所示:

    双向循环链表即是将上述二者联合起来使用,以达到完成各类工作的效用,在以后大多数链表结构的使用中,我们都会选择双向循环链表。


     一、双向循环链表

    循环结构

     双向循环链表的循环方式是其尾结点的后继指针指向头结点(表头),而头结点的前置指针指向尾结点,达到双向循环的目的,这样不仅使得对链表尾部的操作更为简单,也减少了对NULL指针的引用。

    1.双向循环链表头文件及函数声明

    新建头文件"dclist.h"(double circle list)对链表函数声明进行保存,方便我们后期查看及使用

    #pragma once
    #include<stdio.h>
    #include<string.h>
    #include<assert.h>
    #include<ctype.h>
    #include<stdlib.h>
    
    typedef int Element;
    
    typedef struct DNode
    {
    	Element data;
    	DNode* next;
    	DNode* prev;
    }DNode, * PDNode;
    
    //初始化链表
    void InitList(PDNode plist);
    
    //购买结点
    PDNode BuyNode();
    
    //头插
    bool Push_Front(PDNode plist, Element val);
    
    //尾插
    bool Push_Back(PDNode plist, Element val);
    
    //按位置插
    bool Insert_Pos(PDNode plist, int pos, Element val);
    
    //头删
    bool Pop_Front(PDNode plist);
    
    //尾删
    bool Pop_Back(PDNode plist);
    
    //按位置删
    bool Erease_Pos(PDNode plist, int pos);
    
    //按值删
    bool Erease_Val(PDNode plist, Element val);
    
    //查找  返回结点地址
    PDNode Find(PDNode plist, Element val);
    
    //判空
    bool IsEmpty(PDNode plist);
    
    //获取元素个数
    int GetSize(PDNode plist);
    
    //打印链表
    void Print(PDNode plist);
    
    //清空
    void Clear(PDNode plist);
    
    //销毁
    void Destroy(PDNode plist);

     

    2.初始化

    在对使用链表进行数据的储存之前,我们需要进行链表的初始化

    1.结点构造

    如图所示,带双向循环链表的结点由三部分构成:

    1.数据域

    2.指针域1:指向后继结点的指针

    3.指针域2:指向前置结点的指针

    typedef int Element;//如此对数据类型进行改名操作,若要进行修改数据类型操作会更加方便
    
    typedef struct DNode
    {
    	Element data;
    	DNode* next;//后继指针
    	DNode* prev;//前置指针
    }DNode, * PDNode;

    2.初始化函数

    与单链表不同的是,在双向循环链表不存在数据时,头结点的指针域不置为NULL,其后继指针与前置指针都指向头结点本身,以形成最基础的循环形态:

    //初始化链表
    void InitList(PDNode plist)
    {
    	assert(plist != NULL);
    	plist->next = plist->prev = plist;
    }

    3.结点申请

    因为链表的结构特性,我们需要对结点进行多次申请,为了方便进行其他函数操作,并且为了优化代码,我们将结点的申请封装于一个函数

    //购买结点
    PDNode BuyNode()
    {
    	PDNode node = (PDNode)malloc(sizeof(DNode));
    	if (node == NULL)
    	{
    		exit(1);
    	}
    	memset(node, 0, sizeof(*node));//将申请的结点内存重置,防止数据残留
    	return node;
    }

     4.数据插入

    双向循环链表存在多个指针指向的断开和重新指向,我们在此先进行分析和讲解,如下图所示:

     

    按照正常逻辑,我们再重新指定指针指向时,首先需要打破原有的指针指向,即上图中红叉部分,但实际编写程序中,我们会直接修改指针的指向,从而在代码中只会体现重新指向的过程。

    在图中,已经标注出4个指针指向的修改,首先,我们应该对新申请的结点中指针(即图中34箭头的指向)进行指定,因为如果我们先对旧有指针进行修改,那么我们可能会丢失结点的地址信息,从而失去我们已经保存的数据。

    其中指针具体的指向修改,我们不用太在意顺序,只需要记住先考虑新节点的指向,后修改旧结点的指向即可,下面的代码中,我们将采用4321的顺序:

    1.按位置插入

    我们先进行通用插入的实现:

    //按位置插
    bool Insert_Pos(PDNode plist, int pos, Element val)
    {
    	assert(plist != NULL);
        //判断插入位置是否合法
    	if (pos < 0 || pos > GetSize(plist))
    	{
    		return false;
    	}
    	PDNode node = plist;//将结点指针定位至需要插入数据位置之前的结点
    	for (int i = 0; i < pos; i++)
    	{
    		node = node->next;
    	}
    	PDNode newnode = BuyNode();//申请新节点 
    	newnode->data = val;
        //以下为插入步骤
    	newnode->next = node->next;//4
    	newnode->prev = node;//3
    	node->next->prev = newnode;//2
    	node->next = newnode;//1
    	return true;
    }

    2.尾插

    因为表头的前置指针指向尾结点,所以我们不用像单链表一样进行遍历后才能尾插。

    //尾插
    bool Push_Back(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	PDNode newnode = BuyNode();
    	newnode->data = val;
        //插入
    	newnode->next = plist;//4
    	newnode->prev = plist->prev;//3
        plist->prev = newnode;//2
    	plist->prev->next = newnode;//1
    	return true;
    }

    3.头插

    直接调用按位置插入,插入位置为0

    //头插
    bool Push_Front(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	return Insert_Pos(plist, 0, val);
    }

     5.查找

    查找与普通链表的查找基本相同,但是在while循环中的结束条件不同,以结点指针是否指向表头来判断

    //查找  返回结点地址
    PDNode Find(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	PDNode node = plist->next;
        //遍历链表查找与val 相同的值
    	while (node != plist && node->data != val)
    	{
    		node = node->next;
    	}
    	if (plist == node)
    	{
    		return NULL;
    	}
    	return node;
    }

     6.数据删除

    双向循环链表的删除大致与单链表相同,但在两相隔结点的重新链接时需要连结两个指针,即被删除结点的前置结点的后继指针指向被删除结点的后继结点,而后继结点的前置指针指向前置结点

    1.按位置删除

    //按位置删
    bool Erease_Pos(PDNode plist, int pos)
    {
    	assert(plist != NULL);
    	if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist))
    	{
    		return false;
    	}
    	PDNode delnode = plist;
    	for (int i = 0; i <= pos; i++)
    	{
    		delnode = delnode->next;
    	}
        //重新连结
    	delnode->prev->next = delnode->next;
    	delnode->next->prev = delnode->prev;
    	free(delnode);
    	delnode = NULL;
    	return true;
    }

     2.按值删除

    这里调用了查找函数,找到val值所在的结点

    //按值删
    bool Erease_Val(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	PDNode delnode = Find(plist, val);
    	if (delnode == NULL)
    	{
    		return false;
    	}
    	delnode->prev->next = delnode->next;
    	delnode->next->prev = delnode->prev;
    	free(delnode);
    	delnode = NULL;
    	return true;
    }

    3.尾删 

    同样的,因为表头的前置指针指向尾结点,则可以减少遍历链表所消耗的资源。

    //尾删
    bool Pop_Back(PDNode plist)
    {
    	assert(plist != NULL);
    	if (IsEmpty(plist))
    	{
    		return false;
    	}
    	PDNode delnode = plist->prev;
    	delnode->prev->next = delnode->next;
    	delnode->next->prev = delnode->prev;
    	free(delnode);
    	delnode = NULL;
    	return true;
    }

    4.头删 

    直接调用按位置删除,删除位置为0

    //头删
    bool Pop_Front(PDNode plist)
    {
    	assert(plist != NULL);
    	return Erease_Pos(plist, 0);
    }

    7.清空与销毁 

    1.清空

    这里我们使用比较简单的方法,一直头删即可,当然这里的尾删也可以使用,消耗资源相同。

    //清空
    void Clear(PDNode plist)
    {
    	assert(plist != NULL);
    	while (!IsEmpty(plist))
    	{
    		Pop_Front(plist);
    	}
    }

    2.销毁

    调用清空函数,并使链表达到未初始化的状态。

    //销毁
    void Destroy(PDNode plist)
    {
    	Clear(plist);
    	plist->next = plist->prev = NULL;
    }

    8.双向循环链表源文件及整体函数实现 

    #include "dclist.h"
    
    //初始化链表
    void InitList(PDNode plist)
    {
    	assert(plist != NULL);
    	plist->next = plist->prev = plist;
    }
    
    //购买结点
    PDNode BuyNode()
    {
    	PDNode node = (PDNode)malloc(sizeof(DNode));
    	if (node == NULL)
    	{
    		exit(1);
    	}
    	memset(node, 0, sizeof(*node));
    	return node;
    }
    
    //头插
    bool Push_Front(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	return Insert_Pos(plist, 0, val);
    }
    
    //尾插
    bool Push_Back(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	PDNode newnode = BuyNode();
    	newnode->data = val;
    	newnode->prev = plist->prev;
    	newnode->next = plist;
    	plist->prev->next = newnode;
    	plist->prev = newnode;
    	return true;
    }
    
    //按位置插
    bool Insert_Pos(PDNode plist, int pos, Element val)
    {
    	assert(plist != NULL);
    	if (pos < 0 || pos > GetSize(plist))
    	{
    		return false;
    	}
    	PDNode node = plist;
    	for (int i = 0; i < pos; i++)
    	{
    		node = node->next;
    	}
    	PDNode newnode = BuyNode();
    	newnode->data = val;
    	newnode->next = node->next;
    	newnode->prev = node;
    	node->next->prev = newnode;
    	node->next = newnode;
    	return true;
    }
    
    //头删
    bool Pop_Front(PDNode plist)
    {
    	assert(plist != NULL);
    	return Erease_Pos(plist, 0);
    }
    
    //尾删
    bool Pop_Back(PDNode plist)
    {
    	assert(plist != NULL);
    	if (IsEmpty(plist))
    	{
    		return false;
    	}
    	PDNode delnode = plist->prev;
    	delnode->prev->next = delnode->next;
    	delnode->next->prev = delnode->prev;
    	free(delnode);
    	delnode = NULL;
    	return true;
    }
    
    //按位置删
    bool Erease_Pos(PDNode plist, int pos)
    {
    	assert(plist != NULL);
    	if (pos < 0 || pos >= GetSize(plist) || IsEmpty(plist))
    	{
    		return false;
    	}
    	PDNode delnode = plist;
    	for (int i = 0; i <= pos; i++)
    	{
    		delnode = delnode->next;
    	}
    	delnode->prev->next = delnode->next;
    	delnode->next->prev = delnode->prev;
    	free(delnode);
    	delnode = NULL;
    	return true;
    }
    
    //按值删
    bool Erease_Val(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	PDNode delnode = Find(plist, val);
    	if (delnode == NULL)
    	{
    		return false;
    	}
    	delnode->prev->next = delnode->next;
    	delnode->next->prev = delnode->prev;
    	free(delnode);
    	delnode = NULL;
    	return true;
    }
    
    //查找  返回结点地址
    PDNode Find(PDNode plist, Element val)
    {
    	assert(plist != NULL);
    	PDNode node = plist->next;
    	while (node != plist && node->data != val)
    	{
    		node = node->next;
    	}
    	if (plist == node)
    	{
    		return NULL;
    	}
    	return node;
    }
    
    //判空
    bool IsEmpty(PDNode plist)
    {
    	assert(plist != NULL);
    	return (plist->next == plist->prev && plist->next == plist);
    }
    
    //获取元素个数
    int GetSize(PDNode plist)
    {
    	assert(plist != NULL);
    	PDNode node = plist->next;
    	int count = 0;
    	while (node != plist)
    	{
    		node = node->next;
    		count++;
    	}
    	return count;
    }
    
    //打印链表
    void Print(PDNode plist)
    {
    	assert(plist != NULL);
    	PDNode node = plist->next;
    	while (node != plist)
    	{
    		printf("%d ", node->data);
    		node = node->next;
    	}
    	printf("\n");
    }
    
    //清空
    void Clear(PDNode plist)
    {
    	assert(plist != NULL);
    	while (!IsEmpty(plist))
    	{
    		Pop_Front(plist);
    	}
    }
    
    //销毁
    void Destroy(PDNode plist)
    {
    	Clear(plist);
    	plist->next = plist->prev = NULL;
    }


     

    总结

    以上为双向循环链表的实现和方法讲解,双向循环链表为比较常用的链表形式,学习并理解双向循环链表会方便以后的学习。

    展开全文
  • 设计算法,判断带头结点的循环双向链表是否对称 算法思路: ⚫ 建立两个工作指针p和q,p从左向右扫描L,q从右向左扫描L,两者同时扫描⚫ 进入while循环判断,若p与q不相等且p的后继不等于q ⚫ 若对应数据结点的data...
  • 说明 相比Linux内核链表宿主结构可有多个链表结构的优点,本函数集侧重封装性和易用性,而灵活性和效率有所降低. 可基于该函数集方便地构造栈或队列集. 本函数集暂未考虑并发保护. 一 概念 链表是一种物理存储单元上非...
  • =tail){ //这里因为不知道链表是奇数个还是偶数个所以两个条件都写上了 if(pre->data==tail->data){ pre=pre->next; tail=tail->prior; } } if(pre==tail||pre->next==tail){ //这里根据指针判断是否...
  • 双向循环链表,顾名思义就是在双向链表的基础上,将尾节点的“right”指针指向头结点,同时头结点的“left”指针指向尾节点,它和双向链表的不同是,其判断节点是否遍历完毕的条件不再是是否为空,而是是否回到了头...
  • 双向循环链表定义 双向循环链表(Double Cycle Linked List)是双向链表的一种更复杂的变形,头结点的上一节点链接域指向尾结点,而尾结点的下一节点链接域指向头节点。 节点示意图 表元素域elem用来存放具体的...
  • 通过上文,了解相信大家已经简单了解了单链表的结构,本文主要介绍循环双向链表,简单说就是双向链表和循环链表的结合,为什么把它放在一起实现呢,因为总体而言,循环双向链表基本解决了各类链表的弊端,实用性较强...
  • 双向循环链表的C语言实现 头文件 #include<stdio.h> #include<stdlib.h> //结果函数状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define ...
  • 用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
  • 双向循环链表,即每个节点都拥有一前一后两个指针且头尾互链的链表。各种链表的简单区别如下:单向链表:基本链表;单向循环链表:不同于单向链表以 NULL 判断链表的尾部,单向循环链表的尾部链接到表头,因此当迭代...
  • 双向循环链表详解及其基本功能的实现

    多人点赞 热门讨论 2022-01-25 19:37:54
    在单链表详解中我们提到了链表的几种基本的结构,在这里要详细讲到的就是带头双向循环链表,其结构如下: 该链表拥有1个头节点,且每个节点都有一个前驱指针和一个后继指针,分别用来保存前一个节点的地址和后一个...
  • 判断循环链表是否对称 二、解题思路 解题思路很简单,跟判断回文数的方法类似,只不过换成了链表。 首先需要写出循环链表,第二,则判断是否对称 判断是否对称,定义两个指针,p1指针指向头指针的后继(头遍历...
  • 单链表、循环链表、双向循环链表总结

    千次阅读 多人点赞 2019-11-23 18:56:31
    链表介绍 不带头结点的单向链表 带头结点的单向链表 循环链表 双向循环链表
  • 1、单项循环列表单向循环链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。和单链表相比,循环单链表的长处是从链尾到链头...
  • 带头结点双向循环链表基本操作(c语言版)
  • 判断循环链表是否对称

    千次阅读 2021-03-18 15:08:25
    题目:设计一个算法判断带头结点的循环链表是否对称 分析: 简单分析,我们可以设置两个指针,pre和next,从头结点出发,进行比较,若pre与next所指值不同,则不对称,若pre和next指向了同一个节点 则该循环双...
  • 双向循环链表的合并

    2021-05-23 08:11:38
    循环链表和双向链表的区别是是什么?最后一个结点指针指向不同 在建立一个...双向循环链表中如何交换两个结点,为什么我p , q交换 先用笨的办法,把p ,q分别摘下来,然后插回去就可以了 t=p->next;t->pre=p...
  • //双向循环链表 可栈可队列 public class LinkedList implements List , Dequeue , Stack { private class Node {//结点定义参数 E data; Node pre; //直接前驱 Node next;//直接后继 public Node(){ this(null,...
  • 针对带头的双向循环链表的基本功能展开讲解: 目录 1.结构体定义 a. typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* _next; struct ListNode* _prev; }ListNode;
  • 队列--双向循环链表实现 通过对线性表的插入删除操作在异端完成 比如: 头插入对应的是尾删除 尾插入对应的是头删除 出数据的一端是队头,进数据的是队尾 栈: 先进后出 队列: 先进先出 */ // ...
  • C语言双向循环链表

    2021-08-07 20:03:39
    在C语言中,链表分为单向链表双向链表,单向链表只能朝一个方向遍历,中间的一个节点只能由上一个节点推出,只能往前推,无法往后推,关于单向链表的介绍可以点击单向链表介绍。 这次介绍双向链表,既然叫双向就...
  • 数据结构c语言双向循环链表 双向循环链表在定义上类似于循环单链表,就多了个前指针,以方便于向前查找。在双向链表中需要同时修改两个方向的指针,是单向链表指针的两倍。 完整代码如下: #include <stdio.h>...
  • 文章目录一:双向链表(一):双向链表的结构(二):数据的构建(三):创建节点(四):创建链表(五):插入1:表头法插入2:表尾法插入3:指定位置插入(六):删除1:头删除 一:双向链表 (一):双向链表的...
  • Java实现带头结点的双向循环链表

    千次阅读 2019-10-18 16:45:58
    文章目录一、什么是双向循环链表?二、带头结点的双向循环链表的实现 一、什么是双向循环链表? 双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同,双向链表也有带头结点结构和不带头结点结构两种...
  • 文章不空谈理论,完全采用手把手教学,并有综合示例练习题,看完这篇,你绝对能掌握数据结构双向循环链表

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,029
精华内容 20,011
关键字:

判断双向循环链表