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

C语言数据结构之双向链表_c语言 双向链表

作者：不正经 | 2024-04-24 03:30:12

赞

踩

c语言 双向链表

前言

        前面介绍了单链表，由于单链表遍历查找是单向性的，故引出了双向链表的概念，也叫双链表，既可以向前查找，也可以向后遍历。

C语言数据结构之单链表

C语言数据结构之双向链表

c语言数据结构之栈

c语言数据结构之队列
​​​​​​​
C语言数据结构之树

1   双链表

1.1  基本结构

在单链表的基础上增加一个前驱指针，每个数据结点中都有两个指针，分别指向直接后继和直接前驱。初始化一个头节点，前驱指针和后驱指针均指向NULL，头节点的数据域是有数据的，这点跟单链表不同。

pre表示前驱指针，指向当前结点的前一个结点，如果当前结点是头结点，则pre指针为空；

next表示后继指针，指向当前结点的下一个结点，如果当前结点是尾结点，则next指针为空。

  1. typedef struct _NODE {
  2.     int data;
  3.     struct _NODE *next;   //后继指针
  4.     struct _NODE *pre;    //前驱指针
  5. }Node,*Nodelist;

1.1  创建双链表

调用malloc函数申请内存的时候返回值是指向申请的地址，如果申请失败返回NULL，这里我们最好要养成习惯判断是否内存申请成功；exit函数的作用是退出当前程序的进程；头节点的两个指针都指向NULL，并给头节点输入数据；当输入文件结束符(window下输入ctrl+z、linux下输入ctrl+d)的时候就完成链表的创建。

  1. Nodelist double_link_create()
  2. {
  3.     int Data = 0;
  4.     Node *p = NULL;
  5.     Node *head = (Nodelist)malloc(sizeof(Node));
  6.     if(head == NULL){
  7.         printf("head malloc fail.\n");
  8.         exit(-1);
  9.     }
  10.     head->pre = NULL;
  11.     head->next = NULL;
  12.     printf("window下输入ctrl+z完成创建;linux下输入ctrl+d完成创建\n");
  13.     printf("please input data:");
  14.     scanf("%d",&Data);
  15.     head->data = Data;
  16.     p = head;
  17.  
  18.     while(scanf("%d",&Data) != EOF){
  19.         Node *q = (Nodelist)malloc(sizeof(Node));
  20.         if(q == NULL){
  21.             printf("malloc fail.\n");
  22.             exit(-1);
  23.         }
  24.         q->data = Data;
  25.         q->pre = p;
  26.         q->next = NULL;
  27.         p->next = q;
  28.         p = q;
  29.     }
  30.  
  31.     return head;
  32. }

1.2  链表中插入新节点

双向链表的插入操作，首先需要开辟一个新的节点内存空间，然后将它的pre指针指向所需插入位置的前一个结点，同时，它所需插入的前一个结点的next指针修改指向为该新的结点，同理，该新的结点的next指针将会指向一个原本的下一个结点，而修改下一个结点的pre指针为指向新结点自身。

还需要对插入位置进行考虑：①插入到头节点位置处理；②插入到链表中间处理；③插入到表尾处理；④插入位置超过链表本身长度处理。

  1. Nodelist double_link_insert(Nodelist h, int addr, int data)
  2. {
  3.     Node *p = h;
  4.     Node *add_node = (Nodelist)malloc(sizeof(Node));
  5.     if(add_node == NULL){
  6.         printf("malloc fail.\n");
  7.         exit(-1);
  8.     }
  9.     add_node->data = data;
  10.  
  11.     if(addr == 1){          //插入到头节点要特殊考虑
  12.         add_node->pre = NULL;
  13.         add_node->next = p;
  14.         p->pre = add_node;
  15.         h = add_node;       //头节点指向新节点
  16.         return h;
  17.     }
  18.     else{
  19.         for(int i = 1; i < addr; i++){
  20.             if(p->next != NULL){
  21.                 p = p->next;
  22.             }
  23.             else{           //addr错误则将新节点链接在表尾
  24.                 printf("addr is too large\n");
  25.                 add_node->pre = p;
  26.                 add_node->next = NULL;
  27.                 p->next = add_node;
  28.                 return h;
  29.             }
  30.         }
  31.         add_node->pre = p->pre;
  32.         add_node->next = p;
  33.         p->pre = add_node;
  34.     }
  35.     return h;
  36. }

1.3  链表删除节点

