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

链表C语言实现--单向链表

作者：Li_阴宅 | 2024-08-08 00:10:02

赞

踩

链表C语言实现--单向链表

        线性结构的链式存储也称为链表，相比于顺序表，链表能够解决顺序表中空间资源浪费问题以及空间不足的问题。链表的每一个结点包含数据域和指针域，而每一个结点在内存中的地址是不连续的，且能适应动态变化。在数据插入和数据删除操作效率比顺序表高，但在数据查找和修改效率较低，需要遍历链表。

  链表又分为：

  • 有头链表，头节点不存数据，所以数据操作都从头节点所指的下一节点开始，就不会误操作到头节点。故更加常用。

  • 无头链表，第一个节点就存数据，但数据操作就要判断是否是头节点，不能对头节点操作，特别像删除操作就不能对头节点进行。

 本文采用有头链表，链表的每个结点的都用一个结构体表示，唯一特殊的就是头结点不存数据，只存指向下一个结点的指针。结构体定义如下：

  1. typedef int data_t;
  2. typedef struct linklist
  3. {
  4.     data_t data;//数据域
  5.     struct linklist *next;//指针域
  6. }LinkList;

首先编写头文件，将链表所涉及的增删改查操作都分别封装成模块

  1. /*===============================================
  2. *   文件名称：linklist.h
  3. *   创 建 者： x m    
  4. *   创建日期：2022年07月28日
  5. *   描    述：
  6. ================================================*/
  7. #ifndef _LINKLIST_
  8. #define _LINKLIST_
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11.  
  12. typedef int data_t;
  13. typedef struct linklist
  14. {
  15.     data_t data;//数据域
  16.     struct linklist *next;//指针域
  17. }LinkList;
  18.  
  19. //创建头节点
  20. LinkList *Creat_Linklist();
  21. //判空
  22. int Linklist_Is_Empty(LinkList *h_node);
  23. //求表长
  24. int Linklist_length(LinkList *h_node);
  25. //从表头插入数据
  26. void Linklist_Insert_head(LinkList *h_node,data_t data);
  27. //打印
  28. void Linklist_Show(LinkList *h_node);
  29. //按位置插入数据
  30. void Linklist_Insert_Pos(LinkList *h_node,int pos,data_t data);
  31.     
  32. //按位置删除
  33. void Linklist_Delete_Pos(LinkList *h_node,int pos);
  34. //按数据值删除
  35. void Linklist_Delete_Data(LinkList *h_node,data_t data);
  36. //按位置查找
  37. data_t Linklist_Search_Pos(LinkList *h_node,int pos);
  38. //按数据值查找
  39. int Linklist_Search_Data(LinkList *h_node,data_t data);
  40. //按位置修改
  41. void Linklist_Change_Pos(LinkList *h_node,int pos,data_t data);
  42. //按值修改
  43. void Linklist_Change_data(LinkList *h_node,data_t data,data_t newdata);
  44. //清空链表
  45. void Linklist_Empty(LinkList *h_node);
  46. //销毁链表
  47. void Linklist_Delete(LinkList **h_node);
  48. //循环头插10次
  49. void Test_Insert(LinkList *h_node);
  50.  
  51.  
  52.  
  53.  
  54. #endif

在模块文件内实现各个功能

1.创建头结点

头结点申请到空间后，因为其数据域不使用，默认-1就行，应为当前没有下一节点，所以指针域初始化为空NULL，然后返回头结点地址给其他模块和主函数使用。

  1. LinkList *Creat_Linklist()
  2. {
  3.     LinkList *head=(LinkList*)malloc(sizeof(LinkList));
  4.     if(NULL==head)
  5.     {
  6.         printf("malloc error!\n");
  7.         return NULL;
  8.     }
  9.     head->data=-1;
  10.     head->next=NULL;
  11.     return head;
  12. }

2.判空

即判断链表当前是否为空表，没有存储数据的结点。那就是判断头结点的下一节点是否为空

  1. int Linklist_Is_Empty(LinkList *h_node)
  2. {
  3.     if(h_node->next==NULL)return 0;//表空返回0
  4.     else return 1;
  5. }

3.求表长

