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

数据结构---单链表实现

作者：酷酷是懒虫 | 2024-08-19 21:59:50

赞

踩

数据结构---单链表实现

单链表是什么

我的理解是“特殊的数组”，通过访问地址来连接起来

1怎么创建链表 ----通过结构体（成员有存入数据的data和指向下一个节点的地址的指针（结构体指针）next

初始架构---DataType 对应存入数据类型，此处的Node==struct node *

  1. //头文件
  2. #include<stdio.h>
  3. //宏定义
  4. #define DataType int 
  5.  
  6. //全局变量
  7.  
  8. //结构体
  9. typedef struct node
  10. {
  11. 	DataType data;
  12. 	struct node* next;
  13. }node, * Node;
  14.  
  15. int main()
  16. {
  17.  
  18.  
  19. 	return 0;
  20. }

2初始化链表+尾插+打印

  1.  
  2.  
  3. Node Init(Node phead)
  4. {
  5. 	phead = (Node)malloc(sizeof(node));
  6. 	if (phead == -1)
  7. 		return -1;
  8. 	phead->next = NULL;
  9. }
  10.  
  11. int PushBack(Node phead, DataType num)
  12. {
  13. 	//创建新节点
  14. 	Node newnode = malloc(sizeof(node));
  15. 	newnode->next = NULL;
  16. 	newnode->data = num;
  17. 	//创建指针找到链表的尾，然后插入，
  18. 	Node p = NULL;
  19. 	//出来for循环就插入不用考虑链表为空因为for循环里面已经考虑判断了
  20. 	for (p = phead; p->next != NULL; p = p->next);
  21. 	p->next = newnode;
  22. 	return 0;
  23. }
  24.  
  25. void show_list(Node phead)
  26. {
  27. 	
  28. 	Node cur = NULL;
  29. 	cur = phead;
  30. 	//判断是否为空
  31. 	if (phead == NULL)
  32. 	{
  33. 		printf("NULL\n");
  34. 	}
  35. 	//遍历头节点没有数据所有从头节点下一个数据开始打印
  36. 	for (cur = phead->next; cur != NULL; cur = cur->next)
  37. 	{
  38. 		printf("%d->", cur->data);
  39. 	}
  40. 	printf("NULL\n");
  41. }
  42.

现象：

  1.  
  2. //头文件
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5.  
  6. //宏定义
  7. #define DataType int 
  8. //全局变量
  9.  
  10. //结构体
  11. typedef struct node
  12. {
  13. 	DataType data;
  14. 	struct node* next;
  15. }node, * Node;
  16.  
  17. Node Init(Node phead)
  18. {
  19. 	phead = (Node)malloc(sizeof(node));
  20. 	if (phead == -1)
  21. 		return -1;
  22. 	phead->next = NULL;
  23. }
  24.  
  25. int PushBack(Node phead, DataType num)
  26. {
  27. 	//创建新节点
  28. 	Node newnode = malloc(sizeof(node));
  29. 	newnode->next = NULL;
  30. 	newnode->data = num;
  31. 	//创建指针找到链表的尾，然后插入，
  32. 	Node p = NULL;
  33. 	//出来for循环就插入不用考虑链表为空因为for循环里面已经考虑判断了
  34. 	for (p = phead; p->next != NULL; p = p->next);
  35. 	p->next = newnode;
  36. 	return 0;
  37. }
  38.  
  39. void show_list(Node phead)
  40. {
  41. 	
  42. 	Node cur = NULL;
  43. 	cur = phead;
  44. 	//判断是否为空
  45. 	if (phead == NULL)
  46. 	{
  47. 		printf("NULL\n");
  48. 	}
  49. 	//遍历头节点没有数据所有从头节点下一个数据开始打印
  50. 	for (cur = phead->next; cur != NULL; cur = cur->next)
  51. 	{
  52. 		printf("%d->", cur->data);
  53. 	}
  54. 	printf("NULL\n");
  55. }
  56.  
  57. int main()
  58. {
  59. 	Node phead = NULL;
  60. 	phead = Init(phead);
  61. 	PushBack(phead, 1);
  62. 	PushBack(phead, 1);
  63. 	PushBack(phead, 1);
  64. 	PushBack(phead, 1);
  65. 	show_list(phead);
  66.  
  67. 	return 0;
  68. }

3添加删除和修改的功能 

删除时利用两个指针一个找一个删，再指向

