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

C语言实现链表基本操作_c语言链表的基本操作

作者：我家自动化 | 2024-04-22 21:24:44

赞

踩

c语言链表的基本操作

目录

一、什么是链表

二、为什么要使用链表

三、链表相关知识

四、链表实现

1.定义结构体

2.创建链表

3.遍历链表

4.判断链表是否为空

5.计算链表长度

6.插入一个数据

7.删除数据

8.全部代码

一、什么是链表

如果把数据比喻成珠子，指针就是线，链表通过指针这条线就是把数据这些珠子串起来。

二、为什么要使用链表

数组是我们接触c语言时学到的一种重要的数据存储方式，是连续的，可以快速查找某个位置的数据。都是要对数组实现删除和插入等功能时，需要移动大量的数据，耗时长。而且数组使用前就分配好内存，分配的内存过小可能不够用，过大就造成浪费。

而链表实现对数据删除和插入的功能时具有优势，而且可以要用时才分配，可以说基本不存在内存不足和浪费的情况。链表分配内存时一小块一小块的，数组则是连续的一大块。假如我们要存储学生的成绩，那就要一个学生的姓名，学号，课程名字，课程成绩等等，假定一个学生要二十字节的空间，一个学院五千人，那就要10万字节。如果你硬要用数组存储，你得找到一块连续的10万字节的空间，很难吧。用链表就不需要，一块连续且这么大的空间。

三、链表相关知识

头结点：单链表的第一个结点，头结点的数据域不存储信息，指针域指向第一个有效结点即首结点。头结点的作用是使所有链表（包括空表）的头指针非空，其实头结点的作用是为了方便操作。

首结点：存放第一个有效数据的节点。

头指针：指向头节点的指针。

尾节点：存放最后一个有效数据的节点。

尾指针：指向尾节点的指针。

四、链表实现

1.定义结构体

  1. typedef struct Node
  2. {
  3. 	Elemtype data;//数据域
  4. 	struct Node* pNext;//指针域
  5.  
  6. }NODE, * PNODE;//NODE相当于struct Node，* PNODE相当于struct Node *

结构体大同小异，主要分为数据域和指针域。看需求修改数据域，比如你存放学生成绩，那就多定义一些数据类型就好。

2.创建链表

  1. PNODE create_list()//创建链表
  2. {
  3. 	int length, value;
  4.  
  5. 	PNODE pHead = (PNODE)malloc(sizeof(NODE));//分配头结点
  6. 	if (NULL == pHead)
  7. 	{
  8. 		printf("分配内存失败，程序结束！\n");
  9. 		exit(-1);
  10. 	}
  11. 	PNODE pTail = pHead;//尾结点，每次增加结点时，尾结点跟着后移
  12. 	pTail->pNext = NULL;
  13.  
  14. 	printf("链表结点个数：");
  15. 	scanf("%d", &length);
  16. 	for (int i = 0; i < length; i++)
  17. 	{
  18. 		printf("输入第%d个结点的值：", i + 1);
  19. 		scanf("%d", &value);
  20. 		PNODE pNew = (PNODE)malloc(sizeof(NODE));
  21. 		if (NULL == pNew)
  22. 		{
  23. 			printf("分配内存失败，程序结束\n");
  24. 			exit(-1);
  25. 		}
  26. 		pNew->data = value;
  27. 		pTail->pNext = pNew;
  28. 		pNew->pNext = NULL;
  29. 		pTail = pNew;
  30. 	}
  31.  
  32. 	return pHead;
  33. }

使用尾指针方便操作，链表操作里面，经常要多定义一两个指针辅助功能实现。

3.遍历链表

  1. void traverse_list(PNODE pHead)//遍历链表
  2. {
  3. 	PNODE p = pHead->pNext;//用指针p指向第一个结点
  4.  
  5. 	while (p != NULL)
  6. 	{
  7. 		printf("%-4d", p->data);
  8. 		p = p->pNext;
  9. 	}
  10. 	printf("\n");
  11.  
  12. }

把头指针赋值给另外一个新的指针，遍历时就移动新指针就好了。

4.判断链表是否为空

  1. bool is_empty(PNODE pHead)//判断链表是否为空
  2. {
  3. 	if (NULL == pHead->pNext)
  4. 		return true;
  5. 	else
  6. 		return false;
  7. }

