devbox
从前慢现在也慢
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

双向链表（Double Linked List）

作者：从前慢现在也慢 | 2024-04-13 23:37:37

赞

踩

双向链表

一、简介

        虽然单向链表能够100%解决逻辑关系为“一对一”数据的存储问题，但在解决那些需要大量查找前趋节点的问题是，单向链表无疑是不能用了，因为单向链表适合“从前往后”查找，并不适合“从后往前”查找。

        如果要提高链表的查找效率，那双向链表（双链表）无疑是首选。

        双向链表字面上的意思是“双向”的链表，如图1所示。

图1 - 双向链表示意图

        双向指各个节点之间的逻辑关系是双向的，该链表通常只有一个头节点。

        从图1还可以看出，双向链表中每个节点包括一下3个部分，分别是指针域（用于指向当前节点的直接前驱节点）、数据域（用于存储数据元素）和指针域（用于指向当前节点的后继节点）。

二、创建

1、声明

  1. typedef struct line{
  2.     struct line *prior;//指向直接前趋
  3.     int data;
  4.     struct line *next;//指向直接后继
  5. }line;

2、创建

  1. line* initLine(line *head){
  2.     head=(line*)malloc(sizeof(line));//创建链表第一个结点（首元结点）
  3.     head->prior=NULL;
  4.     head->next=NULL;
  5.     head->data=1;
  6.     line *list=head;
  7.     for(int i=2; i<=3; i++)
  8.     {
  9.         //创建并初始化一个新结点
  10.         line *body=(line*)malloc(sizeof(line));
  11.         body->prior=NULL;
  12.         body->next=NULL;
  13.         body->data=i;
  14.  
  15.         list->next=body;//直接前趋结点的next指针指向新结点
  16.         body->prior=list;//新结点指向直接前趋结点
  17.         list=list->next;
  18.     }
  19.     return head;
  20. }

三、基本操作

1、添加节点

        添加节点可以分为三种，分别是：添加至表头、添加至链表的中间位置和添加至链表尾。

添加至表头

        将新元素添加到表头，只需要将其与表头元素建立双层逻辑关系即可。

        假设定义新元素节点为tmp，表头节点为head，则只需要执行下面两个步骤和即可：

  1. tmp的next变成head，head的prior编程tmp；
  2. 将head移至tmp，重新指向新的表头。

        比如将元素7天添加到双向链表的表头，则实现过程如图2所示。

图2 - 添加元素至双向链表的表头

添加至链表的中间位置

        添加至表的中间位置主要分为两个步骤：

  1. 新节点先与其后继节点建立双层逻辑关系；
  2. 新节点的前驱与之建立双层逻辑关系。

         此过程如图3所示。

图3 - 双向链表中间位置添加数据元素示意图

 添加至表尾

        与添加至表头很相似，其过程如下：

  1. 找到双向链表的最后一个节点；
  2. 让新节点与其进行双层逻辑关系建立。

        此过程如图4所示。 

图4 - 双向链表尾部添加元素示意图

代码

经过上述内容，我们可以试着编写代码了。

  1. line *insertLine(line *head,int data,int add){
  2.     //新建数据域为data的结点
  3.     line *temp=(line*)malloc(sizeof(line));
  4.     temp->data=data;
  5.     temp->prior=NULL;
  6.     temp->next=NULL;
  7.     //插入到链表头，要特殊考虑
  8.     if(add==1)
  9.     {
  10.         temp->next=head;
  11.         head->prior=temp;
  12.         head=temp;
  13.     }
  14.     else
  15.     {
  16.         line *body=head;
  17.         //找到要插入位置的前一个结点
  18.         for(int i=1; i<add-1; i++)
  19.         {
  20.             body=body->next;
  21.         }
  22.         //判断条件为真，说明插入位置为链表尾
  23.         if(body->next==NULL)
  24.         {
  25.             body->next=temp;
  26.             temp->prior=body;
  27.         }
  28.         else
  29.         {
  30.             body->next->prior=temp;
  31.             temp->next=body->next;
  32.             body->next=temp;
  33.             temp->prior=body;
  34.         }
  35.     }
  36.     return head;
  37. }

2、删除节点

        双向链表删除节点时，只需要遍历到要删除的节点，然后将其删除即可。

        例如，从删除2的过程如图5所示。

图5 - 双向链表删除元素的操作示意图

代码

  1. //删除结点的函数，data为要删除结点的数据域的值
  2. line *delLine(line *head,int data)
  3. {
  4.     line *temp=head;
  5.     //遍历链表
  6.     while(temp)
  7.     {
  8.         //判断当前结点中数据域和data是否相等，若相等，摘除该结点
  9.         if (temp->data==data)
  10.         {
  11.             temp->prior->next=temp->next;
  12.             temp->next->prior=temp->prior;
  13.             free(temp);
  14.             return head;
  15.         }
  16.         temp=temp->next;
  17.     }
  18.     printf("链表中无该数据元素");
  19.     return head;
  20. }

3、查找节点

        依次遍历表中数据，直到找到为止。

代码

  1. //head为原双链表，elem表示被查找元素
  2. int selectElem(line * head,int elem){
  3. //新建一个指针t，初始化为头指针 head
  4.     line * t=head;
  5.     int i=1;
  6.     while(t)
  7.     {
  8.         if(t->data==elem)
  9.         {
  10.             return i;
  11.         }
  12.         i++;
  13.         t=t->next;
  14.     }
  15.     //程序执行至此处，表示查找失败
  16.     return -1;
  17. }

