精华内容
下载资源
问答
  • 双向循环链表的建立,插入,删除(带头节点
    千次阅读
    2018-01-03 00:28:33
    #include<iostream>
    #include<cstdio>
    #include<malloc.h>
    
    #define OVERFLOW -2
    #define ERROR -1
    
    typedef struct DuLNode{
        int data;
        struct DuLNode *prior,*next;
    }DuLNode,*DuLinkList;
    
    void CreateList_DuL(DuLinkList &L,int n){//头插入法建立双向循环链表
        int data;
        DuLNode *rear,*p;
        rear=L=(DuLinkList)malloc(sizeof(DuLNode));
        L->next=NULL;
        for(int i=0;i<n;i++){
            p=(DuLinkList)malloc(sizeof(DuLNode));
            scanf("%d",&data);
            p->data=data;
            p->next=rear->next;
            rear->next=p;
            p->prior=rear;
            rear=p;
        }
        rear->prior=L;
        L->prior=rear;
    }
    
    void ListInsert_Dul(DuLinkList &L,int i,int e){
        //在双向链表第i个位置插入元素e
        DuLNode *p,*q;
    
        p=L;
        int j=0,data;
        while(p&&j<i-1){
            p=p->next;j++;
        }
        if(!p||j>i-1)return;
        q=(DuLinkList)malloc(sizeof(DuLNode));
        q->data=e;
        q->next=p->next;
        p->next->prior=q;
        p->next=q;
        q->prior=p;
    }
    
    void ListDelete_Dul(DuLinkList &L,int i){
        DuLNode *q,*p;
        p=L;
        int j=0;
        while(p&&j<i){
            p=p->next;j++;
        }
        if(!p||j>i)return;
        p->prior->next=p->next;
        p->next->prior=p->prior;
        free(p);
    }
    int main(){
        DuLinkList T;
        int n;
        printf("输入个数:\n");
        scanf("%d",&n);
        printf("输入个元素:\n");
        CreateList_DuL(T,n);
        printf("插入位置与值\n");
        int pos,val;
        scanf("%d%d",&pos,&val);
        ListInsert_Dul(T,pos,val);//随便想第三个位置插入4
        printf("打印:\n");
        DuLNode *p;
        p=T->next;
        while(p){
            printf("%d ",p->data);
            p=p->next;
        }
        printf("\n删除位置\n");
        scanf("%d",&pos);
        ListDelete_Dul(T,pos);
        printf("打印:\n");
        p=T->next;
        while(p){
            printf("%d ",p->data);
            p=p->next;
        }
    }
    

    更多相关内容
  • 4.双向循环链表 1.单链表: 何为链表? 通过地址的方式,找到数据。 比如 到银行办理业务,业务员根据票号,来找到下一个人进行办理业务。 同样地,链表的意思是,通过一个地址,找到数据。 1.1数据内容...

    1.单链表:

    何为链表?

    通过地址的方式,找到数据。

    比如 到银行办理业务,业务员根据票号,来找到下一个人进行办理业务。

    同样地,链表的意思是,通过一个地址,找到数据。

    1.1数据内容为int型的链表
    public class LinkList{
        public static void main(String[] args){
     
            Node n1=new Node(9);
            Node n2=new Node(8);
            Node n3=new Node(7);
            //追加节点
            n1.append(n2);
            n2.append(n3);
            System.out.println(n1.next().next().getData());//7
    
        }
    
    }
    //构建一个节点类
    class Node{
        //节点内容
        int data;
        //下一个节点
        Node next;
        public Node(int value){
            this.data=value;
        }
    
        //为当前节点追加下一个节点
        public void append(Node node){
            //将当前节点赋值给currentNode
            Node currentNode=this;
            //循环向后找
            while(true){
                
                Node nextNode=currentNode.next;
                //如果下一个节点为空,则退出循环
                if(nextNode==null){
                    break;
                }
                //将下一个节点赋给当前节点
                currentNode=nextNode;
            }
            //因为退出循环的时候,是当下一节点为空的时候,所以把需要返回的节点追加为当前节点的下一节点
            currentNode.next=node;
        }
        //返回下一个节点
        public Node next(){
            return this.next;
        }
        //获得节点内容
        public int getData(){
            return this.data;
        }
    
    }
    
    
    1.2数据内容为数组的链表
    import java.util.Arrays;
    import java.util.Set;
    
    //import com.sun.corba.se.impl.orbutil.graph.Node;
    public class LinkList{
        public static void main(String[] args){
            Node n1=new Node(new int[]{1,2,4,5,6});        
            Node n2=new Node(new int[]{7,8,9,10}); 
            Node n3=new Node(new int[]{11,12,13,14});
            n1.append(n2);
            n2.append(n3);
            //System.out.println(n1.next().getdata());
            n1.next().getdata();//7,8,9,10  
            }   
            
        }
    
     class Node{
        //节点内容
        int[] data;
        //下一个节点
        Node next;
        public Node(int[] value){
            this.data=value;
        }
        //追加节点
        public void append(Node node){
            Node currentNode=this;
            //往后寻找
            while(true){
                Node nextNode=currentNode.next;
                if(nextNode==null){
                    break;
                }
                // 追加下一节点为当前节点;
                currentNode=nextNode;
            }
                //由于当前节点的后一节点为空,因此将node放到当前节点的下一节点       
                currentNode.next=node;
        }
        //返回下一个节点
        public Node next(){
            return this.next;
        }
        public void getdata(){
            for(int i=0;i<data.length;i++){
                System.out.print(data[i]+"\t");
            }
        }
        
    
    }
    

    2.删除插入单链表中的节点

    删除节点:
    public void remove(){
            //取出下下节点
            Node newNext=next.next;
            //将下下节点  赋值给当前节点的下一节点
            this.next=newNext;
    

    思路:

    取出当前节点的下下节点,将下下节点赋值给 当前节点的下一节点。那么原来 当前节点的下一节点就被删除了。

    插入节点:

    我们插入节点只能插入当前节点的下一节点,而不能直接插入给当前节点。

    思路:1.先将当前节点下一节点取出 2.再将需要插入的节点赋值给当前节点的下一节点3.把之前取出的节点作为新节点的下一节点

     //插入节点
        public void add(node){
            //取出下一节点,作为下下节点
            Node nextNode=this.next;
            //将需要插入的节点,作为当前节点的下一节点
            this.next=node;
            //将之前的下下节点作为新节点的下一节点
            node.next=newNode;
        }
    

    3.循环链表

    之前的单向链表是通过一个节点,找下一个节点,但是我们却不能通过其他节点来找第一个节点,那么循环链表的意思就是通过最后一个节点,来寻找到第一个节点。整个节点就串联起来了。

    在这里插入图片描述

    整个循环链表和单链很相似。只需要将下一节点变为当前节点

    import java.util.Arrays;
    import java.util.Set;
    /**循环链表 */
    
    public class LinkList2{
        public static void main(String[] args){
            LoopNode n1=new LoopNode(1);        
            LoopNode n2=new LoopNode(2); 
            LoopNode n3=new LoopNode(3);
            //追加节点
            n1.add(n2);
            n2.add(n3);
            System.out.println(n3.next().getdata());
            
            
           
            
            
            }   
            
        }
    
     class LoopNode{
        //节点内容
        int data;
        //这里就是与单链表的区别,将下一节点初始化为当前节点
        LoopNode next=this;
        public LoopNode(int value){
            this.data=value;
        }
       
        //插入节点
        public void add(LoopNode node){
            //取出下一节点,作为下下节点
            LoopNode nextNode=this.next;
            //将需要插入的节点,作为当前节点的下一节点
            this.next=node;
            //将之前的下下节点作为新节点的下一节点
            node.next=nextNode;
        }
        
       
        //返回下一个节点
        public LoopNode next(){
            return this.next;
        }
        public int getdata(){
            return this.data;
        }
        
    
    }
    

    4.双向循环链表

    通过每个节点可以寻找到他的上一个和下一个节点。因此叫双向。这个相较于单向循环链表,就是多了一个向前的节点。

    核心代码处理解:

    在这里插入图片描述

      public class DoubleLoopLinkList{
        public static void main(String[] args){
           DoubleNode n1=new DoubleNode(2);
           DoubleNode n2=new DoubleNode(3);
           DoubleNode n3=new DoubleNode(4);
           n1.after(n2);
           n2.after(n3);
           System.out.println(n1.next().getdata());//3
           System.out.println(n2.pre().getdata());//2
    
        }
    }
    class DoubleNode{
        //节点数据
        int data;
        //上一个节点
        DoubleNode pre=this;
        DoubleNode next=this;
        
        public DoubleNode(int value){
            this.data=value;
        }
        /*增加节点   双向链表核心代码*/
        public void after(DoubleNode node){
            //原来节点的下一节点,
            DoubleNode nextNext=next;
            //将新节点作为当前节点的下一节点
            this.next=node;
            //把新节点作为当前节点的前一节点;
            node.pre=this;
            //让原来的节点的下一节点作为当前节点的下一节点
            node.next=nextNext;
           //将原来节点的上一节点作为新节点
            nextNext.pre=node;
        } 
        //下一个节点
        public DoubleNode next(){
             return this.next;
        }
        //上一个节点
        public DoubleNode pre(){
            return this.pre;
        }
        public int getdata(){
            return this.data;
        }
        
    }
    

    展开全文
  • 双向链表指定节点后插入节点

    千次阅读 2021-05-25 02:52:35
    要在列表中的指定节点之后插入节点,需要跳过所需数量的节点以便到达目标节点,然后根据需要调整指针。为此,请参考使用以下步骤。为新节点分配内存。 请使用以下语句。ptr = (struct node *)malloc(sizeof(struct ...

    要在列表中的指定节点之后插入节点,需要跳过所需数量的节点以便到达目标节点,然后根据需要调整指针。

    为此,请参考使用以下步骤。

    为新节点分配内存。 请使用以下语句。ptr = (struct node *)malloc(sizeof(struct node));

    使用指针temp遍历列表以跳过所需数量的节点以到达指定节点。temp=head;

    for(i=0;i

    {

    temp = temp->next;

    // the temp will be null if the list doesn't last long up to mentioned location

    if(temp == NULL)

    {

    return;

    }

    }

    temp将指向for循环结束时的指定节点。要在此节点之后插入新节点,因此需要在此处调整ptr指针。使ptr的下一个指针指向temp的下一个节点。ptr -> next = temp -> next;

    使新节点ptr的prev指针指向temp。ptr -> prev = temp;

    使temp指针指向新节点ptr。temp -> next = ptr;

    使temp节点的pre指针指向新节点。temp -> next -> prev = ptr;

    算法

    第1步:IF PTR = NULL

    提示:OVERFLOW

    转到第15步

    [IF结束]

    第2步:设置NEW_NODE = PTR

    第3步:SET PTR = PTR - > NEXT

    第4步:设置NEW_NODE - > DATA = VAL

    第5步:SET TEMP = START

    第6步:SET I = 0

    第7步:重复第8步到第10步直到 I

    第8步:SET TEMP = TEMP - > NEXT

    第9步:如果TEMP = NULL

    第10步:提示 “比所需的元素少”

    转到第15步

    [结束]

    [循环结束]

    第11步:设置NEW_NODE - > NEXT = TEMP - > NEXT

    第12步:设置NEW_NODE - > PREV = TEMP

    第13步:设置TEMP - > NEXT = NEW_NODE

    第14步:设置TEMP - > NEXT - > PREV = NEW_NODE

    第15步:退出

    示意图如下 -

    c6f0204b2e0486b13d2981809d301e1f.png

    使用C语言实现的示意代码 -

    #include

    #include

    void insert_specified(int);

    void create(int);

    struct node

    {

    int data;

    struct node *next;

    struct node *prev;

    };

    struct node *head;

    void main()

    {

    int choice, item, loc;

    do

    {

    printf("Enter the item which you want to insert?\n");

    scanf("%d", &item);

    if (head == NULL)

    {

    create(item);

    }

    else

    {

    insert_specified(item);

    }

    printf("Press 0 to insert more ?\n");

    scanf("%d", &choice);

    } while (choice == 0);

    }

    void create(int item)

    {

    struct node *ptr = (struct node *)malloc(sizeof(struct node));

    if (ptr == NULL)

    {

    printf("OVERFLOW");

    }

    else

    {

    if (head == NULL)

    {

    ptr->next = NULL;

    ptr->prev = NULL;

    ptr->data = item;

    head = ptr;

    }

    else

    {

    ptr->data = item;printf("Press 0 to insert more ?\n");

    ptr->prev = NULL;

    ptr->next = head;

    head->prev = ptr;

    head = ptr;

    }

    printf("Node Inserted\n");

    }

    }

    void insert_specified(int item)

    {

    struct node *ptr = (struct node *)malloc(sizeof(struct node));

    struct node *temp;

    int i, loc;

    if (ptr == NULL)

    {

    printf("OVERFLOW\n");

    }

    else

    {

    printf("Enter the location\n");

    scanf("%d", &loc);

    temp = head;

    for (i = 0;i < loc;i++)

    {

    temp = temp->next;

    if (temp == NULL)

    {

    printf("can't insert\n");

    return;

    }

    }

    ptr->data = item;

    ptr->next = temp->next;

    ptr->prev = temp;

    temp->next = ptr;

    temp->next->prev = ptr;

    printf("Node Inserted\n");

    }

    }

    执行上面示例代码,得到以下结果 -

    Enter the item which you want to insert?

    12

    Node Inserted

    Press 0 to insert more ?

    0

    Enter the item which you want to insert?

    90

    Node Inserted

    Press 0 to insert more ?

    2

    ¥ 我要打赏

    纠错/补充

    收藏

    加QQ群啦,易百教程官方技术学习群

    注意:建议每个人选自己的技术方向加群,同一个QQ最多限加 3 个群。

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

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

    数据结构与算法 总共分为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;
    }
    
    
    
    展开全文
  • 双向循环链表——插入2. 双向循环链表——删除 单向循环链表 关于两个循环链表合并为一个循环链表 双向循环链表 在单链表L中,查找ai的后继Next(L,a;),耗时仅为O(1),因为取ai后继指针即可。 但查找a;的直接...
  • 今天我们要来实现的是对双向循环链表进行节点插入。大家可以和《C语言实现单链表节点插入》单链表的节点插入对比着学习。代码上传至 https://github.com/chenyufeng1991/InsertDoubleLinkedList 。核心代码...
  • 双向循环链表插入 -- C语言

    千次阅读 2020-02-19 16:14:05
    /*构建双向循环链表*/ tail = getDouListTail(gDoubHead); tail->next = gDoubHead; gDoubHead->prev = tail; insertDoubLoopSortedListNode(&gDoubHead, 22); insertDoubLoopSortedListNode(&gDoubHead, 21)...
  • #include#includetypedef struct DoubleLinkedList{int data;struct DoubleLinkedList *pre;struct DoubleLinkedList *next;...//建立链表DlinkedList_Node* createDLink(){DlinkedList_Node *head,*p,*s...
  • 二、双向循环链表 1、双向循环链表示意图 2、双向循环链表节点设计 struct d_node{ int data; //数据域 struct d_node *next; struct d_node *prev; }; 3、双向循环链表的一般性结构 1)只有头结点的情况 2)...
  • 双向链表插入节点

    千次阅读 2017-09-12 23:15:00
    双向链表插入节点 1、根据实例分析 2、把节点之间的关系看成 是边的拆除和重建 3、为了方便叙述,给边标了号 如图所示是我们要操作的结构体和在双向链表的图。 现在我们的目的就是在ab节点之间插入x节点。 ...
  • 双向循环链表,顾名思义就是在双向链表的基础上,将尾节点的“right”指针指向头结点,同时头结点的“left”指针指向尾节点,它和双向链表的不同是,其判断节点是否遍历完毕的条件不再是是否为空,而是是否回到了头...
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示
  • 说明 相比Linux内核链表宿主结构可有多个链表结构的优点,本函数集侧重封装性和易用性,而灵活性和效率有所降低. 可基于该函数集方便地构造栈或队列集. 本函数集暂未考虑并发保护. 一 概念 链表是一种物理存储单元上非...
  • 双向循环链表 众所周知,单向链表想要查找当前节点的上一个数据,必须得重新把链表遍历一遍,十分浪费资源;(这也是链表不如数组高效的一个方面,数组只需要知道下标即可一步到位) 而如果可以创建一种双向的链表,...
  • 一、双向循环链表 循环结构 1.双向循环链表头文件及函数声明 2.初始化 1.结点构造 2.初始化函数 3.结点申请 4.数据插入 1.按位置插入 2.尾插 3.头插 5.查找 6.数据删除 1.按位置删除 2.按值删除 3.尾...
  • 双向链表插入、删除、与创建的原理: 其实双向链表和单链表的区别主要是在节点的结构上,因为节点结构不同,进而导致相关操作较单链表也就有了一些差异;双向链表,顾名思义,从头可以到尾,由尾也可以到头;双向...
  • 双向链表插入、删除节点(详细图解+代码)

    万次阅读 多人点赞 2020-02-01 20:36:36
    双向链表 在单链表的基础上增加了前缀结点,一定程度上提升了查找元素的速度 在查找元素时,可以反向查找前缀结点 插入结点过程(分为4步) 这四个步骤的顺序可调整,但是必须要保证需要的链不断!!...
  • 【数据结构-C】双向循环链表基本操作及图解分析

    千次阅读 多人点赞 2022-01-29 16:20:03
    双向链表介绍 ????双向链表的基本操作及图解分析 ????1.双向链表创建新的结点 ????2.双向链表初始化 ????3.双向链表的尾插 ????4.双向链表的头插 ????5.双向链表的头删 ????6.双向链表的尾删 ????7.查找某个...
  • 双向链表插入

    千次阅读 2021-09-20 15:15:06
    将s结点变成a结点的后继,就要给a结点的next域赋值,赋的是新插入结点的地址,而他此时在s里存着 a结点的next域就是p的前驱结点的next,即p->prior->next=s; 接下来s还要作为b的前驱,则又需要修改两个...
  • 双向链表和双向循环链表 和单向链表相比,多了一个前驱结点。如果他为空,那么next和prior都指向自己。而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可。 插入...
  • 双向循环链表

    2018-12-02 19:34:48
    该代码实现了双向循环链表的创建,插入,删除和遍历等功能,方向键上键为插入节点,方向键下键为删除节点,方向键左键为遍历节点并打印。适合初学者学习。注释极其详细。
  • 双向循环链表增删查改C语言实现

    多人点赞 2021-10-05 16:26:13
    目录双向链表的结构双向链表的实现双向链表的声明双向链表的实现结点的创建头结点的创建链表的销毁链表的打印链表的尾插链表的尾删链表的头插链表的头删查找指定位置前插入指定位置删除 双向链表的结构 双向链表...
  • 双向循环链表讲解及实现

    千次阅读 多人点赞 2021-04-08 19:39:36
    带头双向循环链表二.实现(1).动态申请一个结点 一.带头双向循环链表 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个链表虽然结构复杂,但是使用...
  • 一般我们都构造双向循环链表。 双向链表 双向链表节点 typedef int CycleList_Data; typedef struct Cycle_Node { CycleList_Data data; struct Cycle_Node* front; struct Cycle_Node* next; }Cycl
  • 双向链表(1) - 基本介绍以及插入节点

    万次阅读 多人点赞 2015-06-13 23:49:36
    双向链表(1) - 基本介绍以及插入节点
  • 简介:在双向链表中,我们可以通过任意一个结点访问到其前驱元素和后继元素,时间复杂度为O(1),所以双向链表是十分方便的,我们通常构建链表也会选择去构建双向链表。 单个节点包括两个指针: 空表的判断体条件是L...
  • 双向循环链表详解及其基本功能的实现

    多人点赞 热门讨论 2022-01-25 19:37:54
    在单链表详解中我们提到了链表的几种基本的结构,在这里要详细讲到的就是带头双向循环链表,其结构如下: 该链表拥有1个头节点,且每个节点都有一个前驱指针和一个后继指针,分别用来保存前一个节点的地址和后一个...
  • 今天我学习了双向循环链表,不过与以往的不同,这次的双向循环链表 有坑,是巨坑… 我以为写的会很顺利 没想到 我竟然踩了“雷”… 好尴尬哦,下面我们来学习这个 双向循环链表把~ 对了,说一下为什么需要双向循环...
  • 双向链表插入排序(交换节点

    千次阅读 2020-11-16 14:09:37
    插入排序需要从后往前遍历寻找可以插入的位置,所以会使用到双向链表 typedef struct Node//定义的结构体 { int data; struct Node* per; //记录前驱 struct Node* next; }*List; 创建带头节点的双链表 List ...
  • 用C++和Java实现带头节点双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 37,677
精华内容 15,070
关键字:

双向循环链表插入节点