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

C语言—链表_c语言链表

作者：不正经 | 2024-05-12 02:26:06

赞

踩

c语言链表

文章目录

一，链表的概念

二，静态创建链表和动态遍历

 三，统计链表节点个数及链表查找

 四，链表的插入

1，从指定节点后方插入新节点

2，从指定节点前方插入新节点 

五，链表删除指定节点

六，动态创建链表

           1，头插法：

           2，尾插法：

一，链表的概念

1，什么是链表？

链表是一种数据结构，是一种数据存放的思想；
2，链表和数组的区别

数组的特点：

  • 数组中的每一个元素都属于同一数据类型的；
  • 数组是一组有序数据的集合；
  • 数组是在内存中开辟一段连续的地址空间用来存放一组数据，可以用数组名加下标来访问数组中的元素； 

链表的特点：               

  • 动态地进行存储分配的一种结构；
  • 链表中的各节点在内存中的地址都是不连续的；
  • 链表是由一个个节点组成，像一条链子一样；
  • 链表中的节点一般包括两个部分（1）用户要用的数据（2）下一个节点的地址；

*两者对比：

  •  一个数组只能存放同一种类型的数据，而链表中就可以存放不同的数据类型；
  • 数组中的元素地址是连续的，想删除或添加一个新的元素，十分的麻烦不灵活，而且用数组存放数据是都要先定义好数组的大小(即元素的个数)，如果在定义数组时，定义小了，内存不够用，定义大了，显然会浪费内存；而链表就可以很好的解决这些问题，链表中每一项都是一个结构体，链表中各节点在内存中的地址可以是不连续的，所以你想删除或添加一个新的节点很简单和方便，直接把节点中存放的的地址拿去修改就ok了(具体怎么添加或删除放在后用代码详细讲)，因为链表是一种动态结构，所以链表在建立的时候并不用像数组一样需要提前定义大小和位置(具体怎么创建也放在后面用代码详细讲)。

二，静态创建链表和动态遍历

  1.  
  2. #include<stdio.h>
  3.  
  4. struct Test//声明结构体类型
  5. {
  6. 	int data;//定义数据域
  7. 	struct Test *next;//定义指针域
  8. };
  9.  
  10. //遍历链表
  11. void printLink(struct Test *head)
  12. {
  13.     struct Test *p = head;//使p指向链表头
  14.  
  15. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时，循环结束
  16. 		printf("%d ",p->data);//输出当前节点中data的值
  17. 		p = p->next;//使p指向下一个节点
  18. 	}
  19.     printf("\n");
  20. }
  21.  
  22. int main()
  23. {
  24.     struct Test* head;
  25.     //定义结构体变量，作为节点，给节点赋值
  26. 	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
  27. 	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
  28. 	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
  29. 	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
  30. 	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
  31. 	
  32.     head = &t1;//将节点t1的起始地址赋给头指针head
  33. 	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
  34. 	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
  35. 	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
  36. 	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
  37. 	
  38. 	printLink(head);//把链表头传到函数printLink中
  39. 	
  40. 	return 0;
  41. }

 三，统计链表节点个数及链表查找

  1.  
  2. #include<stdio.h>
  3.  
  4. struct Test//声明结构体类型
  5. {
  6. 	int data;//定义数据域
  7. 	struct Test *next;//定义指针域
  8. };
  9.  
  10. //遍历链表
  11. void printLink(struct Test *head)
  12. {
  13.     struct Test *p = head;//使p指向链表头
  14.  
  15. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时，循环停止
  16. 		printf("%d ",p->data);//输出当前节点中data的值
  17. 		p = p->next;//使p指向下一个节点
  18. 	}
  19. }
  20.  
  21. //统计节点的个数
  22. int getNodeSum(struct Test *head)
  23. {
  24. 	int sum = 0;
  25. 	struct Test *p = head;//使p指向链表头
  26. 	
  27. 	 while(p != NULL){//遍历链表,直到链表尾NULL时停止
  28. 		sum++;//统计链表节点的个数
  29. 		p = p->next;//使p指向下一个节点
  30. 	}
  31. 	return sum;//把统计的节点的个数return回去
  32. }
  33.  
  34. //链表查询
  35. int searchLink(struct Test *head,int  n)
  36. {
  37. 	while(head != NULL){//遍历链表，直到链表尾NULL时停止
  38. 		if(head->data == n){//判断当前节点中的data(数据域)和要查询的是否相同
  39. 			return 1;//相同的话return 1
  40. 		}
  41. 		head = head->next;//使head指向下一个节点
  42. 	}
  43. 	return 0;//不相同return 0
  44. }
  45.  
  46. int main()
  47. {
  48. 	int ret;
  49.     struct Test* head;
  50.     //定义结构体变量，作为节点，给节点赋值
  51. 	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
  52. 	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
  53. 	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
  54. 	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
  55. 	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
  56. 	
  57.     head = &t1;//将节点t1的起始地址赋给头指针head
  58. 	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
  59. 	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
  60. 	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
  61. 	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
  62. 	
  63. 	printLink(head);//把链表头传到函数printLink中
  64. 	
  65. 	ret = getNodeSum(head);
  66. 	printf("此链表一共有%d个节点\n",ret);
  67. 	
  68. 	ret = searchLink(head,2);
  69. 	if(ret == 1){//判断return回来的值
  70. 	    printf("有1这个节点\n");
  71. 	}
  72. 	else{
  73. 		printf("没有1这个节点\n");
  74. 	}
  75. 	
  76. 	ret = searchLink(head,7);
  77. 	if(ret == 1){//判断return回来的值
  78. 	    printf("有7这个节点\n");
  79. 	}
  80. 	else{
  81. 		printf("没有7这个节点\n");
  82. 	}
  83. 	
  84. 	return 0;
  85. }

 四，链表的插入