修改就是在查找的基础上再加一个if判断

  1. #define _CRT_SECURE_NO_WARNINGS
  2. //头文件
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5.  
  6. //宏定义
  7. #define DataType int 
  8. //全局变量
  9.  
  10. //结构体
  11. typedef struct node
  12. {
  13. 	DataType data;
  14. 	struct node* next;
  15. }node, * Node;
  16.  
  17. Node Init(Node phead)
  18. {
  19. 	phead = (Node)malloc(sizeof(node));
  20. 	if (phead == NULL)
  21. 		return -1;
  22. 	phead->next = NULL;
  23. }
  24.  
  25. int PushBack(Node phead, DataType num)
  26. {
  27. 	//创建新节点
  28. 	Node newnode = malloc(sizeof(node));
  29. 	newnode->next = NULL;
  30. 	newnode->data = num;
  31. 	//创建指针找到链表的尾，然后插入，
  32. 	Node p = NULL;
  33. 	//出来for循环就插入不用考虑链表为空因为for循环里面已经考虑判断了
  34. 	for (p = phead; p->next != NULL; p = p->next);
  35. 	p->next = newnode;
  36. 	return 0;
  37. }
  38.  
  39. void show_list(Node phead)
  40. {
  41. 	
  42. 	Node cur = NULL;
  43. 	cur = phead;
  44. 	//判断是否为空
  45. 	if (phead == NULL)
  46. 	{
  47. 		printf("NULL\n");
  48. 	}
  49. 	//遍历头节点没有数据所有从头节点下一个数据开始打印
  50. 	for (cur = phead->next; cur != NULL; cur = cur->next)
  51. 	{
  52. 		printf("%d->", cur->data);
  53. 	}
  54. 	printf("NULL\n");
  55. }
  56. int Delect(Node phead,DataType num)
  57. {
  58. 	if (phead == NULL)
  59. 	{
  60. 		printf("peahd is NULL\n");
  61. 		return -1;
  62. 	}
  63. 	Node cur1= NULL;
  64. 	Node cur2 = NULL;
  65. 	for (cur1 = phead, cur2 = phead->next; cur1->next != NULL; cur1 = cur2, cur2 = cur2->next)
  66. 	{
  67. 		if (cur2->data == num)
  68. 		{
  69. 			cur1->next = cur2->next;
  70. 			free(cur2);
  71. 			return 0;
  72. 			}
  73. 	}
  74. 	printf("no find num\n");
  75. 	return -1;
  76. }
  77.  
  78. int Change(Node phead, int num1, int num2)
  79. {
  80. 	if (phead == NULL)
  81. 	{
  82. 		printf("peahd is NULL\n");
  83. 		return -1;
  84. 	}
  85. 	Node cur = NULL;
  86. 	for (cur = phead->next;cur != NULL; cur = cur->next)
  87. 	{
  88. 		if (cur->data == num1)
  89. 		{
  90. 			cur->data = num2;
  91. 			return 0;
  92. 		}
  93. 	}
  94. 	printf("no find num1\n");
  95. 	return -1;
  96. }
  97. int main()
  98. {
  99. 	Node phead = NULL;
  100. 	phead = Init(phead);
  101. 	PushBack(phead, 1);
  102. 	PushBack(phead, 1);
  103. 	PushBack(phead, 1);
  104. 	PushBack(phead, 1);
  105. 	Change(phead, 1, 2);
  106. 	show_list(phead);
  107. 	Delect(phead, 1);
  108. 	show_list(phead);
  109. 	Delect(phead, 1);
  110. 	Delect(phead, 1);
  111. 	Delect(phead, 1);
  112. 	show_list(phead);
  113. 	Delect(phead, 1);
  114. 	show_list(phead);
  115. 	Change(phead, 1, 2);
  116. 	show_list(phead);
  117.  
  118. 	return 0;
  119. }

4释放---释放后链表为空，不会显示后面功能

  1.  
  2. void Releas(Node phead)
  3. {
  4. 	Node cur1 = NULL;
  5. 	Node cur2 = NULL;
  6. 	for (cur1 = cur2 = phead; cur1->next != NULL; cur1 = cur2)
  7. 	{
  8. 		cur2 = cur1->next;
  9. 		free(cur1);
  10. 	}
  11. }
  12. int main()
  13. {
  14. 	Node phead = NULL;
  15. 	phead = Init(phead);
  16. 	PushBack(phead, 1);
  17. 	PushBack(phead, 1);
  18. 	PushBack(phead, 1);
  19. 	PushBack(phead, 1);
  20. 	Change(phead, 1, 2);
  21. 	Releas(phead);
  22. 	show_list(phead);
  23. 	Delect(phead, 1);
  24. 	show_list(phead);
  25. 	Delect(phead, 1);
  26. 	Delect(phead, 1);
  27. 	Delect(phead, 1);
  28. 	show_list(phead);
  29. 	Delect(phead, 1);
  30. 	show_list(phead);
  31. 	Change(phead, 1, 2);
  32. 	show_list(phead);
  33.  
  34. 	return 0;
  35. }

