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

用结构体实现单链表_结构体链表

作者：你好赵伟 | 2024-05-12 02:15:33

赞

踩

结构体链表

链表是指通过链式存储（使用任意不连续的内存空间）存放线性表中的数据元素，其中单链表由于一个结点只含一个指针域只能单向链接，故称单链表。

目录

前言

一、定义结构体

二、头插法

三、尾插法

四、任意结点插入（三种实现方法）

4.1.for循环插入

4.2.在已有链表中插入

4.3.（看代码）

五、删除任意结点

前言

1. 本篇文章通过自定义头插、尾插、任意结点插入、任意结点删除以及打印函数，来实现单链表。

2. 代码中的struct Node* tp1=new Node()（C++写法）也可写为struct Node* tp1=(Node*)malloc(sizeof(struct Node))（C语言写法）。

一、定义结构体

  1. #include"stdlib.h"
  2. #include"stdio.h"//头文件
  3.  
  4. /*malloc(m)函数，开辟m字节长度的地址空间，并返回这段空间的首地址
  5.   sizeof(x)运算，计算变量x的长度
  6.   free(p)函数，释放指针p所指变量的存储空间，即彻底删除一个变量
  7.   
  8. 需要加载头文件：<stdlib.h>*/
  9.  
  10. struct Node 
  11. {
  12. 	int data; 
  13. 	struct Node* next;
  14. };//结构体
  15.  
  16. struct Node* head;
  17. struct Node* last;//全局变量

二、头插法

该方法会将每次新接收到的数据都放在链表的最前面。

    struct Node* tp1=new Node();//（C++写法）也可以写成struct Node* tp1=(Node*)malloc(sizeof(struct Node))（C语言写法）
    tp1->data=x;
    tp1->next=head;
    head=tp1;

图解：

红色数字均为假定的地址

​

总代码如下：

  1. #include"stdlib.h"
  2. #include"stdio.h"
  3. struct Node 
  4. {
  5. 	int data; 
  6. 	struct Node* next;
  7. };
  8. struct Node* head;
  9. struct Node* last;
  10.  
  11. void Insert_1(int x)
  12. {
  13. 	struct Node* tp1=new Node();
  14.     tp1->data=x;
  15.     tp1->next=head;
  16.     head=tp1;
  17.  }//自定义头插入函数（Insert_1）
  18.  
  19. void Print()
  20. {
  21. 	struct Node* tp=head;
  22. 	printf("\n");//空一行
  23. 	printf("链表为：\n");
  24. 	while(tp!=NULL)
  25. 	{
  26. 		printf("%d ",tp->data);
  27. 		tp=tp->next;
  28. 	}
  29. }//自定义打印函数（Print）
  30.  
  31. int main()
  32. {
  33. 	head=NULL;
  34. 	int i,n,x;
  35. 	printf("请输入链表长度：\n");
  36. 	scanf("%d",&n);
  37. 	printf("\n");//空一行
  38. 	for(i=0;i<n;i++)
  39. 	{
  40. 		printf("请输入链表倒数第%d个元素：\n",i+1);
  41. 		scanf("%d",&x);
  42. 	    Insert_1(x);
  43. 	}
  44. 	Print();
  45. }

三、尾插法

该方法会将每次新接收到的数据都按输入顺序存放在链表里。

    struct Node* tp1=new Node();//（C++写法）也可以写成struct Node* tp1=(Node*)malloc(sizeof(struct Node))（C语言写法）
    if(head==NULL)
    {
    tp1->data=x;
    tp1->next=NULL;
    head=tp1;
    last=tp1;
    }
   else
   {  
       last->next=tp1;
       tp1->data=x;
       tp1->next=NULL;
       last=tp1;
    }

图解：

红色数字均为假定的地址

​

总代码如下：

  1. #include"stdlib.h"
  2. #include"stdio.h"
  3. struct Node 
  4. {
  5. 	int data; 
  6. 	struct Node* next;
  7. };
  8. struct Node* head;
  9. struct Node* last;
  10.  
  11. void Insert_2(int x)
  12. {
  13. 	
  14. 	struct Node* tp1=new Node();
  15. 	if(head==NULL)
  16. 	{
  17.     tp1->data=x;
  18.     tp1->next=NULL;
  19.     head=tp1;
  20. 	last=tp1;
  21.     }
  22.    else
  23.    {  
  24. 	   last->next=tp1;
  25.        tp1->data=x;
  26.        tp1->next=NULL;
  27.        last=tp1;
  28. 	}
  29.  }//自定义尾插入函数（Insert_2）
  30.  
  31. void Print()
  32. {
  33. 	struct Node* tp=head;
  34. 	printf("\n");//空一行
  35. 	printf("链表为：\n");
  36. 	while(tp!=NULL)
  37. 	{
  38. 		printf("%d ",tp->data);
  39. 		tp=tp->next;
  40. 	}
  41. }//自定义打印函数（Print）
  42.  
  43. int main()
  44. {
  45. 	head=NULL;
  46. 	int i,n,x;
  47. 	printf("请输入链表长度：\n");
  48. 	scanf("%d",&n);
  49. 	printf("\n");//空一行
  50. 	for(i=0;i<n;i++)
  51. 	{	
  52. 	    printf("请输入链表第%d个元素：\n",i+1);
  53. 	    scanf("%d",&x);
  54. 	    Insert_2(x);
  55.     }
  56. 		
  57. 	Print();
  58. }

