C语言实现常用数据结构：带头结点的单链表（第3篇）

﹏ヽ暗。殇╰゛Y 2022-11-24 14:18 71阅读 0赞

# 单链表 #

单链表使用指针来保存线性表数据元素的关系。

实现要点：

1.使用指针来指向下一个数据元素。

2.单链表分为带头结点的单链表、不带头结点的单链表。

3.使用带头结点的单链表不需要对空表进行特殊处理，简化操作。

优缺点和适用场景：

适用于进行大量插入、删除操作的场景，不具备随机存取的特性，访问数据必须循环遍历。

# 使用示例 #

功能：输入数据个数和数据，逆序保存到顺序表，并逆序输出显示到屏幕。

运行结果如下：

请输入数据总个数:10

请依次输入10个整数:0 1 2 3 4 5 6 7 8 9

单链表输出结果:9 8 7 6 5 4 3 2 1 0

单链表删除5位置数据后输出结果:9 8 7 6 4 3 2 1 0

# 代码实现：带头点的单链表 #

*/
    #include <stdio.h>
    #include <stdlib.h>
    
    
    // 定义单链表数据结构 
    typedef struct list_node
    {
      int data;
      struct list_node *next;
    }list_node;
    
    
    // 创建和初始化空链表 
    list_node *create_link_list()
    {
      // 创建头节点 
      list_node *head = (list_node *)malloc(sizeof(list_node));
      // 头结点的data域保存长度
      if(head == NULL)
        return NULL;
      head->data = 0;
      head->next = NULL;
      return head; 
    }
    
    
    // 增加
    int insert_link_list(list_node *list, int data ,int pos)
    {
      if(list == NULL || pos < 1 || pos > list->data+1)
        return -1;
      list_node *node = (list_node *)malloc(sizeof(list_node));
      if(node == NULL)
        return -1;
      node->data = data;
      node->next = NULL;
      // 循环找到插入的位置 
      int i;
      list_node *p = list;
      for(i=0; i<pos-1; i++)
        p = p->next;
      node->next = p->next;
      p->next = node;
      list->data++;
      return 0;
    }
    
    
    // 删除 
    int delete_link_list(list_node *list, int *data, int pos)
    {
      if(list==NULL || pos < 1 || pos > list->data)
        return -1;
      
      // 循环找到要删除的元素前一个位置
      int i;
      list_node *p = list;
      for(i=0; i<pos-1; i++)
        p = p->next;
      
      list_node *q = p->next;
      *data = q->data;
      p->next = q->next;
      free(q);
      list->data--;
      return 0;  
    }
    
    
    // 查看 
    void print_link_list(list_node *list)
    {
      if(list != NULL)
      {
        list_node *p = list;
        while((p=p->next) != NULL)
          printf("%d ", p->data);
        printf("\n");
      }
     } 
     
     // 销毁
    void free_link_list(list_node *list)
    {
       if(list != NULL)
       {
         list_node *p = NULL;
         while((p=list->next) != NULL)
         {
           list->next = p->next;
          free(p); 
        }
        free(list);
      }
    }
    
    
    int main(void)
    {
      list_node *list = create_link_list(); 
        
      int n,d;
      printf("请输入数据总个数:");
      scanf("%d", &n);
      printf("请依次输入%d个整数:", n);
      int i;
      for(i=0; i<n; i++)
      {
        scanf("%d", &d);
        // 每次插入到链表首位，这样实现倒序 
        insert_link_list(list, d, 1); 
      }  
      printf("单链表输出结果:");
      print_link_list(list); 
      
      printf("单链表删除%d位置数据后输出结果:",n/2);
      delete_link_list(list, &d, n/2);
      
      print_link_list(list); 
      free_link_list(list);
      
      return 0;
    }

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。  
![format_png][]  
![format_png 1][]

[format_png]: /images/20221124/7959f6121d6643ceaf019a65d754050e.png
[format_png 1]: /images/20221124/ac3346b37ab942cf9127c96069fea406.png