5最终代码---链表实现方法有很多掌握自己熟练的解决问题才是关键

  1. #define _CRT_SECURE_NO_WARNINGS
  2. //头文件
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5.  
  6. //宏定义
  7. #define DataType int 
  8. //全局变量
  9.  
  10. //结构体
  11. typedef struct node
  12. {
  13. 	DataType data;
  14. 	struct node* next;
  15. }node, * Node;
  16.  
  17. Node Init(Node phead)
  18. {
  19. 	phead = (Node)malloc(sizeof(node));
  20. 	if (phead == NULL)
  21. 		return -1;
  22. 	phead->next = NULL;
  23. }
  24.  
  25. int PushBack(Node phead, DataType num)
  26. {
  27. 	//创建新节点
  28. 	Node newnode = malloc(sizeof(node));
  29. 	newnode->next = NULL;
  30. 	newnode->data = num;
  31. 	//创建指针找到链表的尾，然后插入，
  32. 	Node p = NULL;
  33. 	//出来for循环就插入不用考虑链表为空因为for循环里面已经考虑判断了
  34. 	for (p = phead; p->next != NULL; p = p->next);
  35. 	p->next = newnode;
  36. 	return 0;
  37. }
  38.  
  39. void show_list(Node phead)
  40. {
  41. 	
  42. 	Node cur = NULL;
  43. 	cur = phead;
  44. 	//判断是否为空
  45. 	if (phead == NULL)
  46. 	{
  47. 		printf("NULL\n");
  48. 	}
  49. 	//遍历头节点没有数据所有从头节点下一个数据开始打印
  50. 	for (cur = phead->next; cur != NULL; cur = cur->next)
  51. 	{
  52. 		printf("%d->", cur->data);
  53. 	}
  54. 	printf("NULL\n");
  55. }
  56. int Delect(Node phead,DataType num)
  57. {
  58. 	if (phead == NULL)
  59. 	{
  60. 		printf("peahd is NULL\n");
  61. 		return -1;
  62. 	}
  63. 	Node cur1= NULL;
  64. 	Node cur2 = NULL;
  65. 	for (cur1 = phead, cur2 = phead->next; cur1->next != NULL; cur1 = cur2, cur2 = cur2->next)
  66. 	{
  67. 		if (cur2->data == num)
  68. 		{
  69. 			cur1->next = cur2->next;
  70. 			free(cur2);
  71. 			return 0;
  72. 			}
  73. 	}
  74. 	printf("no find num\n");
  75. 	return -1;
  76. }
  77.  
  78. int Change(Node phead, int num1, int num2)
  79. {
  80. 	if (phead == NULL)
  81. 	{
  82. 		printf("peahd is NULL\n");
  83. 		return -1;
  84. 	}
  85. 	Node cur = NULL;
  86. 	for (cur = phead->next;cur != NULL; cur = cur->next)
  87. 	{
  88. 		if (cur->data == num1)
  89. 		{
  90. 			cur->data = num2;
  91. 			return 0;
  92. 		}
  93. 	}
  94. 	printf("no find num1\n");
  95. 	return -1;
  96. }
  97. void Releas(Node phead)
  98. {
  99. 	Node cur1 = NULL;
  100. 	Node cur2 = NULL;
  101. 	for (cur1 = cur2 = phead; cur1->next != NULL; cur1 = cur2)
  102. 	{
  103. 		cur2 = cur1->next;
  104. 		free(cur1);
  105. 	}
  106. }
  107. int main()
  108. {
  109. 	Node phead = NULL;
  110. 	phead = Init(phead);
  111. 	PushBack(phead, 1);
  112. 	PushBack(phead, 1);
  113. 	PushBack(phead, 1);
  114. 	PushBack(phead, 1);
  115. 	Change(phead, 1, 2);
  116. 	Releas(phead);
  117. 	show_list(phead);
  118. 	Delect(phead, 1);
  119. 	show_list(phead);
  120. 	Delect(phead, 1);
  121. 	Delect(phead, 1);
  122. 	Delect(phead, 1);
  123. 	show_list(phead);
  124. 	Delect(phead, 1);
  125. 	show_list(phead);
  126. 	Change(phead, 1, 2);
  127. 	show_list(phead);
  128.  
  129. 	return 0;
  130. }

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

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

  

闽ICP备14008679号