表长指的是链表存储数据的结点个数，头结点不算。所以需要从第一个结点开始遍历链表，链表结点的偏移和顺序表不同，要想找到下一个结点，就得通过当前结点的指针域（next）指向下一个结点，直到下一个结点地址为NULL，结束遍历。

  1. int Linklist_length(LinkList *h_node)
  2. {
  3.     int len=0;
  4.     LinkList *p=h_node->next;//p指向头节点后的第一个节点
  5.     while(p!=NULL)
  6.     {
  7.         len++;
  8.        // printf("%d,",p->data);//打印数据
  9.         p=p->next;
  10.  
  11.     }
  12.     return len;
  13. }

4.头插法添加数据

从头结点后添加结点存储数据

 第一步是将新申请的结点的next指针指向原来头结点后的第一个结点，

第二步则是将头结点的next指针指向新节点

两步先后顺序不能反，如果反过来的话，会丢失原来第一个结点的地址，因为头结点next保存的地址被新节点地址所覆盖。

  1. void Linklist_Insert_head(LinkList *h_node,data_t data)
  2. {
  3.     LinkList *p=(LinkList *)malloc(sizeof(LinkList));
  4.     if(NULL==p)
  5.     {
  6.         printf("malloc new node error!\n");
  7.         return ;
  8.     }
  9.     p->data=data;//存数据
  10.  
  11.     p->next=h_node->next;//新节点拿到下一节点的地址
  12.     h_node->next=p; //上一节点刷新得到新节点的地址
  13. }

5.打印

即遍历链表，打印每个结点存的数据

  1. void Linklist_Show(LinkList *h_node)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空，无法打印\n");
  6.         return ;
  7.     }
  8.     LinkList *p=h_node->next;//p指向头节点后的第一个节点
  9.     while(p!=NULL)
  10.     {
  11.         printf("%d,",p->data);//打印数据
  12.         p=p->next;
  13.  
  14.     }
  15. }

6.按位置插入数据

这里的位置是从第一个存储数据的结点开始，我是从0开始计算位置，也就是第一个数据结点的位置为0，第二个数据结点的位置为1....这和数组存储数据的下标相似，所以我就按这种方式表达位置。

按位置插入和头插法有些区别，头插法是首先知道头结点的地址的，即函数参数传进来。而按位置插要根据传入的位置来找到要插入的结点的前一结点地址，

  1. void Linklist_Insert_Pos(LinkList *h_node,int pos,data_t data)
  2. {
  3.     LinkList * new=(LinkList*)malloc(sizeof(LinkList));
  4.     if(NULL==new)
  5.     {
  6.         printf("malloc new node error!\n");
  7.         return ;
  8.     }
  9.     LinkList *p=h_node;
  10.     if(pos<0 || pos>Linklist_length(p))
  11.     {
  12.         printf("pos errror!\n");
  13.         return ;
  14.     }
  15.     while(pos--)
  16.     {
  17.         p=p->next;
  18.     }
  19.  
  20.     new->data=data;
  21.  
  22.     new->next=p->next;
  23.     p->next=new;
  24.  
  25. }

 7.按位置删除

删除结点首先要找到其前一结点的位置并将其next指针指向要删除结点的下一结点地址，并释放删除结点的空间。

 例如上图，删除位置1的结点，则位置0结点的next指针指向位置2结点，但是这样为丢失位置1结点的地址，无法释放其空间。所以需要定义一个临时变量用来保存位置1的地址，在链表完成删除结点后，释放该结点空间。

  1. void Linklist_Delete_Pos(LinkList *h_node,int pos)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空，无法删除");
  6.         return ;
  7.     }
  8.     LinkList *p=h_node;
  9.     LinkList *q=NULL;
  10.     if(pos<0 || pos>=Linklist_length(p))
  11.     {
  12.         printf("pos errror!\n");
  13.         return ;
  14.     }
  15.     while(pos--)
  16.     {
  17.         p=p->next;
  18.     }
  19.     q=p->next;//q指向pos这个位置上的节点，用于后续删除
  20.    // p->next=p->next->next;//等价于下面这个语句
  21.     p->next=q->next;
  22.     free(q);
  23.     q=NULL;
  24. }