插入一个新节点有两种方法：        

  1.  在指定节点后
  2.  在指定节点前

1，从指定节点后方插入新节点

找到指定节点,把新节点节点的下一个节点放在要新节点的next(指针域)中,再把新节点放在指定节点的next(指针域)中

  1. #include<stdio.h>
  2.  
  3. struct Test//声明结构体类型
  4. {
  5. 	int data;//定义数据域
  6. 	struct Test *next;//定义指针域
  7. };
  8.  
  9. //遍历链表
  10. void printLink(struct Test *head)
  11. {
  12.     struct Test *p = head;
  13.  
  14. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
  15. 		printf("%d ",p->data);//输出p节点中data的值
  16. 		p = p->next;//使p指向下一节点
  17. 	}
  18. 	printf("\n");
  19. }
  20.  
  21. //从指定节点后方插入新节点
  22. void insertFromBehind(struct Test *head,int n,struct Test *new)
  23. {
  24. 	struct Test *p = head;
  25. 	while(p != NULL){
  26. 		if(p->data == n){//判断当前节点是不是指定节点
  27. 			new->next = p->next;//把新节点的next(指针域)指向指定节点的下一个节点(这边要注意顺序不能换，否则链表会断掉)
  28. 			p->next = new;//再把指定节点的next(指针域)指向新节点
  29. 		}
  30. 		p = p->next;//使p指向下一节点
  31. 	}
  32. }
  33.  
  34. int main()
  35. {
  36. 	struct Test* head;
  37.     //定义结构体变量，作为节点，给节点赋值
  38. 	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
  39. 	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
  40. 	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
  41. 	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
  42. 	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
  43. 	
  44.     head = &t1;//将节点t1的起始地址赋给头指针head
  45. 	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
  46. 	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
  47. 	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
  48. 	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
  49. 	
  50. 	printLink(head);//把链表头传到函数printLink中
  51. 	
  52. 	struct Test new = {100,NULL};//定义一个新节点
  53. 	
  54. 	insertFromBehind(head,5,&new);//把链表头,要插入的位置,和新节点的地址传过去
  55. 	printLink(head);//把链表头传过去,打印链表
  56. 	
  57. 	
  58. 	return 0;
  59. }

2，从指定节点前方插入新节点 