4、更改节点

        在查找的基础上完成。过程是通过遍历找到的节点，直接将数据域修改即可。

代码

  1. //更新函数，其中，add 表示更改结点在双链表中的位置，newElem 为新数据的值
  2. line *amendElem(line *p,int add,int newElem){
  3.     line *temp=p;
  4.     //遍历到被删除结点
  5.     for (int i=1; i<add; i++)
  6.     {
  7.         temp=temp->next;
  8.     }
  9.     temp->data=newElem;
  10.     return p;
  11. }

四、完整代码

        给出的所有代码的整合代码：

  1. #include <bits/stdc++.h>
  2. typedef struct line{
  3.     struct line *prior;
  4.     int data;
  5.     struct line *next;
  6. }line;
  7. //双链表的创建
  8. line* initLine(line * head);
  9. //双链表插入元素，add表示插入位置
  10. line * insertLine(line * head,int data,int add);
  11. //双链表删除指定元素
  12. line * delLine(line * head,int data);
  13. //双链表中查找指定元素
  14. int selectElem(line * head,int elem);
  15. //双链表中更改指定位置节点中存储的数据，add表示更改位置
  16. line *amendElem(line * p,int add,int newElem);
  17. //输出双链表的实现函数
  18. void display(line * head);
  19. int main(){
  20.     line *head=NULL;
  21.     //创建双链表
  22.     head=initLine(head);
  23.     display(head);
  24.     //在表中第 3 的位置插入元素 7
  25.     head=insertLine(head,7,3);
  26.     display(head);
  27.     //表中删除元素 2
  28.     head=delLine(head,2);
  29.     display(head);
  30.  
  31.     printf("元素 3 的位置是：%d\n",selectElem(head,3));
  32.     //表中第 3 个节点中的数据改为存储 6
  33.     head=amendElem(head,3,6);
  34.     display(head);
  35.     return 0;
  36. }
  37. line* initLine(line * head){
  38.     head=(line*)malloc(sizeof(line));
  39.     head->prior=NULL;
  40.     head->next=NULL;
  41.     head->data=1;
  42.     line *list=head;
  43.     for(int i=2; i<=5; i++)
  44.     {
  45.         line*body=(line*)malloc(sizeof(line));
  46.         body->prior=NULL;
  47.         body->next=NULL;
  48.         body->data=i;
  49.  
  50.         list->next=body;
  51.         body->prior=list;
  52.         list=list->next;
  53.     }
  54.     return head;
  55. }
  56. line *insertLine(line *head,int data,int add){
  57.     //新建数据域为data的结点
  58.     line *temp=(line*)malloc(sizeof(line));
  59.     temp->data=data;
  60.     temp->prior=NULL;
  61.     temp->next=NULL;
  62.     //插入到链表头，要特殊考虑
  63.     if(add==1)
  64.     {
  65.         temp->next=head;
  66.         head->prior=temp;
  67.         head=temp;
  68.     }
  69.     else
  70.    	{
  71.         line * body=head;
  72.         //找到要插入位置的前一个结点
  73.         for(int i=1; i<add-1; i++)
  74.         {
  75.             body=body->next;
  76.         }
  77.         //判断条件为真，说明插入位置为链表尾
  78.         if(body->next==NULL)
  79.         {
  80.             body->next=temp;
  81.             temp->prior=body;
  82.         }
  83.         else
  84.         {
  85.             body->next->prior=temp;
  86.             temp->next=body->next;
  87.             body->next=temp;
  88.             temp->prior=body;
  89.         }
  90.     }
  91.     return head;
  92. }
  93. line *delLine(line *head,int data)
  94. {
  95.     line *temp=head;
  96.     //遍历链表
  97.     while(temp)
  98.     {
  99.         //判断当前结点中数据域和data是否相等，若相等，摘除该结点
  100.         if(temp->data==data)
  101.         {
  102.             temp->prior->next=temp->next;
  103.             temp->next->prior=temp->prior;
  104.             free(temp);
  105.             return head;
  106.         }
  107.         temp=temp->next;
  108.     }
  109.     printf("链表中无该数据元素");
  110.     return head;
  111. }
  112. //head为原双链表，elem表示被查找元素
  113. int selectElem(line *head,int elem){
  114. //新建一个指针t，初始化为头指针 head
  115.     line *t=head;
  116.     int i=1;
  117.     while(t)
  118.     {
  119.         if(t->data==elem)
  120.         {
  121.             return i;
  122.         }
  123.         i++;
  124.         t=t->next;
  125.     }
  126.     //程序执行至此处，表示查找失败
  127.     return -1;
  128. }
  129. //更新函数，其中，add 表示更改结点在双链表中的位置，newElem 为新数据的值
  130. line *amendElem(line *p,int add,int newElem){
  131.     line * temp=p;
  132.     //遍历到被删除结点
  133.     for(int i=1; i<add; i++)
  134.     {
  135.         temp=temp->next;
  136.     }
  137.     temp->data=newElem;
  138.     return p;
  139. }
  140. //输出链表的功能函数
  141. void display(line *head)
  142. {
  143.     line *temp=head;
  144.     while(temp)
  145.     {
  146.         if(temp->next==NULL)
  147.         {
  148.             printf("%d\n",temp->data);
  149.         }
  150.         else
  151.         {
  152.             printf("%d->",temp->data);
  153.         }
  154.         temp=temp->next;
  155.     }
  156. }

参考文献：http://c.biancheng.net/view/3343.html

好啦，以上就是本文的全部内容啦！创作不易，点个赞再走呗～

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/419128
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号