5.计算链表长度

  1. int length_list(PNODE pHead)//计算链表长度
  2. {
  3. 	PNODE p = pHead->pNext;
  4. 	int length = 0;
  5. 	while (p != NULL)
  6. 	{
  7. 		length++;
  8. 		p = p->pNext;
  9. 	}
  10. 	return length;
  11. }

6.插入一个数据

  1. bool insert_list(PNODE pHead, int position, int value)//在第position个结点前面插入一个结点
  2. {
  3. 	int i = 0;
  4. 	PNODE p = pHead;
  5.  
  6. 	while (p != NULL && i < position - 1)
  7. 	{
  8. 		p = p->pNext;
  9. 		i++;
  10. 	}
  11.  
  12. 	if (i > position - 1 || NULL == p)
  13. 		return false;
  14. 	
  15. 	PNODE pNew = (PNODE)malloc(sizeof(NODE));
  16. 	if (NULL == pNew)
  17. 	{
  18. 		printf("内存分配失败\n");
  19. 		exit(-1);
  20. 	}
  21. 	pNew->data = value;
  22. 	PNODE q = p->pNext;
  23. 	p->pNext = pNew;
  24. 	pNew->pNext = q;
  25. 	return true;
  26. }

7.删除数据

  1. bool delect_list(PNODE pHead, int position, int* value)//删除第position个结点
  2. {
  3. 	int i = 0;
  4. 	PNODE p = pHead;
  5.  
  6. 	while (p->pNext != NULL && i < position - 1)
  7. 	{
  8. 		p = p->pNext;
  9. 		i++;
  10. 	}
  11.  
  12. 	if (i > position - 1 || NULL == p->pNext)
  13. 		return false;
  14.  
  15. 	PNODE q = p->pNext;
  16. 	*value = q->data;
  17. 	p->pNext = p->pNext->pNext;
  18. 	free(q);
  19. 	q = NULL;
  20. 	return true;
  21. }

删完记得释放内存，否则造成内存泄漏。

排序

  1. void sort_list(PNODE pHead)//排序
  2. {
  3. 	int length = length_list(pHead);
  4. 	int i, j, t;
  5. 	PNODE p, q;
  6. 	for (i = 0,p = pHead->pNext; i < length - 1; i++, p = p->pNext)
  7. 	{
  8. 		for (j = i + 1, q = p->pNext; j < length; j++, q = q->pNext)
  9. 		{
  10. 			if (p->data > q->data)
  11. 			{
  12. 				t = p->data;
  13. 				p->data = q->data;
  14. 				q->data = t;
  15. 			}
  16. 		}
  17. 	}
  18. }

