devbox
代码艺术创作者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构之双向链表_双向链表数据结构

作者：代码艺术创作者 | 2024-02-02 12:47:28

赞

踩

双向链表数据结构

双向链表与单向链表较为类似，单向链表有一个指针域，用来指向后继结点，而双向链表有两个指针域，分别用来指向前驱结点和后继结点。玩双向链表时一定要从单向链表的思维中跳出来，否则在操作双向链表时就会出现各种问题。在玩双向链表时，一定要动手画图或者在脑子里画图，考虑好每个操作细节。 

 一、双向链表的基本操作

双向链表的数据结构：

  1. typedef struct node//定义双向链表的数据结构
  2. {
  3.     int data;
  4.     struct node * prior;
  5.     struct node * next;
  6. }Node;

这里以整型作为结点数据域的数据类型

1. 初始化链表

        Node * initialize();

       创建头结点，初始化头结点的各个成员变量，返回头结点的指针

 2.头插法添加结点

        void insertFirst(Node * head,int data);

        方法形参上需传入头结点指针和新结点的数据，方法内会创建新结点，之后操作新结点、头结点、首结点，将新结点插入首结点的位置

3.尾插法添加结点

        void append(Node * head,int data);

        方法形参上需传入头结点指针和新结点的数据，方法内会创建新结点，之后操作头结点、末结点、新结点，将新结点插入到末结点的后面

4.删除结点

        int delete(Node * head,int data);

         方法形参上需传入头结点指针和结点的数据，方法内会从首结点向末结点遍历，查找指定数据的结点，若查找成功，则删除该结点，返回1，若查找无果，返回0

5.反转链表

        void reverse(Node * head);

          方法形参上需传入头结点指针,方法内会将链表的首尾顺序进行颠倒，原先的首结点作尾结点，原先的尾结点作首结点

6.正向遍历链表

        void traverse(Node * head);

          方法形参上需传入头结点指针，方法内输出链表的所有结点数据，不包括头结点

7.反向遍历链表

        void traverseReversely(Node * head);

        方法形参上需传入头结点指针，方法内从末结点到首结点进行数据输出，不输出头结点

