详解双向链表的基本操作(C语言)

(4) 2024-04-21 08:23

Hi,大家好,我是编程小6,很荣幸遇见你,我把这些年在开发过程中遇到的问题或想法写出来,今天说一说详解双向链表的基本操作(C语言),希望能够帮助你!!!。

工科生一枚,热衷于底层技术开发,有强烈的好奇心,感兴趣内容包括单片机,嵌入式Linux,Uboot等,欢迎学习交流!
爱好跑步,打篮球,睡觉。
欢迎加我QQ1500836631(备注CSDN),一起学习交流问题,分享各种学习资料,电子书籍,学习视频等。

文章目录

    • 1.双向链表的定义
    • 2.双向链表的创建
    • 3.双向链表的插入
    • 4.双向链表的删除
    • 5.双向链表更改节点数据
    • 6.双向链表的查找
    • 7.双向链表的打印
    • 8.测试函数及结果

1.双向链表的定义

上一节学习了单向链表单链表详解。今天学习双链表。学习之前先对单向链表和双向链表做个回顾。
单向链表特点
  1.我们可以轻松的到达下一个节点, 但是回到前一个节点是很难的.
  2.只能从头遍历到尾或者从尾遍历到头(一般从头到尾)
双向链表特点
  1.每次在插入或删除某个节点时, 需要处理四个节点的引用, 而不是两个. 实现起来要困难一些
  2.相对于单向链表, 必然占用内存空间更大一些.
  3.既可以从头遍历到尾, 又可以从尾遍历到头
双向链表的定义:
  双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。下图为双向链表的结构图。
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第1张
  从上中可以看到,双向链表中各节点包含以下 3 部分信息:
  指针域:用于指向当前节点的直接前驱节点;
  数据域:用于存储数据元素。
  指针域:用于指向当前节点的直接后继节点;
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第2张
双向循环链表的定义:
  双向链表也可以进行首尾连接,构成双向循环链表,如下图所示
在创建链表时,只需要在最后将收尾相连即可(创建链表代码中已经标出)。其他代码稍加改动即可。
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第3张
双链表的节点结构用 C 语言实现为:

/*随机数的范围*/
#define MAX 100
/*节点结构*/
typedef struct Node{ 
   
    struct Node *pre;
    int data;
    struct Node *next;
}Node;

2.双向链表的创建

  同单链表相比,双链表仅是各节点多了一个用于指向直接前驱的指针域。因此,我们可以在单链表的基础轻松实现对双链表的创建。
  需要注意的是,与单链表不同,双链表创建过程中,每创建一个新节点,都要与其前驱节点建立两次联系,分别是:
  将新节点的 prior 指针指向直接前驱节点;
  将直接前驱节点的 next 指针指向新节点;
  这里给出创建双向链表的 C 语言实现代码:

#define MAX 100
Node *CreatNode(Node *head)
{ 
   
        head=(Node*)malloc(sizeof(Node));//鍒涘缓閾捐〃绗竴涓粨鐐癸紙棣栧厓缁撶偣锛?
        if(head == NULL)
        { 
   
            printf("malloc error!\r\n");
            return NULL;
        }
        head->pre=NULL;
        head->next=NULL;
        head->data=rand()%MAX;
        return head;
}
Node* CreatList(Node * head,int length)
{ 
   
    if (length == 1)
    { 
   
        
        return( head = CreatNode(head));
    }
    else
    { 
   
        head = CreatNode(head);
        Node * list=head;
        for (int i=1; i<length; i++) 
        /*创建并初始化一个新结点*/
        { 
   
            Node * body=(Node*)malloc(sizeof(Node));
            body->pre=NULL;
            body->next=NULL;
            body->data=rand()%MAX;
			/*直接前趋结点的next指针指向新结点*/
            list->next=body;
            /*新结点指向直接前趋结点*/
            body->pre=list;
            /*把body指针给list返回*/
            list=list->next;
        }
         
    }
    /*加上以下两句就是双向循环链表*/
    // list->next=head;
    // head->prior=list;
    return head;
}

3.双向链表的插入

  根据数据添加到双向链表中的位置不同,可细分为以下 3 种情况:
1.添加至表头
  将新数据元素添加到表头,只需要将该元素与表头元素建立双层逻辑关系即可。
  换句话说,假设新元素节点为 temp,表头节点为 head,则需要做以下 2 步操作即可:
  temp->next=head; head->prior=temp;
  将 head 移至 temp,重新指向新的表头;
  将新元素 7 添加至双链表的表头,则实现过程如下图所示:
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第4张

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_16933601/article/details/105351119

2.添加至表的中间位置
  同单链表添加数据类似,双向链表中间位置添加数据需要经过以下 2 个步骤,如下图所示:
  新节点先与其直接后继节点建立双层逻辑关系;
  新节点的直接前驱节点与之建立双层逻辑关系;
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第5张
3.添加至表尾
  与添加到表头是一个道理,实现过程如下:
  找到双链表中最后一个节点;
  让新节点与最后一个节点进行双层逻辑关系;
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第6张