首先，指定需要删除的结点位置，选中这个结点的前一个结点，将前一个结点的next指针指向自己的下一个结点，同时，选中该节点的下一个结点，将下一个结点的pre指针修改指向为自己的上一个结点，最后，释放删除结点的内存空间。

逻辑注意事项：①假设指定删除位置超过链表本身长度如何处理；②删除头节点处理；③删除为节点处理；④删除中间节点处理。

  1. Nodelist double_link_delete(Nodelist h, int addr)
  2. {
  3.     Node *p = h;
  4.     for(int i = 1; i < addr; i++){
  5.         if(p->next != NULL){
  6.             p = p->next;
  7.         }
  8.         else{
  9.             printf("addr error,function exit.\n");
  10.             return h;
  11.         }
  12.     }
  13.     if(addr == 1){          //删除头节点
  14.         p->next->pre = NULL;
  15.         h = p->next;
  16.         free(p);
  17.     }
  18.     else{
  19.         if(p->next == NULL){    //删除尾节点
  20.             p->pre->next = NULL;
  21.             free(p);
  22.         }
  23.         else{
  24.             p->pre->next = p->next;
  25.             p->next->pre = p->pre;
  26.             free(p);
  27.         }
  28.     }
  29.     return h;
  30. }

2  示例程序