要考虑两种情况：

  1. 在第一个节点前插入；
  2. 在中间节点插入；

  1. #include<stdio.h>
  2.  
  3. struct Test//声明结构体类型
  4. {
  5. 	int data;//定义数据域
  6. 	struct Test *next;//定义指针域
  7. };
  8.  
  9. //遍历链表
  10. void printLink(struct Test *head)
  11. {
  12.     struct Test *p = head;
  13.  
  14. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
  15. 		printf("%d ",p->data);//输出p节点中data的值
  16. 		p = p->next;//使p指向下一节点
  17. 	}
  18. 	printf("\n");
  19. }
  20.  
  21. //从指定节点前方插入新节点
  22. struct Test* insertFromfront(struct Test *head,int data,struct Test *new)
  23. {
  24. 	struct Test* p = head;
  25. 	//在头节点插入(链表头会改变)
  26. 	if(p->data == data){//判断指定的节点是不是头节点
  27. 	    new->next = p;//让新节点的next(指针域)指向p
  28. 		return new;//现在new成为新的链表头了
  29. 	}
  30. 	//在中间节点插入
  31. 	while(p->next != NULL){//因为这里是从中间节点插入，所以会从第二个节点开始遍历链表,直到链表尾NULL时停止
  32. 		if(p->next->data == data){//判断当前节点是不是指定节点
  33. 			new->next = p->next;//让要插入节点的next(指针域)指向p->next(就是当前节点的下一个节点)
  34. 			p->next = new;//在让当前节点next(指针域)指向要插入的节点new
  35. 			return head;//再把链表头给return回去
  36. 		}
  37. 		p = p->next;//使p指向下一节点
  38. 	}
  39. 	return head;
  40. }
  41.  
  42. int main()
  43. { 
  44. 	struct Test* head;
  45.     //定义结构体变量，作为节点，给节点赋值
  46. 	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
  47. 	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
  48. 	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
  49. 	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
  50. 	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
  51. 	
  52.     head = &t1;//将节点t1的起始地址赋给头指针head
  53. 	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
  54. 	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
  55. 	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
  56. 	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
  57. 	
  58. 	printLink(head);//将头指针的地址传到函数printLink中
  59. 	
  60. 	struct Test new = {100,NULL};//定义一个新节点
  61. 	
  62. 	
  63. 	head = insertFromfront(head,5,&new);//把链表头,要插入的位置,和新节点的地址传过去
  64. 	printLink(head);//把链表头传过去,打印链表
  65. 	
  66. 	return 0;
  67. }

五，链表删除指定节点

要考虑两种情况：

  1. 判断删除的节点是不是第一个节点，如果是第一个节点，直接改链表头，让第二个节点成为新的链表头
  2. 删除的节点如果非第一个节点的话：把要删除节点的前一个节点的next(指针域)越过要删除的节点，然后指向要删除节点的下一个节点；

*注意如果链表是动态创建的记得把删除的这个节点给free掉

  1. #include<stdio.h>
  2.  
  3. struct Test//声明结构体类型
  4. {
  5. 	int data;//定义数据域
  6. 	struct Test *next;//定义指针域
  7. };
  8.  
  9. //遍历链表
  10. void printLink(struct Test *head)
  11. {
  12.     struct Test *p = head;
  13.  
  14. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
  15. 		printf("%d ",p->data);//输出p节点中data的值
  16. 		p = p->next;//使p指向下一节点
  17. 	}
  18. 	printf("\n");
  19. }
  20.  
  21. //删除指定节点
  22. struct Test* deleteNode(struct Test *head,int data)
  23. {
  24. 	struct Test* p = head;
  25. 	//删除第一个节点
  26. 	if(p->data == data){//判断要删除的节点是不是头节点
  27. 	    head = head->next;//让p指向下一个节点
  28. 		return head;//把新的链表头传回去
  29. 	}
  30. 	//删除非第一个节点
  31. 	while(p->next != NULL){//从第二个节点开始遍历链表
  32. 		if(p->next->data == data){//判断当前节点是不是要删除的节点
  33. 			p->next = p->next->next;//把要删除节点的前一个节点的next(指针域)越过要删除的节点，然后指向要删除节点的下一个节点
  34. 			return head;//把链表头传回去
  35. 		}
  36. 		p = p->next;//使p指向下一节点
  37. 	}
  38. 	return head;
  39. }
  40.  
  41. int main()
  42. { 
  43. 	struct Test* head;
  44.     //定义结构体变量，作为节点，给节点赋值
  45. 	struct Test t1 = {1,NULL};//对节点t1的data和next赋值
  46. 	struct Test t2 = {2,NULL};//对节点t2的data和next赋值
  47. 	struct Test t3 = {3,NULL};//对节点t3的data和next赋值
  48. 	struct Test t4 = {4,NULL};//对节点t4的data和next赋值
  49. 	struct Test t5 = {5,NULL};//对节点t5的data和next赋值
  50. 	
  51.     head = &t1;//将节点t1的起始地址赋给头指针head
  52. 	t1.next = &t2;//将节点t2的起始地址赋给t1节点中的next
  53. 	t2.next = &t3;//将节点t3的起始地址赋给t2节点中的next
  54. 	t3.next = &t4;//将节点t4的起始地址赋给t3节点中的next
  55. 	t4.next = &t5;//将节点t5的起始地址赋给t4节点中的next
  56. 	
  57. 	printLink(head);//将头指针的地址传到函数printLink中
  58. 	printf("删除指定节点后的链表：\n");
  59. 	head = deleteNode(head,5);//把链表头，和要删除第几个节点传过去
  60. 	printLink(head);//把链表头传过去,打印链表
  61. 	
  62. 	return 0;
  63. }