二、代码实现

  1.  
  2. /*
  3. 双向链表
  4.     初始化链表
  5.     增加结点(头插法、尾插法)
  6.     删除结点
  7.     反转链表
  8.     遍历链表(正向遍历，反向遍历)
  9. */
  10. #include<stdio.h>
  11. #include<stdlib.h>
  12.  
  13. typedef struct node//定义双向链表的数据结构
  14. {
  15.     int data;
  16.     struct node * prior;
  17.     struct node * next;
  18. }Node;
  19.  
  20. Node * initialize();//初始化链表
  21. void insertFirst(Node * head,int data);//头插法添加结点
  22. void append(Node * head,int data);//尾插法添加结点
  23. int delete(Node * head,int data);//删除结点
  24. void reverse(Node * head);//反转链表
  25. void traverse(Node * head);//正向遍历链表
  26. void traverseReversely(Node * head);//反向遍历链表
  27.  
  28. int main(int argc,char * argv[])
  29. {
  30.     puts("------------------初始化链表------------------");
  31.     Node * head=initialize();
  32.     printf("head->prior=%p\n",head->prior);   
  33.     printf("head->next=%p\n",head->next);   
  34.     printf("head->data=%i\n",head->data);   
  35.  
  36.     puts("------------------头插法插入30，50，80------------------");
  37.     insertFirst(head,30);
  38.     insertFirst(head,50);
  39.     insertFirst(head,80);
  40.     
  41.     puts("------------------正向遍历链表------------------");
  42.     traverse(head);
  43.     puts("------------------反向遍历链表------------------");
  44.     traverseReversely(head);
  45.  
  46.     puts("------------------尾插法插入18，19，20------------------");
  47.     append(head,18);
  48.     append(head,19);
  49.     append(head,20);
  50.     puts("------------------正向遍历链表------------------");
  51.     traverse(head);
  52.     puts("------------------反向遍历链表------------------");
  53.     traverseReversely(head);
  54.     
  55.     puts("------------------删除数据为20的结点------------------");
  56.     puts(delete(head,20)?"删除成功":"删除失败");
  57.     traverse(head);
  58.  
  59.     puts("------------------删除数据为80的结点------------------");
  60.     puts(delete(head,80)?"删除成功":"删除失败");
  61.     traverse(head);
  62.    
  63.     puts("------------------删除数据为30的结点------------------");
  64.     puts(delete(head,30)?"删除成功":"删除失败");
  65.     traverse(head);
  66.  
  67.     puts("------------------尾插法插入90，150------------------");
  68.     append(head,90);
  69.     append(head,150);
  70.     traverse(head);
  71.     
  72.     puts("------------------反转链表------------------");
  73.     reverse(head);
  74.     traverse(head);
  75.     
  76.     puts("------------------再反转链表------------------");
  77.     reverse(head);
  78.     traverse(head);
  79.  
  80.     return 0;
  81. }
  82.  
  83. Node * initialize()//初始化链表
  84. {
  85.     Node * head=(Node *)malloc(sizeof(Node));
  86.     head->data=0;//头结点的数据域用来存储链表中结点的数量，不包括头结点
  87.     head->prior=NULL;//头结点的前指针域置为空，在整个程序的运行过程中不作改变
  88.     head->next=NULL;//头结点的后指针域暂时置为空，在整个程序的运行过程中会产生变化
  89.     return head;
  90. }
  91.  
  92. void insertFirst(Node * head,int data)//头插法添加结点
  93. {
  94.     Node * newborn=(Node *)malloc(sizeof(Node));//创建新结点
  95.     newborn->data=data;//为新结点的数据域赋值
  96.     /*
  97.     采用头插法为双向链表添加结点时，
  98.     注意：链表中只有一个头结点时，有三个指针变量需要赋值，
  99.         分别是新结点前指针域、后指针域，头结点的后指针域
  100.         链表中除了头结点外，还存在其它结点，有四个指针变量需要赋值
  101.         分别是新结点前指针域、后指针域，原先的首结点的前指针域，头结点的后指针域
  102.     */
  103.     newborn->prior=head;
  104.     newborn->next=head->next;
  105.     if(head->next!=NULL)//链表中不是只有头结点，头结点有后继结点，该后继结点就是首结点
  106.     {
  107.         head->next->prior=newborn;//将首结点的前指针域指向新结点
  108.     }
  109.     head->next=newborn;//头结点的后指针域指向新结点
  110.     head->data++;//头结点的数据域自增
  111. }
  112.  
  113. void append(Node * head,int data)//尾插法添加结点
  114. {
  115.     Node * begin=head;//定义指针变量begin，初始值为头结点的指针，将其作为循环变量
  116.     for(;begin->next!=NULL;begin=begin->next);//遍历至末结点
  117.     
  118.     Node * newborn=(Node *)malloc(sizeof(Node));//创建新结点
  119.     newborn->data=data;//为新结点的数据域赋值
  120.     newborn->prior=begin;//新结点的前指针域指向末结点
  121.     newborn->next=begin->next;//把末结点后指针域的值赋给新结点的后指针域
  122.     begin->next=newborn;  //末结点的后指针域指向新结点
  123.     head->data++;//链表中结点数量自增
  124. }
  125.  
  126. int delete(Node * head,int data)//删除结点
  127. {
  128.     for(Node * begin=head->next;begin;begin=begin->next)//从首结点向尾结点进行遍历
  129.     {
  130.         if(begin->data==data)//若查找到指定数据的结点,先问问该结点是否为末结点
  131.         {
  132.             if(begin->next!=NULL)//若非末结点
  133.             {
  134.                 begin->prior->next=begin->next;
  135.                 begin->next->prior=begin->prior;
  136.             }else//若为末结点
  137.             {
  138.                 begin->prior->next=begin->next;
  139.             }
  140.             free(begin);//释放要删除的结点空间
  141.             head->data--;//链表中的结点数量自减
  142.             return 1;
  143.         }
  144.     }
  145.     return 0;
  146. }
  147.  
  148. void reverse(Node * head)//反转链表
  149. {
  150.     //反转链表使用头插法完成
  151.     Node * temporary;//临时变量，作一个中间存储
  152.     Node * begin=head->next;//定义指针变量begin，存储首结点的指针
  153.     head->next=NULL;//头结点的后指针域置为空
  154.     while(begin)//从首结点向末结点进行遍历
  155.     {
  156.         temporary=begin->next;//将当前结点的后继结点指针存储到指针变量temporary中，
  157.         //当前结点的两个指针域重新赋值后，就无法确定原先的后继结点，这里先把其后续结点指针存储起来
  158.         begin->prior=head;//当前结点的前指针域指向头结点
  159.         begin->next=head->next;//当前结点的后指针域指向头结点后指针域的指向
  160.         if(head->next!=NULL)//若头结点后指针域不为空，则说明链表中不是只有头结点
  161.         {
  162.             head->next->prior=begin;//头结点的后继结点前指针域指向当前结点
  163.         }
  164.         head->next=begin;//头结点的后指针域指向当前结点
  165.         begin=temporary;//指针变量begin从当前结点转到下一个结点
  166.     }
  167. }
  168.  
  169. void traverse(Node * head)//正向遍历链表
  170. {
  171.     //头结点的数据域不进行展示,这里直接用head->next表示其它结点
  172.     //用前驱的后指针域表示后继结点
  173.     if(head->next->next==NULL)//到达末结点
  174.     {
  175.         printf("%d\n",head->next->data);
  176.         return;
  177.     }
  178.     printf("%d , ",head->next->data);
  179.     traverse(head->next);
  180. }
  181.  
  182. void traverseReversely(Node * head)//反向遍历链表
  183. {
  184.     Node * begin=head->next;//将首结点的指针赋给指针变量begin
  185.     while(begin->next!=NULL)//将指针变量begin作为循环变量进行遍历，循环条件是begin未到达末结点
  186.     {
  187.         begin=begin->next;//指针变量begin向末结点遍历
  188.     }
  189.     while(begin!=head)
  190.     {
  191.         if(begin->prior==head)//到达首结点
  192.         {
  193.             printf("%d\n",begin->data);
  194.         }else
  195.         {
  196.             printf("%d , ",begin->data);
  197.         }
  198.         begin=begin->prior;
  199.     }
  200. }

三、运行展示

 四、总结

        玩双向链表，画图第一步，代码第二步，运行第三步。细心、耐心、恒心即可把玩双链表。

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

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

  

闽ICP备14008679号