• C理解(四):链表

    本文主要探讨单链表与双链表相关知识。

    linux内核链表(include/linux/list.h)
            内核链表中纯链表封装,纯链表的各种操作函数（节点创建、插入、删除、遍历······）,纯链表内嵌在驱动结构体中,实现驱动的创建、插入、删除、遍历等

    单链表 

            单链表链表头插入节点,尾插入节点,删除节点,逆序

    代码示例:

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. struct node
    5. {
    6.         int data;
    7.         struct node *next;
    8. };
    9.  
    10. //创建节点
    11. struct node * create_node(int data)
    12. {
    13.         struct node *p = (struct node *)malloc(sizeof(struct node));
    14.         if(p == NULL)
    15.         {
    16.                 printf("malloc error\n");
    17.         return NULL;
    18.         }
    19.         p->data = data;
    20.         p->next = NULL;
    21.         return p;
    22. }
    23.  
    24. //头部插入节点
    25. void insert_head(struct node *phead,struct node *new)
    26. {
    27.         struct node *p = phead;
    28.         if(p == NULL)
    29.                 exit(0);
    30.         new->next = p->next;
    31.         p->next = new;
    32.         (phead->data)++;        //头节点存储节点数量
    33. }
    34.  
    35. //尾部插入
    36. void insert_tail(struct node *phead,struct node *new)
    37. {
    38.         struct node *p = phead;
    39.         if(p == NULL)
    40.                 exit(0);
    41.         while(p->next != NULL)
    42.         {
    43.                 p = p->next;
    44.         }
    45.         p->next = new;
    46.         (phead->data)++;        //头节点存储节点数量
    47. }
    48.  
    49. //遍历链表
    50. void printf_link(struct node *phead)
    51. {
    52.         if(phead == NULL)
    53.         exit(0);
    54.         struct node *p = phead;
    55.         printf("num of struct : %d \n",p->data);
    56.         while(p->next != NULL)
    57.         {
    58.                 p = p->next;
    59.                 printf("struct data : %d\n",p->data);
    60.         }
    61. }
    62.  
    63. //删除节点
    64. int  delete_node(struct node *phead,int data)
    65. {
    66.         if(phead == NULL)
    67.         exit(-1);
    68.         struct node *p = phead;
    69.         struct node *prev = NULL;
    70.         while(p->next != NULL)
    71.         {
    72.                 prev = p;
    73.                 p = p->next;
    74.                 if(p->data == data)
    75.                 {
    76.                         if(p->next != NULL)
    77.                         {
    78.                                 prev->next = p->next;   //其他节点
    79.                                 free(p);
    80.                         }
    81.                         else
    82.                         {
    83.                                 prev->next = NULL;      //尾节点
    84.                                 free(p);
    85.                         }
    86.                         (phead->data)--;
    87.                         return 0;
    88.                 }
    89.         }
    90.         printf("have no data\n");
    91.         return -1;
    92. }
    93.  
    94. //链表逆序
    95. void reserve_link(struct node *phead)
    96. {
    97.         if(phead == NULL)
    98.         exit(-1);
    99.         struct node *p = phead->next;
    100.         struct node *back = NULL;
    101.         struct node *prev = NULL;
    102.         if(p->next == NULL || p == NULL)        //只有一个节点,不逆序
    103.         return ;
    104.         while(p->next != NULL)                  //两个及两个以上节点
    105.         {
    106.                 back = p->next;                 //保存链表的下一个节点,由于头插逆序法插入节点与后面节点断开
    107.                 if(p == phead->next)            //第一个节点指向NULL作为逆序首节点
    108.                 {
    109.                         p->next = NULL;
    110.                 }
    111.                 else
    112.                 {
    113.                         p->next = phead->next;
    114.                 }
    115.                 phead->next = p;
    116.                 p = back;
    117.         }
    118.         insert_head(phead,p);   //最后一个节点插入到链表,由于最后一个节点指向NULL,while判断失效
    119.         (phead->data)--;        //头插最后一个节点时,默认新增一个节点
    120. }
    121.  
    122. int main()
    123. {
    124.         //创建头节点
    125.         struct node *head = create_node(0);
    126.  
    127.         //头部插入节点
    128.         insert_head(head,create_node(1));
    129.         insert_head(head,create_node(2));
    130.         insert_head(head,create_node(3));
    131.         insert_head(head,create_node(4));
    132.         insert_head(head,create_node(5));
    133.  
    134.         //尾部插入节点
    135.         insert_tail(head,create_node(1));
    136.         insert_tail(head,create_node(2));
    137.         insert_tail(head,create_node(3));
    138.         insert_tail(head,create_node(4));
    139.         insert_tail(head,create_node(5));
    140.  
    141.         //遍历节点
    142.         printf_link(head);
    143.  
    144.         //删除节点
    145.         delete_node(head,5);
    146.         delete_node(head,5);
    147.         delete_node(head,4);
    148.  
    149.         //遍历节点
    150.         printf_link(head);
    151.  
    152.         //链表逆序
    153.         reserve_link(head);
    154.  
    155.         //遍历节点
    156.         printf_link(head);
    157.  
    158.         return 0;
    159. }

    结果示例:

    双链表

            双链表尾插入,头插入,删除节点,前向遍历,后向遍历 

    代码示例:

    1. #include <stdio.h>
    2. #include <stdlib.h>
    3.  
    4. struct node
    5. {
    6.         int data;
    7.         struct node *next;
    8.         struct node *prev;
    9. };
    10.  
    11. //创建节点
    12. struct node * create_node(int data)
    13. {
    14.         struct node *p = (struct node *)malloc(sizeof(struct node));
    15.         if(p == NULL)
    16.         {
    17.                 printf("malloc error\n");
    18.                 return NULL;
    19.         }
    20.         p->data = data;
    21.         p->next = NULL;
    22.         p->prev = NULL;
    23.         return p;
    24. }
    25.  
    26. //头部插入节点
    27. void insert_head(struct node *phead,struct node *new)
    28. {
    29.         struct node *p = phead;
    30.         if(p == NULL)
    31.                 exit(0);
    32.         new->next = p->next;
    33.         if(p->next != NULL)
    34.         p->next->prev = new;
    35.         p->next = new;
    36.         new->prev = p;
    37.         (phead->data)++;        //头节点存储节点数量
    38. }
    39.  
    40. //尾部插入
    41. void insert_tail(struct node *phead,struct node *new)
    42. {
    43.         struct node *p = phead;
    44.         if(p == NULL)
    45.         exit(0);
    46.         while(p->next != NULL)
    47.         {
    48.                 p = p->next;
    49.         }
    50.         p->next = new;
    51.         new->prev = p;
    52.         new->next = NULL;
    53.         (phead->data)++;        //头节点存储节点数量
    54. }
    55.  
    56. //后项遍历链表
    57. void next_printf_link(struct node *phead)
    58. {
    59.         if(phead == NULL)
    60.         exit(0);
    61.         struct node *p = phead;
    62.         printf("num of struct : %d \n",p->data);
    63.         while(p->next != NULL)
    64.         {
    65.                 p = p->next;
    66.                 printf("struct data : %d\n",p->data);
    67.         }
    68. }
    69.  
    70. //前项遍历链表
    71. void prev_printf_link(struct node *phead)
    72. {
    73.         if(phead == NULL)
    74.                 exit(0);
    75.         struct node *p = phead;
    76.         printf("num of struct : %d \n",p->data);
    77.         while(p->next != NULL)
    78.         {
    79.                 p = p->next;
    80.         }
    81.         while(p->prev != NULL)
    82.         {
    83.                 printf("struct data : %d\n",p->data);
    84.                 p = p->prev;
    85.         }
    86. }
    87.  
    88. //删除节点
    89. int  delete_node(struct node *phead,int data)
    90. {
    91.         if(phead == NULL)
    92.         exit(-1);
    93.         struct node *p = phead;
    94.         struct node *test = NULL;
    95.         while(p->next != NULL)
    96.         {
    97.                 p = p->next;
    98.                 if(p->data == data)
    99.                 {
    100.                         if(p->next == NULL)
    101.                         {
    102.                                 p->prev->next = NULL;   //尾节点
    103.                         }
    104.                         else
    105.                         {
    106.                                 //其他节点
    107.                                 p->prev->next = p->next;
    108.                                 p->next->prev = p->prev;
    109.                         }
    110.                         free(p);
    111.                         (phead->data)--;
    112.                         return 0;
    113.                 }
    114.         }
    115.         printf("have no data\n");
    116.         return -1;
    117. }
    118.  
    119. int main()
    120. {
    121.         //创建头节点
    122.         struct node *head = create_node(0);
    123.  
    124.         //头部插入节点
    125.         insert_head(head,create_node(1));
    126.         insert_head(head,create_node(2));
    127.         insert_head(head,create_node(3));
    128.         insert_head(head,create_node(4));
    129.         insert_head(head,create_node(5));
    130.  
    131.         //尾部插入节点
    132.         insert_tail(head,create_node(1));
    133.         insert_tail(head,create_node(2));
    134.         insert_tail(head,create_node(3));
    135.         insert_tail(head,create_node(4));
    136.         insert_tail(head,create_node(5));
    137.  
    138.         //遍历节点
    139.         next_printf_link(head);
    140.  
    141.         //删除节点
    142.         delete_node(head,2);
    143.         delete_node(head,5);
    144.         delete_node(head,4);
    145.  
    146.         //next遍历节点
    147.         next_printf_link(head);
    148.  
    149.         //prev遍历节点
    150.         prev_printf_link(head);
    151.         return 0;
    152. }

    结果示例:

  • 相关阅读:
    ChatGPT突然上线APP！iPhone可用、速度更快，GPT-4用量限制疑似取消
    TikTok对文化艺术的影响：传统与现代的碰撞
    linux进阶55——service文件
    李m圆申论
    Vue2.0+Vue3.0复习
    企业级软件开发流程
    微信小程序隐藏滚动条的方法
    码农的转型之路-偶遇大佬情况或有变
    精选20个大模型高频面试题
    Windows 内网渗透之委派攻击
  • 原文地址：https://blog.csdn.net/tyro_wzp/article/details/133419655