六，动态创建链表

动态创建链表也是有两种方法：

1，头插法：

每一次创建的新节点插在之前的链表头之前，再让新节点做为新的链表头；

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. struct Test//声明结构体类型
  5. {
  6. 	int data;//定义数据域
  7. 	struct Test *next;//定义指针域
  8. };
  9.  
  10. //遍历链表
  11. void printLink(struct Test *head)
  12. {
  13.     struct Test *p = head;
  14.  
  15. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
  16. 		printf("%d ",p->data);//输出p节点中data的值
  17. 		p = p->next;//使p指向下一节点
  18. 	}
  19. 	printf("\n");
  20. }
  21.  
  22. struct Test* insertFromHead(struct Test* head,struct Test* new)
  23. {
  24. 	
  25. 	if(head == NULL){//判断链表是否为空
  26. 		head = new;//如果为空把创建的新节点当作链表头
  27. 	}else{
  28. 		new->next = head;//当链表不为空的时候，让新节点插在链表头的前面(称之为头插法)
  29. 		head = new;//再让新节点成为链表头
  30. 	}
  31. 	return head;
  32. }
  33.  
  34. //动态创建链表(头插法)
  35. struct Test* creatLink(struct Test* head)
  36. {
  37. 	struct Test* new;
  38. 	while(1){
  39. 		new = (struct Test*)malloc(sizeof(struct Test));//开辟空间
  40. 		new->next = NULL;
  41. 		printf("input your ne node data:\n");
  42. 		scanf("%d",&(new->data));//输入节点的数据域(data)
  43. 	    if(new->data == 0){//判断每次输入的值是否为0，如果为0，停止创建新节点
  44. 		    printf("0 quit\n");
  45. 			return head;
  46. 		}
  47. 		head = insertFromHead(head,new);
  48.     }	
  49. 	return head;
  50. }
  51.  
  52. int main()
  53. {
  54. 	struct Test* head = NULL;
  55.     head = creatLink(head);	
  56. 	printLink(head);
  57. 	
  58. 	return 0;
  59. }

2，尾插法：

如果链表为空，创建的第一个节点做为链表头，然后每一次创建的新节点插在链表最后一个节点的指针域(next)中；

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3.  
  4. struct Test//声明结构体类型
  5. {
  6. 	int data;//定义数据域
  7. 	struct Test *next;//定义指针域
  8. };
  9.  
  10. //遍历链表
  11. void printLink(struct Test *head)
  12. {
  13.     struct Test *p = head;
  14.  
  15. 	while(p != NULL){//p现在是链表头,会一直遍历链表尾NULL时停止
  16. 		printf("%d ",p->data);//输出p节点中data的值
  17. 		p = p->next;//使p指向下一节点
  18. 	}
  19. 	printf("\n");
  20. }
  21.  
  22. struct Test* insertBehind(struct Test* head,struct Test* new)
  23. {
  24. 	struct Test* p = head;
  25. 	
  26. 	if(p == NULL){//判断链表是否为空
  27. 		return head = new;//如果为空把创建的新节点当作链表头
  28. 	}
  29. 	while(p->next != NULL){//遍历到最后一个节点
  30. 		p = p->next;//使p指向下一节点
  31. 	}
  32. 	p->next = new;//把新节点插入最后一个节点的指针域(next)中
  33. 	return head;//把链表头传回去
  34. }
  35.  
  36. //动态创建链表(尾插法)
  37. struct Test* creatLink(struct Test* head)
  38. {
  39. 	struct Test* new;
  40. 	while(1){
  41. 		new = (struct Test*)malloc(sizeof(struct Test));//开辟空间
  42. 		new->next = NULL;
  43. 		printf("input your ne node data:\n");
  44. 		scanf("%d",&(new->data));//输入节点的数据域(data)
  45. 	    if(new->data == 0){//判断每次输入的值是否为0，如果为0，停止创建新节点
  46. 		    printf("0 quit\n");
  47. 			return head;
  48. 		}
  49. 		head = insertBehind(head,new);
  50. 	}
  51. }
  52.  
  53. int main()
  54. {
  55. 	struct Test* head = NULL;
  56. 	head = creatLink(head);
  57. 	printLink(head);
  58. 	
  59. }

写在最后：

博主是一位在校中专生，刚学不久，实力有限，内容仅供参考，有不对地方欢迎大神指出，一起讨论，一起进步

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

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

  

闽ICP备14008679号