/*在第add位置的前面插入data节点*/
Node * InsertListHead(Node * head,int add,int data)
{ 
   
    /*新建数据域为data的结点*/
    Node * temp=(Node*)malloc(sizeof(Node));
    if(temp== NULL)
    { 
   
        printf("malloc error!\r\n");
        return NULL;
    }    
    else
    { 
   
        temp->data=data;
        temp->pre=NULL;
        temp->next=NULL; 
    }
    /*插入到链表头,要特殊考虑*/
    if (add==1)
    { 
   
        temp->next=head;
        head->pre=temp;
        head=temp;
    }
    else
    { 
   
        Node * body=head;
        /*找到要插入位置的前一个结点*/
        for (int i=1; i<add-1; i++)
        { 
   
            body=body->next;
        }
        /*判断条件为真,说明插入位置为链表尾*/
        if (body->next==NULL)
        { 
   
            body->next=temp;
            temp->pre=body;
        }
        else
        { 
   
            body->next->pre=temp;
            temp->next=body->next;
            body->next=temp;
            temp->pre=body;
        }
    }
    return head;
}


/*在第add位置的后面插入data节点*/
Node * InsertListEnd(Node * head,int add,int data)
{ 
   
    int i = 1;
    /*新建数据域为data的结点*/
    Node * temp=(Node*)malloc(sizeof(Node));
    temp->data=data;
    temp->pre=NULL;
    temp->next=NULL;

    Node * body=head;
    while ((body->next)&&(i<add+1))
    { 
   
        body=body->next;
        i++;
    }
    
    /*判断条件为真,说明插入位置为链表尾*/
    if (body->next==NULL)
    { 
   
        body->next=temp;
        temp->pre=body;
        temp->next=NULL;
    }
    else
    { 
   
        temp->next=body->pre->next;
        temp->pre=body->pre;
        body->next->pre=temp;
        body->pre->next=temp;

    }

    return head;
}

4.双向链表的删除

  双链表删除结点时,只需遍历链表找到要删除的结点,然后将该节点从表中摘除即可。
  例如,删除元素 2 的操作过程如图 所示:
详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第7张

Node * DeleteList(Node * head,int data)
{ 
   
    Node * temp=head;
    /*遍历链表*/
    while (temp)
    { 
   
        /*判断当前结点中数据域和data是否相等,若相等,摘除该结点*/
        if (temp->data==data) 
        { 
   
            /*判断是否是头结点*/
            if(temp->pre == NULL)
            { 
   
                head=temp->next;
                temp->next = NULL;
                free(temp);
                return head;
            }
            /*判断是否是尾节点*/
            else if(temp->next == NULL)
            { 
   
                temp->pre->next=NULL;
                free(temp);
                return head;
            }
            else
            { 
   
                temp->pre->next=temp->next;
                temp->next->pre=temp->pre;
                free(temp);
                return head;   
            }
            

        }
        temp=temp->next;
    }
    printf("Can not find %d!\r\n",data);
    return head;
}

5.双向链表更改节点数据

  更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是:通过遍历找到存储有该数据元素的结点,直接更改其数据域即可。

/*更新函数,其中,add 表示更改结点在双链表中的位置,newElem 为新数据的值*/
Node *ModifyList(Node * p,int add,int newElem)
{ 
   
    Node * temp=p;
    /*遍历到被删除结点*/
    for (int i=1; i<add; i++) 
    { 
   
        temp=temp->next;
    }
    temp->data=newElem;
    return p;
}

6.双向链表的查找

  通常,双向链表同单链表一样,都仅有一个头指针。因此,双链表查找指定元素的实现同单链表类似,都是从表头依次遍历表中元素。

/*head为原双链表,elem表示被查找元素*/
int FindList(Node * head,int elem)
{ 
   
/*新建一个指针t,初始化为头指针 head*/
    Node * temp=head;
    int i=1;
    while (temp) 
    { 
   
        if (temp->data==elem)
        { 
   
            return i;
        }
        i++;
        temp=temp->next;
    }
    /*程序执行至此处,表示查找失败*/
    return -1;
}

7.双向链表的打印

/*输出链表的功能函数*/
void PrintList(Node * head)
{ 
   
    Node * temp=head;
    while (temp) 
    { 
   
        /*如果该节点无后继节点,说明此节点是链表的最后一个节点*/
        if (temp->next==NULL) 
        { 
   
            printf("%d\n",temp->data);
        }
        else
        { 
   
            printf("%d->",temp->data);
        }
        temp=temp->next;
    }
}

8.测试函数及结果

int main() 
{ 
   
    Node * head=NULL;
    //创建双链表
    head=CreatList(head,5);
    printf("新创建双链表为\t");
    PrintList(head);
    //在表中第 5 的位置插入元素 1
    head=InsertListHead(head, 5,1);
    printf("在表中第 5 的位置插入元素 1\t");
    PrintList(head);
    //在表中第 3 的位置插入元素 7
    head=InsertListEnd(head, 3, 7);
    printf("在表中第 3 的位置插入元素 7\t");
    PrintList(head);
    // //表中删除元素 7
    head=DeleteList(head, 7);
    printf("表中删除元素 7\t\t\t");
    PrintList(head);
    printf("元素 1 的位置是\t:%d\n",FindList(head,1));
    //表中第 3 个节点中的数据改为存储 6
    head = ModifyList(head,3,6);
    printf("表中第 3 个节点中的数据改为存储6\t");
    PrintList(head);
    return 0;
}

详解双向链表的基本操作(C语言)_https://bianchenghao6.com/blog__第8张
  大家的鼓励是我继续创作的动力,如果觉得写的不错,欢迎关注,点赞,收藏,转发,谢谢!
以上代码均为测试后的代码。如有错误和不妥的地方,欢迎指出。
部分内容参考网络,如有侵权,请联系删除。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_16933601/article/details/105351119

今天的分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

上一篇

已是最后文章

下一篇

已是最新文章

发表回复