双链表主要懂如何插入、删除操作，其它的修改、查询、打印等都跟单链表差不多，逻辑点比较简单，重点是学会对指针的使用。

  1. /****************************************
  2. Fuction:C语言实现双向链表
  3. Time:9/21/2022
  4. Author:Qurry
  5. ****************************************/
  6.  
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10.  
  11. typedef struct _NODE {
  12.     int data;
  13.     struct _NODE *next;   //后继指针
  14.     struct _NODE *pre;    //前驱指针
  15. }Node,*Nodelist;
  16.  
  17. /**********    创建双链表    ************/
  18. Nodelist double_link_create()
  19. {
  20.     int Data = 0;
  21.     Node *p = NULL;
  22.     Node *head = (Nodelist)malloc(sizeof(Node));
  23.     if(head == NULL){
  24.         printf("head malloc fail.\n");
  25.         exit(-1);
  26.     }
  27.     head->pre = NULL;
  28.     head->next = NULL;
  29.     printf("window下输入ctrl+z完成创建;linux下输入ctrl+d完成创建\n");
  30.     printf("please input data:");
  31.     scanf("%d",&Data);
  32.     head->data = Data;
  33.     p = head;
  34.  
  35.     while(scanf("%d",&Data) != EOF){
  36.         Node *q = (Nodelist)malloc(sizeof(Node));
  37.         if(q == NULL){
  38.             printf("malloc fail.\n");
  39.             exit(-1);
  40.         }
  41.         q->data = Data;
  42.         q->pre = p;
  43.         q->next = NULL;
  44.         p->next = q;
  45.         p = q;
  46.     }
  47.  
  48.     return head;
  49. }
  50.  
  51. /*********  链表增加节点  ***********
  52.  * addr:增加节点的位置
  53.  * data:增加节点的数据
  54.  * ********************************/
  55. Nodelist double_link_insert(Nodelist h, int addr, int data)
  56. {
  57.     Node *p = h;
  58.     Node *add_node = (Nodelist)malloc(sizeof(Node));
  59.     if(add_node == NULL){
  60.         printf("malloc fail.\n");
  61.         exit(-1);
  62.     }
  63.     add_node->data = data;
  64.  
  65.     if(addr == 1){          //插入到头节点要特殊考虑
  66.         add_node->pre = NULL;
  67.         add_node->next = p;
  68.         p->pre = add_node;
  69.         h = add_node;       //头节点指向新节点
  70.         return h;
  71.     }
  72.     else{
  73.         for(int i = 1; i < addr; i++){
  74.             if(p->next != NULL){
  75.                 p = p->next;
  76.             }
  77.             else{           //addr错误则将新节点链接在表尾
  78.                 printf("addr is too large\n");
  79.                 add_node->pre = p;
  80.                 add_node->next = NULL;
  81.                 p->next = add_node;
  82.                 return h;
  83.             }
  84.         }
  85.         add_node->pre = p->pre;
  86.         add_node->next = p;
  87.         p->pre = add_node;
  88.     }
  89.     return h;
  90. }
  91.  
  92. /***********   链表删除节点   *************
  93.  * addr:删除节点的位置
  94.  * **************************************/
  95. Nodelist double_link_delete(Nodelist h, int addr)
  96. {
  97.     Node *p = h;
  98.     for(int i = 1; i < addr; i++){
  99.         if(p->next != NULL){
  100.             p = p->next;
  101.         }
  102.         else{
  103.             printf("addr error,function exit.\n");
  104.             return h;
  105.         }
  106.     }
  107.     if(addr == 1){          //删除头节点
  108.         p->next->pre = NULL;
  109.         h = p->next;
  110.         free(p);
  111.     }
  112.     else{
  113.         if(p->next == NULL){    //删除尾节点
  114.             p->pre->next = NULL;
  115.             free(p);
  116.         }
  117.         else{
  118.             p->pre->next = p->next;
  119.             p->next->pre = p->pre;
  120.             free(p);
  121.         }
  122.     }
  123.     return h;
  124. }
  125.  
  126. /**********     链表修改数据       **********
  127.  * old_data:要修改的数据
  128.  * new_data:修改后的数据
  129.  * ****************************************/
  130. void double_link_modify(Nodelist h, int old_data, int new_data)
  131. {
  132.     Node *p = h;
  133.     while(p->data != old_data){
  134.         if(p->next != NULL){
  135.             p = p->next;
  136.         }
  137.         else{
  138.             printf("old_data error!\n");
  139.             return;
  140.         }
  141.     }
  142.     p->data = new_data;
  143. }
  144.  
  145. /********    链表查找数据    *********
  146.  * addr:查找数据的位置
  147.  * *********************************/
  148. void double_link_find(Nodelist h, int addr)
  149. {
  150.     Node *p = h;
  151.     for(int i = 1; i < addr; i++){
  152.         if(p->next != NULL){
  153.             p = p->next;
  154.         }
  155.         else{
  156.             printf("addr error,function exit.\n");
  157.             return;
  158.         }
  159.     }    
  160.     printf("Data:%d\n",p->data);
  161. }
  162.  
  163. /**********      链表数据打印       **********/
  164. void double_link_print(Nodelist h)
  165. {
  166.     Node *p = h;
  167.     int inode = 1;
  168.     while(1){
  169.         printf("Node[%d]:%d\n",inode++,p->data);
  170.         if(p->next == NULL){
  171.             return;
  172.         }
  173.         else{
  174.             p = p->next;
  175.         }    
  176.     }
  177. }
  178.  
  179. /***********    选择菜单     **************/
  180. int menu_select()
  181. {
  182.     int num;
  183.     printf("1:插入节点   2:修改节点   3:删除节点   4:打印节点数据    5:查找节点数据     0:退出\n");
  184.     printf("Please input num : ");
  185.     scanf("%d",&num);
  186.     return num;
  187. }
  188.  
  189. /************    退出释放内存   ************/
  190. void free_node(Nodelist H)
  191. {
  192.     Node *P = H->next;
  193.     while(1){
  194.         free(P);
  195.         P = P->next;
  196.         if(P->next == NULL){
  197.             free(P);
  198.             break;
  199.         }
  200.     }
  201. }
  202.  
  203. void main()
  204. {
  205.     Node *head = NULL;
  206.     int mode,addr,data1,data2;
  207.     head = double_link_create();
  208.     
  209.     while(1){
  210.         mode = menu_select();
  211.         switch (mode)
  212.         {
  213.             case 0:
  214.                 printf("Bye bye!\n");
  215.                 free_node(head);
  216.                 exit(0);
  217.  
  218.             case 1:
  219.                 printf("please input addr & data:");
  220.                 scanf("%d %d",&addr,&data1);
  221.                 head = double_link_insert(head,addr,data1);
  222.                 break;
  223.  
  224.             case 2:
  225.                 printf("please input old data & new data:");
  226.                 scanf("%d %d",&data1,&data2);
  227.                 double_link_modify(head,data1,data2);
  228.                 break;
  229.  
  230.             case 3:
  231.                 printf("please input addr:");
  232.                 scanf("%d",&addr);
  233.                 head = double_link_delete(head,addr);
  234.                 break;
  235.  
  236.             case 4:
  237.                 double_link_print(head);
  238.                 break;
  239.  
  240.             case 5:
  241.                 printf("please input addr:");
  242.                 scanf("%d",&addr);
  243.                 double_link_find(head,addr);
  244.                 break;
  245.  
  246.             default:
  247.                 printf("input num error!\n");
  248.                 break;
  249.         }
  250.     }
  251. }

linux下测试结果

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

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

  

闽ICP备14008679号