四、任意结点插入（三种实现方法）

该代码可以实现在链表任意节点插入数据。

    struct Node* tp1=new Node();//（C++写法）也可以写成struct Node* tp1=(Node*)malloc(sizeof(struct Node))（C语言写法）
    tp1->data=data;
    tp1->next=NULL;
    if(n==1)
    {
        tp1->next=head;
        head=tp1;
    }
    else
    {
        struct Node* tp2=head;
        for(int i=0;i<n-2;i++)
        {
            tp2=tp2->next;
        }
        tp1->next=tp2->next;
        tp2->next=tp1;
    }

4.1.for循环插入

  1. #include"stdlib.h"
  2. #include"stdio.h"
  3. struct Node 
  4. {
  5. 	int data; 
  6. 	struct Node* next;
  7. };
  8. struct Node* head;
  9. struct Node* last;
  10.  
  11. void Insert_3(int data,int n)
  12. {
  13. 	struct Node* tp1=new Node();//或者struct Node* tp=(Node*)malloc(sizeof(struct Node))（创建一个节点）
  14.     tp1->data=data;
  15.     tp1->next=NULL;
  16.     if(n==1)
  17.     {
  18.     	tp1->next=head;
  19.     	head=tp1;
  20. 	}
  21.     else
  22.     {
  23.     	struct Node* tp2=head;
  24.     	for(int i=0;i<n-2;i++)
  25.     	{
  26.     		tp2=tp2->next;
  27. 		}
  28. 		tp1->next=tp2->next;
  29. 		tp2->next=tp1;
  30. 	}
  31.  }//自定义任意插入函数（Insert_3）
  32.  
  33. void Print()
  34. {
  35. 	struct Node* tp=head;
  36. 	printf("\n");//空一行
  37. 	printf("链表为：\n");
  38. 	while(tp!=NULL)
  39. 	{
  40. 		printf("%d ",tp->data);
  41. 		tp=tp->next;
  42. 	}
  43. }//自定义打印函数（Print）
  44.  
  45. int main()
  46. {
  47. 	head=NULL;
  48. 	int i,n,x,y,z;
  49. 	printf("请输入链表长度：\n");
  50. 	scanf("%d",&n);
  51. 	printf("\n");
  52. 	for(i=0;i<n;i++)
  53. 	{
  54. 		printf("请插入链表第%d个元素及位置(s)（1≤s≤%d,s∈N*）：\n",i+1,i+1);
  55. 		scanf("%d%d",&x,&y);
  56. 	    Insert_3(x,y);
  57. 	}
  58. 	Print();
  59. }

4.2.在已有链表中插入

  1. #include"stdlib.h"
  2. #include"stdio.h"
  3. struct Node 
  4. {
  5. 	int data; 
  6. 	struct Node* next;
  7. };
  8. struct Node* head;
  9. struct Node* last;
  10.  
  11. void Insert_2(int x)
  12. {
  13. 	
  14. 	struct Node* tp1=new Node();
  15. 	if(head==NULL)
  16. 	{
  17.     tp1->data=x;
  18.     tp1->next=NULL;
  19.     head=tp1;
  20. 	last=tp1;
  21.     }
  22.    else
  23.    {  
  24. 	   last->next=tp1;
  25.        tp1->data=x;
  26.        tp1->next=NULL;
  27.        last=tp1;
  28. 	}
  29.  }//自定义尾插入函数（Insert_2)
  30.  
  31. void Print()
  32. {
  33. 	struct Node* tp=head;
  34. 	printf("\n");//空一行
  35. 	printf("链表为：\n");
  36. 	while(tp!=NULL)
  37. 	{
  38. 		printf("%d ",tp->data);
  39. 		tp=tp->next;
  40. 	}
  41. }//自定义打印函数（Print）
  42. void Insert_3(int data,int n)
  43. {
  44. 	struct Node* tp1=new Node();//或者struct Node* tp=(Node*)malloc(sizeof(struct Node))（创建一个节点）
  45.     tp1->data=data;
  46.     tp1->next=NULL;
  47.     if(n==1)
  48.     {
  49.     	tp1->next=head;
  50.     	head=tp1;
  51. 	}
  52.     else
  53.     {
  54.     	struct Node* tp2=head;
  55.     	for(int i=0;i<n-2;i++)
  56.     	{
  57.     		tp2=tp2->next;
  58. 		}
  59. 		tp1->next=tp2->next;
  60. 		tp2->next=tp1;
  61. 	}
  62.  }//自定义任意插入函数（Insert_3）
  63.  
  64. int main()
  65. {
  66. 	head=NULL;
  67. 	int i,n,x,y,z;
  68. 	printf("请输入链表长度（不包括将要插入数据）：\n");
  69. 	scanf("%d",&n);
  70. 	printf("\n");//空一行
  71. 	for(i=0;i<n;i++)
  72. 	{	
  73. 	    printf("请输入链表第%d个元素：\n",i+1);
  74. 	    scanf("%d",&x);
  75. 	    Insert_2(x);
  76.     }
  77.     printf("请输入要插入链表的数据及位置：\n");
  78. 	scanf("%d%d",&x,&y);
  79. 	Insert_3(x,y);
  80. 	Print();
  81. }