8.全部代码

  1. #include<stdio.h>
  2. #include<malloc.h>
  3. #include<stdlib.h>
  4. #pragma warning(disable : 4996)
  5.  
  6. typedef int Elemtype;
  7.  
  8. typedef struct Node
  9. {
  10. 	Elemtype data;//数据域
  11. 	struct Node* pNext;//指针域
  12.  
  13. }NODE, * PNODE;//NODE相当于struct Node，* PNODE相当于struct Node *
  14.  
  15. PNODE create_list();
  16. void traverse_list(PNODE pHead);
  17. bool is_empty(PNODE pHead);
  18. int length_list(PNODE pHead);
  19. bool insert_list(PNODE pHead, int position, int value);
  20. bool delect_list(PNODE pHead, int position, int* value);
  21. void sort_list(PNODE pHead);
  22.  
  23.  
  24. int main()
  25. {
  26. 	PNODE pHead = NULL;
  27. 	int value;
  28. 	pHead = create_list();//创建非循环单链表
  29. 	traverse_list(pHead);
  30. 	if (is_empty(pHead))
  31. 		printf("链表为空\n");
  32. 	else
  33. 		printf("链表不为空\n");
  34. 	int length = length_list(pHead);
  35. 	printf("链表长度为%d\n", length);
  36.  
  37. 	insert_list(pHead, 4, 75);
  38. 	traverse_list(pHead);
  39. 	sort_list(pHead);
  40. 	traverse_list(pHead);
  41. 	if (delect_list(pHead, 4, &value))
  42. 	{
  43. 		printf("删除成功，删除的元素为%d\n", value);
  44. 	}
  45. 	else
  46. 	{
  47. 		printf("删除失败，删除的元素不存在\n");
  48. 	}
  49. 	traverse_list(pHead);
  50.  
  51. 	return 0;
  52. }
  53.  
  54. PNODE create_list()//创建链表
  55. {
  56. 	int length, value;
  57.  
  58. 	PNODE pHead = (PNODE)malloc(sizeof(NODE));//分配头结点
  59. 	if (NULL == pHead)
  60. 	{
  61. 		printf("分配内存失败，程序结束！\n");
  62. 		exit(-1);
  63. 	}
  64. 	PNODE pTail = pHead;//尾结点，每次增加结点时，尾结点跟着后移
  65. 	pTail->pNext = NULL;
  66.  
  67. 	printf("链表结点个数：");
  68. 	scanf("%d", &length);
  69. 	for (int i = 0; i < length; i++)
  70. 	{
  71. 		printf("输入第%d个结点的值：", i + 1);
  72. 		scanf("%d", &value);
  73. 		PNODE pNew = (PNODE)malloc(sizeof(NODE));
  74. 		if (NULL == pNew)
  75. 		{
  76. 			printf("分配内存失败，程序结束\n");
  77. 			exit(-1);
  78. 		}
  79. 		pNew->data = value;
  80. 		pTail->pNext = pNew;
  81. 		pNew->pNext = NULL;
  82. 		pTail = pNew;
  83. 	}
  84.  
  85. 	return pHead;
  86. }
  87.  
  88. void traverse_list(PNODE pHead)//遍历链表
  89. {
  90. 	PNODE p = pHead->pNext;//用指针p指向第一个结点
  91.  
  92. 	while (p != NULL)
  93. 	{
  94. 		printf("%-4d", p->data);
  95. 		p = p->pNext;
  96. 	}
  97. 	printf("\n");
  98.  
  99. }
  100.  
  101. bool is_empty(PNODE pHead)//判断链表是否为空
  102. {
  103. 	if (NULL == pHead->pNext)
  104. 		return true;
  105. 	else
  106. 		return false;
  107. }
  108.  
  109. int length_list(PNODE pHead)//计算链表长度
  110. {
  111. 	PNODE p = pHead->pNext;
  112. 	int length = 0;
  113. 	while (p != NULL)
  114. 	{
  115. 		length++;
  116. 		p = p->pNext;
  117. 	}
  118. 	return length;
  119. }
  120.  
  121. bool insert_list(PNODE pHead, int position, int value)//在第position个结点前面插入一个结点
  122. {
  123. 	int i = 0;
  124. 	PNODE p = pHead;
  125.  
  126. 	while (p != NULL && i < position - 1)
  127. 	{
  128. 		p = p->pNext;
  129. 		i++;
  130. 	}
  131.  
  132. 	if (i > position - 1 || NULL == p)
  133. 		return false;
  134. 	
  135. 	PNODE pNew = (PNODE)malloc(sizeof(NODE));
  136. 	if (NULL == pNew)
  137. 	{
  138. 		printf("内存分配失败\n");
  139. 		exit(-1);
  140. 	}
  141. 	pNew->data = value;
  142. 	PNODE q = p->pNext;
  143. 	p->pNext = pNew;
  144. 	pNew->pNext = q;
  145. 	return true;
  146. }
  147.  
  148. bool delect_list(PNODE pHead, int position, int* value)//删除第position个结点
  149. {
  150. 	int i = 0;
  151. 	PNODE p = pHead;
  152.  
  153. 	while (p->pNext != NULL && i < position - 1)
  154. 	{
  155. 		p = p->pNext;
  156. 		i++;
  157. 	}
  158.  
  159. 	if (i > position - 1 || NULL == p->pNext)
  160. 		return false;
  161.  
  162. 	PNODE q = p->pNext;
  163. 	*value = q->data;
  164. 	p->pNext = p->pNext->pNext;
  165. 	free(q);
  166. 	q = NULL;
  167. 	return true;
  168. }
  169.  
  170. void sort_list(PNODE pHead)//排序
  171. {
  172. 	int length = length_list(pHead);
  173. 	int i, j, t;
  174. 	PNODE p, q;
  175. 	for (i = 0,p = pHead->pNext; i < length - 1; i++, p = p->pNext)
  176. 	{
  177. 		for (j = i + 1, q = p->pNext; j < length; j++, q = q->pNext)
  178. 		{
  179. 			if (p->data > q->data)
  180. 			{
  181. 				t = p->data;
  182. 				p->data = q->data;
  183. 				q->data = t;
  184. 			}
  185. 		}
  186. 	}
  187. }

主函数内容仅仅是测试功能而已，最重要是理解各个函数是实现对应的功能。

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

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

  

闽ICP备14008679号