8.按数据删除结点

首先遍历链表，找到存储该数据的结点，然后删除该结点。删除结点的思路和按位置删除一样，找到要删除结点的前一结点地址即可。

  1. void Linklist_Delete_Data(LinkList *h_node,data_t data)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空，无法删除");
  6.         return ;
  7.     }
  8.     LinkList *p=h_node;//p用来指目标值节点的前一节点
  9.     LinkList *q=h_node->next;//q用来指向目标值所在节点
  10.     while(q!=NULL)
  11.     {
  12.         if(q->data==data)
  13.         {
  14.             p->next=q->next;
  15.             free(q);
  16.             q=NULL;
  17.             return ;
  18.         }
  19.         p=q;
  20.         q=q->next;
  21.     }
  22.     printf("未找到与该值相等的节点，无法删除\n");
  23.     return ;
  24.     
  25. }

9.按位置查找

从第一个结点遍历到目标结点位置，输出其数据即可

  1. data_t Linklist_Search_Pos(LinkList *h_node,int pos)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空");
  6.         return -1;
  7.     }
  8.     LinkList *p=h_node;
  9.     if(pos<0 || pos>=Linklist_length(p))
  10.     {
  11.         printf("pos errror!\n");
  12.         return -1;
  13.     }
  14.     while(pos--)
  15.     {
  16.         p=p->next;
  17.     }
  18.     return p->next->data;
  19.  
  20. }

10.按数据值查找

  1. int Linklist_Search_Data(LinkList *h_node,data_t data)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空\n");
  6.         return -1;
  7.     }
  8.     LinkList *p=h_node->next;
  9.     int pos=0;
  10.     while(p!=NULL)
  11.     {
  12.         if(p->data==data)
  13.         {
  14.             return pos;
  15.         }
  16.         p=p->next;
  17.         pos++;
  18.     }
  19.     printf("未找到与该值相等的节点\n");
  20.     return -1;
  21. }

11.按位置修改

思路和按位置查找一样，找到目标结点修改其数据值就行

  1. void Linklist_Change_Pos(LinkList *h_node,int pos,data_t data)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空");
  6.         return ;
  7.     }
  8.     LinkList *p=h_node->next;
  9.     if(pos<0 || pos>=Linklist_length(p))
  10.     {
  11.         printf("pos errror!\n");
  12.         return ;
  13.     }
  14.     while(pos--)
  15.     {
  16.         p=p->next;
  17.     }
  18.     p->data=data;
  19. }

12.按值修改

  1. void Linklist_Change_data(LinkList *h_node,data_t data,data_t newdata)
  2. {
  3.     if(Linklist_Is_Empty(h_node)==0)
  4.     {
  5.         printf("表为空\n");
  6.         return ;
  7.     }
  8.     LinkList *p=h_node->next;
  9.     while(p!=NULL)
  10.     {
  11.         if(p->data==data)
  12.         {
  13.             p->data=newdata;
  14.         }
  15.         p=p->next;
  16.     }
  17.     printf("未找到与该值相等的节点\n");
  18.     return ;
  19. }

13.清空链表

清空链表指删除所有存储数据的结点，最后只剩下头结点

  1. void Linklist_Empty(LinkList *h_node)
  2. {
  3.     LinkList *p=h_node->next;
  4.     int pos=Linklist_length(h_node)-1;
  5.     for(;pos>=0;pos--)
  6.     {
  7.         Linklist_Delete_Pos(h_node,pos);
  8.  
  9.     }
  10.     printf("清空完成\n");
  11.         
  12. }

14.销毁链表

即删除头结点，这里要注意除了释放头结点的空间，还要将指向头结点的指针置为NULL，不然其他函数调用该指针仍然会指向头结点空间，但此时头结点已经释放，再访问就会造成非法访问，程序可能出错。

所以传进函数的指向头结点的指针应当是该指针的地址，这样才能在函数能修改该指针的指向。

