• 单链表---结构体实现

    定义

    链表称为线性表的链式存储，顺序表逻辑上相邻的数据，存储位置也相邻。链表逻辑上相邻的数据，存储位置是随机分布在内存的各个位置上的。

    故

    对于每一个结点，定义的结构体是：

    1. typedef struct _LinkNode 
    2. {
    3. 	int date;				//数据域，存储数据，这里是int类型的数据
    4. 	struct _LinkNode* next; // 指针域，指向了后继元素（下一个结点）的地址
    5. }LinkNode , LinkList;       //两个别名的作用是一模一样的，只是为了区分头结点和结点

     链表的初始化

    我们用一个结构体指针L来指向链表，最开始是带一个头结点的空链表，头结点的数据域一般赋值为-1，也可以存储着链表的长度。头结点的指针域指针第一个元素结点，最开始是没有元素结点的空链表（有头结点），如图：

    代码实现

    1. bool initLinkList(LinkList*& L) //参数是对结构体指针的引用
    2. {
    3. 	L = new LinkList; //也可以写成 L = new LinkNode ;
    4. 	if (!L)
    5. 	{
    6. 		return false; // 申请内存失败，返回了一个空指针
    7. 	}
    8.     
    9. 	L->next = NULL;
    10. 	return true;
    11. }

    链表的插入

    头插法

    将新结点插到头结点的后面，有两种形式，一是链表为空，二是链表中已有元素结点，如图

    你可以分情况，不过也可以不用，例如：

    1. bool insertLinkList(LinkList*& L, LinkNode *node) //node指向要添加的结点
    2. {
    3. 	
    4. 	if (!L || !node) return false;
    5.  
    6. 	node->next = L->next; //包含两种情况
    7. 	L->next = node;
    8. 	return true;
    9. }

    尾插法

    尾插，顾名思义就是在最后一个结点插入之后，也分两种情况，一是链表为空，二是链表中已有元素结点，第一种情况的图和头插法的第一种情况的图一样，就是插入方式不同，以下是第二种情况的图：

    我们只需要找到 next 指向 NULL 的这个结点就好了

    1. bool LinkListinsert(LinkList*& L, LinkNode *node)
    2. {
    3. 	if (!L || !node) return false;
    4.  
    5. 	LinkNode* p = NULL;
    6. 	p = L;
    7.  
    8. 	while (p->next != NULL) //如果是空链表，p == L，所以是包含两种情况
    9. 	{
    10. 		p = p->next;
    11. 	}
    12. 	
    13. 	node->next = p->next;
    14. 	p->next = node;
    15.  
    16. 	return true;
    17. }

    指定位置插入

    在第 i 个结点前插入，那么我们就必须有个临时指针指向第 i-1 个结点

    1. bool InsertLink(LinkList*& L, int i, int e) // 这里也可以用之前的LinkNode *node参数，不过可能i不合法
    2. {
    3. 	if (!L) return false;
    4. 	
    5. 	LinkNode* p = L , *s = NULL ;
    6. 	int j = 0;
    7.  
    8. 	while (p && j < i - 1) // 指向第 i-1 个结点
    9. 	{	
    10. 		p = p->next;
    11. 		j++;
    12. 	}
    13.  
    14. 	//如果在第0个位置之前插入(i<1) || 如果在最后一个结点+2的位置之前插入(i>n+1,n为链表长度)---都是非法的
    15. 	if (i < 1 || !p) return false;
    16.  
    17. 	s = new LinkNode;
    18. 	s->date = e;
    19. 	s->next = p->next;
    20. 	p->next = s;
    21. 	return true;
    22. }

    遍历链表（打印链表）

    1. bool PrintLinkList(LinkList *& L)
    2. {
    3.     if(!L) return false; 
    4. 	LinkNode* p = L->next; //首先指向第一个结点，如果为空链表就会指向 NULL
    5.  
    6. 	while (p != NULL) // 直到指向最后一个结点的 next 指针（NULL）
    7. 	{
    8. 		printf("%d ", p->date);
    9. 		p = p->next;
    10. 	}
    11. 	cout << endl;
    12.     return true;
    13. }

    遍历链表，也可以用来求链表的长度，代码与这个类似。

    链表的获取

    获取链表第 i 个结点的数据域。

    1. bool GetElemLink(LinkList*& L, int i, int &e) //e返回获取的数据域
    2. {
    3.  
    4. 	LinkNode* p = L;
    5. 	int j = 0;
    6.  
    7. 	while ( p!=NULL && j < i)
    8. 	{
    9. 		p = p->next;
    10. 		j++;
    11. 	}
    12.  
    13. 	if (p==NULL || i < 1) //i是非法的：i > n（n为链表长度，例如：获取第n+1个结点的数据域）或者是 
    14.  i < 1（例如：获取了第0个结点的数据域）
    15. 	{
    16. 		return false;
    17. 	}
    18. 	e = p->date;
    19. 	return true;
    20. }

    链表的查找

    查找我们输入的元素在链表中出现的第一个位置。

    1. bool FindElem(LinkList* L, int e,int &index) // index返回位置
    2. {
    3. 	if (!L || !L->next) return false; //空链表
    4.  
    5. 	LinkNode* p = L->next; // 现在指向第一个结点
    6. 	int j = 1;  
    7.  
    8. 	while (p != NULL && p->date != e) 
    9. 	{
    10. 		p = p->next;
    11. 		j++;
    12. 	}
    13.  
    14. 	if (p == NULL)
    15. 		return false;
    16. 	else
    17. 	{
    18. 		index = j;
    19. 		return true;
    20. 	}
    21. }

    链表的删除

    删除第 i 个结点，i 可能不合法，注意不合法的原因。

    1. bool DeleteLinkNode(LinkList*& L, int i)
    2. {
    3.  
    4. 	LinkNode* p = NULL , *q = NULL;
    5.  
    6. 	p = L;
    7.  
    8. 	int j = 0;
    9. 	while ( p->next!=NULL && j < i - 1)
    10. 	{
    11. 		p = p->next;
    12. 		j++;
    13. 	}
    14.     // 指向第 i-1 个结点
    15.  
    16. 	if (i < 1 || p->next == NULL) //i非法，删除第0个结点(i<1) 或者是 删除第n+1个结点(i>n,n为链表的长度)
    17. 		return false;
    18. 	else
    19. 	{
    20. 		q = p->next;
    21. 		p->next = q->next ;
    22. 		delete q;
    23. 		return true;
    24. 	}
    25. 	
    26. }

    链表的销毁（清空）

    销毁就是要归还所申请的内存，删除某个结点时，一定要保存下一个结点的地址。简要解释：先保存第一个结点的地址，随后删除头结点（也申请了空间），再保存第二个结点的地址，删除第一个结点，再保存第三个结点……以此类推，可以将全部结点删除。

    1. void DestoryLink(LinkList*& L)
    2. {
    3. 	LinkNode* p = NULL, * q = NULL;
    4.  
    5. 	p = L;
    6.  
    7. 	while (p != NULL)
    8. 	{	
    9. 		q = p->next;
    10. 		//cout << "删除元素" << p->date << endl;
    11. 		delete p;
    12. 		p = q;
    13. 	}
    14.  
    15. }

    总代码

    以下是全部代码，链表的函数有不同的实现方法。也许我的代码和别人有些差异，所以可以看看 main 函数中是怎样的。

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2.  
    3. #include <iostream>
    4.  
    5. using namespace std;
    6.  
    7.  
    8. typedef struct _LinkNode
    9. {
    10. 	int date;				//数据域
    11. 	struct _LinkNode* next; // 指针域
    12.  
    13. }LinkNode , LinkList;
    14.  
    15.  
    16. //初始化链表
    17. bool initLinkList(LinkList*& L)
    18. {
    19. 	L = new LinkList;
    20. 	if (!L)
    21. 	{
    22. 		return false;
    23. 	}
    24. 	L->next = NULL;
    25. 	return true;
    26. }
    27.  
    28. //前插法
    29. bool insertLinkList(LinkList*& L, LinkNode *node)
    30. {
    31. 	
    32. 	if (!L || !node) return false;
    33.  
    34. 	node->next = L->next;
    35. 	L->next = node;
    36. 	return true;
    37. }
    38.  
    39. //尾插法
    40. bool LinkListinsert(LinkList*& L, LinkNode *node)
    41. {
    42. 	if (!L || !node) return false;
    43.  
    44. 	LinkNode* p = NULL;
    45. 	p = L;
    46.  
    47. 	while (p->next != NULL)
    48. 	{
    49. 		p = p->next;
    50. 	}
    51. 	
    52. 	node->next = p->next;
    53. 	p->next = node;
    54. 	return true;
    55. }
    56.  
    57. //在第i个结点前插入---指定位置插入
    58. bool InsertLink(LinkList*& L, int i, int e)
    59. {
    60. 	if (!L) return false;
    61. 	
    62. 	LinkNode* p = L , *s = NULL ;
    63. 	int j = 0;
    64.  
    65. 	while (p && j < i - 1)
    66. 	{	
    67. 		p = p->next;
    68. 		j++;
    69. 	}
    70.  
    71. 	//如果在第0个位置之前插入(i<1) || 如果在最后一个结点+2的位置之前插入(i>n+1,n为链表长度)---都是非法的
    72. 	if (i < 1 || !p) return false;
    73.  
    74. 	s = new LinkNode;
    75. 	s->date = e;
    76. 	s->next = p->next;
    77. 	p->next = s;
    78. 	return true;
    79. }
    80.  
    81. //打印链表
    82. void PrintLinkList(LinkList *& L)
    83. {
    84. 	LinkNode* p = L->next;
    85.  
    86. 	while (p != NULL)
    87. 	{
    88. 		printf("%d ", p->date);
    89. 		p = p->next;
    90. 	}
    91. 	cout << endl;
    92. }
    93.  
    94. //获取第i个结点的数据元素
    95. bool GetElemLink(LinkList*& L, int i, int &e)
    96. {
    97.  
    98. 	LinkNode* p = L;
    99. 	int j = 0;
    100.  
    101. 	while ( p!=NULL && j < i)
    102. 	{
    103. 		p = p->next;
    104. 		j++;
    105. 	}
    106.  
    107. 	if (p==NULL || i < 1)
    108. 	{
    109. 		return false;
    110. 	}
    111. 	e = p->date;
    112. 	return true;
    113. }
    114.  
    115. //在链表中查找元素,并且用index返回位置
    116. bool FindElem(LinkList* L, int e,int &index)
    117. {
    118. 	if (!L || !L->next) return false;
    119.  
    120. 	LinkNode* p = L->next;
    121. 	int j = 1;
    122.  
    123. 	while (p && p->date != e)
    124. 	{
    125. 		p = p->next;
    126. 		j++;
    127. 	}
    128.  
    129. 	if (p == NULL)
    130. 		return false;
    131. 	else
    132. 	{
    133. 		index = j;
    134. 		return true;
    135. 	}
    136. }
    137.  
    138.  
    139. //删除第i个结点
    140. bool DeleteLinkNode(LinkList*& L, int i)
    141. {
    142.  
    143. 	LinkNode* p = NULL , *q = NULL;
    144.  
    145. 	p = L;
    146.  
    147. 	int j = 0;
    148. 	while ( p->next!=NULL && j < i - 1)
    149. 	{
    150. 		p = p->next;
    151. 		j++;
    152. 	}
    153.  
    154.  
    155. 	if (i < 1 || p->next == NULL) //删除第0个结点(i<1) 或者是 删除第n+1个结点(i>n,n为链表的长度)
    156. 		return false;
    157. 	else
    158. 	{
    159. 		q = p->next;
    160. 		p->next = q->next ;
    161. 		delete q;
    162. 		return true;
    163. 	}
    164. 	
    165. }
    166.  
    167.  
    168. //清空(销毁)链表
    169. void DestoryLink(LinkList*& L)
    170. {
    171. 	LinkNode* p = NULL, * q = NULL;
    172.  
    173. 	p = L;
    174.  
    175. 	while (p != NULL)
    176. 	{	
    177. 		q = p->next;
    178. 		//cout << "删除元素" << p->date << endl;
    179. 		delete p;
    180. 		p = q;
    181. 	}
    182.  
    183. }
    184. int main(void)
    185. {
    186. 	LinkList* L = NULL; //指向表头（头结点）的指针
    187. 	LinkNode* e = NULL; //指向结点的指针
    188. 	initLinkList(L);
    189.  
    190. 	int elem = 0;		//结点的数据元素
    191. 	int i;				//第几个结点
    192. 	int n = 0;			//输入的个数
    193.  
    194. 	int flag = -1;
    195. 	while (flag != 0)
    196. 	{
    197. 		cout << "1.前插链表" << endl
    198. 			<< "2.尾插链表" << endl
    199. 			<< "3.指定位置前插入" << endl
    200. 			<< "4.打印链表" << endl
    201. 			<< "5.获取第i个结点的数据" << endl
    202. 			<< "6.查找元素" << endl
    203. 			<<"7.删除元素"<<endl
    204. 			<< "0.退出(销毁链表)" << endl;
    205. 		cout << "请选择:";
    206. 		cin >> flag;
    207. 		
    208. 		switch (flag)
    209. 		{
    210. 		case 1:
    211. 			cout << "请输入前插法插入链表的个数";
    212. 			cin >> n;
    213. 			cout << "请依次输入" << n << "个数:";
    214. 			while (n--)
    215. 			{
    216. 				e = new LinkNode;
    217. 				cin >> e->date;
    218. 				insertLinkList(L, e);
    219. 			}
    220. 			break;
    221. 		case 2:
    222. 			cout << "请输入尾插入链表的个数";
    223. 			cin >> n;
    224. 			cout << "请依次输入" << n << "个数:";
    225. 			while (n--)
    226. 			{
    227. 				e = new LinkNode;
    228. 				cin >> e->date;
    229. 				LinkListinsert(L, e);
    230. 			}
    231. 			break;
    232. 		case 3:
    233. 			cout << "请输入插入的位置和元素:";
    234. 			cin >> i >> elem;
    235. 			InsertLink(L, i, elem);
    236. 			break;
    237. 		case 4:
    238. 			PrintLinkList(L);
    239. 			break;
    240. 		case 5:
    241. 			cout << "请输入要获取的结点i:";
    242. 			cin >> i;
    243. 			if (GetElemLink(L, i, elem))
    244. 			{
    245. 				cout << "第" << i << "个结点的值为" << elem << endl;
    246. 			}
    247. 			else
    248. 			{
    249. 				cout << "获取元素失败" << endl;
    250. 			}
    251. 			break;
    252. 		case 6:
    253. 			cout << "请输入要查找的元素:";
    254. 			cin >> elem;
    255. 			if (FindElem(L, elem, i))
    256. 			{
    257. 				cout << "找到了,此元素的位置是" << i << endl;
    258. 			}
    259. 			else
    260. 			{
    261. 				cout << "表中无此值" << endl;
    262. 			}
    263. 			break;
    264. 		case 7:
    265. 			cout << "请输入要删除的结点i:";
    266. 			cin >> i;
    267. 			if (DeleteLinkNode(L, i))
    268. 			{
    269. 				cout << "删除成功" << endl;
    270. 			}
    271. 			else
    272. 			{
    273. 				cout << "删除失败" << endl;
    274. 			}
    275. 			break;
    276. 		case 0:
    277. 			DestoryLink(L);
    278. 			break;
    279. 		default:
    280. 			cout << "输入非法! " << endl;
    281. 			break;
    282. 		}
    283.  
    284.  
    285.  
    286. 	}
    287. 	
    288.  
    289.  
    290. 	return 0;
    291. }

    这里也可以将代码复制，自己调试测试一下，删除某些代码，看看会有什么影响，更能理解。

  • 相关阅读:
    Python数据类型：数字
    如何优雅的实现无侵入性参数校验之spring-boot-starter-validation
    JS 数据结构：队列
    IDEA快捷键
    数学问题-反射定律&折射定律的向量形式推导
    一起学习 学习二叉树
    计算机网络基础（二）：物理层、数据链路层及网络层
    Mockito搭配junit单元测试
    复杂AB实验
    基于单片机的水位检测系统仿真设计
  • 原文地址：https://blog.csdn.net/qq_66805048/article/details/133798211