4.3.（看代码）

  1. //前面的代码就不展示了
  2.  
  3. int main()
  4. {
  5. 	head=NULL;
  6. 	Insert_3(3,1);
  7. 	Insert_3(1,2);
  8. 	Insert_3(4,3);
  9. 	Print();
  10. }
  11.  
  12. //输出：3 1 4

五、删除任意结点

该代码可以实现删除链表中任意节点里的数据。

    struct Node* tp1=head;
    if(n==1)
    {
        head=tp1->next;
        free(tp1);
    }
    else
    {
        struct Node* tp2;
        int i;
        for(i=0;i<n-2;i++)
        {
            tp1=tp1->next;
        }
        tp2=tp1->next;
        tp1->next=tp2->next;
        free(tp2);
    }

总代码如下：

  1. #include"stdlib.h"
  2. #include"stdio.h"
  3. struct Node 
  4. {
  5. 	int data; 
  6. 	struct Node* next;
  7. };
  8. struct Node* head;
  9. struct Node* last;
  10.  
  11. void Delect(int n)
  12. {
  13. 	struct Node* tp1=head;
  14. 	if(n==1)
  15. 	{
  16. 		head=tp1->next;
  17. 		free(tp1);
  18. 	}
  19. 	else
  20. 	{
  21. 	    struct Node* tp2;
  22. 		int i;
  23. 		for(i=0;i<n-2;i++)
  24. 		{
  25. 			tp1=tp1->next;
  26. 		}
  27. 		tp2=tp1->next;
  28. 		tp1->next=tp2->next;
  29. 		free(tp2);	
  30. 	}
  31. }//自定义删除函数（Delect)
  32.  
  33. void Insert_2(int x)
  34. {
  35. 	
  36. 	struct Node* tp1=new Node();//或者struct Node* tp=(Node*)malloc(sizeof(struct Node))（创建一个节点）
  37. 	if(head==NULL)
  38. 	{
  39.     tp1->data=x;
  40.     tp1->next=NULL;
  41.     head=tp1;
  42. 	last=tp1;
  43.     
  44.     }
  45.    else
  46.    {  
  47. 	   last->next=tp1;
  48.        tp1->data=x;
  49.        tp1->next=NULL;
  50.        last=tp1;
  51. 	}
  52.  }//自定义尾插入函数（Insert_2）
  53.  
  54. void Print()
  55. {
  56. 	struct Node* tp=head;
  57. 	printf("\n");//空一行
  58. 	printf("链表为：\n");
  59. 	while(tp!=NULL)
  60. 	{
  61. 		printf("%d ",tp->data);
  62. 		tp=tp->next;
  63. 	}
  64. }//自定义打印函数（Print）
  65.  
  66. int main()
  67. {
  68. 	head=NULL;
  69. 	int i,n,x,y;
  70. 	printf("请输入链表长度：\n");
  71. 	scanf("%d",&n);
  72. 	printf("\n");//空一行
  73. 	for(i=0;i<n;i++)
  74. 	{
  75. 		 printf("请输入链表第%d个元素：\n",i+1);
  76. 		scanf("%d",&x);
  77. 	    Insert_2(x);
  78. 	}
  79. 	Print();
  80. 	printf("\n");//空一行
  81. 	printf("\n请输入需要删除链表元素的位置（s)：\n");
  82. 	scanf("%d",&y);
  83. 	Delect(y);
  84. 	Print();
  85. }

感谢各位大佬们的阅读，要是能再点个赞加个关注就更好了\^o^/

如有不妥的地方，请各位大佬移步评论区指正

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

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

  

闽ICP备14008679号