该指针本身就是指针变量，再取它的地址作为实参，则传入函数内的形参为二级指针。

  1. void Linklist_Delete(LinkList **h_node)//要想让对头节点地址进行操作，就得传其地址的地址
  2. {
  3.     if(Linklist_Is_Empty(*h_node)==0)
  4.     {
  5.         free(*h_node);
  6.         *h_node=NULL;
  7.         printf("销毁成功\n");
  8.         return;
  9.     }
  10.     printf("表不为空，无法销毁\n");
  11.  
  12. }

15.循环头插十次

主要是方便调试，每次都一个一个输入数据麻烦

  1. void Test_Insert(LinkList *h_node)
  2. {
  3.       int n=10;
  4.       while(n--)
  5.       {
  6.           Linklist_Insert_head(h_node,n);
  7.       }
  8.  
  9. }

主函数做了一个简易的功能选择界面，便于学习和调试

  1. /*===============================================
  2. *   文件名称：main.c
  3. *   创 建 者：xm     
  4. *   创建日期：2022年07月28日
  5. *   描    述：
  6. ================================================*/
  7. #include "linklist.h"
  8. int main(int argc, char *argv[])
  9. {
  10.     //构建交互界面
  11.     int mode;
  12.     LinkList *h_node;
  13.     int ret,pos,data;
  14.     while(1)
  15.     {
  16.         printf("--------------功能选择----------------\n");
  17.         printf("1.创建头节点 2.判断是否为空表 3.求表长（数据节点个数）4.从表头插入数据\n5.打印表 6.按位置插入数据 7.按位置删除 8.按值删除 9.按位置查找\n10.按值查找 11.按位置修改 12.按值修改\n13.清空链表 14.销毁链表 15.自动头插10个元素\n");
  18.         printf("请输入功能选项\n");
  19.         scanf("%d",&mode);
  20.         getchar();
  21.         switch(mode)
  22.         {
  23.             case 1:h_node=Creat_Linklist();
  24.                 break;
  25.             case 2:ret=Linklist_Is_Empty(h_node);
  26.                    if(ret==0)puts("空表");
  27.                    else puts("非空表");
  28.                 break;
  29.             case 3:ret= Linklist_length(h_node);
  30.                    printf("表长%d\n",ret);
  31.                 break;
  32.             case 4:printf("输入数据\n");
  33.                    scanf("%d",&data);
  34.                 Linklist_Insert_head(h_node,data);
  35.                 break;
  36.             case 5:Linklist_Show(h_node);
  37.                 break;
  38.             case 6:
  39.                     printf("输入位置和数据\n");
  40.                     scanf("%d%d",&pos,&data);
  41.                     Linklist_Insert_Pos(h_node,pos,data);
  42.                 break;
  43.             case 7:
  44.                     printf("输入位置\n");
  45.                     scanf("%d",&pos);
  46.                     Linklist_Delete_Pos(h_node,pos);
  47.                 break;
  48.             case 8:
  49.                     printf("输入值\n");
  50.                     scanf("%d",&data);
  51.                     Linklist_Delete_Data(h_node,data);
  52.                 break;
  53.             case 9:
  54.                     printf("输入位置\n");
  55.                     scanf("%d",&pos);
  56.                     Linklist_Search_Pos(h_node,pos);
  57.                     break;
  58.             case 10:
  59.                     printf("输入值\n");
  60.                     scanf("%d",&data);
  61.                     Linklist_Search_Data(h_node,data);
  62.                     break;
  63.             case 11:
  64.                     printf("输入位置和数据\n");
  65.                     scanf("%d%d",&pos,&data);
  66.                     Linklist_Change_Pos(h_node,pos,data);
  67.                     break;
  68.             case 12:
  69.                     printf("输入要改数据和新数据\n");
  70.                     scanf("%d%d",&data,&ret);
  71.                     Linklist_Change_data(h_node,data,ret);
  72.                     break;
  73.             case 13:
  74.                     Linklist_Empty(h_node);
  75.                     break;
  76.             case 14:
  77.                     Linklist_Delete(&h_node);
  78.                     break;
  79.             case 15:Test_Insert(h_node);
  80.                     break;
  81.             default:
  82.                     puts("输入错误\n");
  83.         }
  84.         puts("");
  85.     }
  86.     return 0;
  87. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Li_阴宅/article/detail/945125
推荐阅读
相关标签

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

  

闽ICP备14008679号