• 链表（7.27）

    3.3 链表的实现
    3.3.1头插
    原理图：
    newnode为新创建的节点
    实现： 
    1. //头插
    2. //让新节点指向原来的头指针（节点），即新节点位于开头
    3. newnode->next = plist;
    4. //再让头指针（节点）指向新节点，新节点就成为了头节点
    5. plist = newnode;

    此操作在链表为空的情况下也能正常运行。

    3.3.2尾插
    原理：创建一个新节点，先通过局部变量 tail 遍历找到指向的下一个节点为空的节点（即倒数第二个节点），然后将该节点与新节点链接起来。
    初步实现： 
    1. // 单链表尾插
    2. //第一个参数为头指针的拷贝（形参）
    3. void SListPushBack(SLTNode* phead, SLTDataType x)
    4. {
    5. 	SLTNode* tail = phead;
    6. 	//创建要插入的新节点
    7. 	SLTNode* newnode = BuySListNode(x);
    8. 	//遍历下一个节点指向为空的节点
    9. 	while (tail->next != NULL)
    10. 	{
    11. 		tail = tail->next;
    12. 	}
    13.     //将该节点与新节点链接起来
    14. 	tail->next = newnode;
    15. }

    phead,tail,newnode为局部变量，出了作用域就会自动销毁，而链表的节点存在于堆上，不会自动销毁。

    上面的步骤是在原有链表的前提下进行的，如果链表为空呢？

    需要让新节点充当头节点，也就是要让 plist（结构体指针）（头指针） 指向新节点,因此我们尝试将新创建的节点赋给头指针

    1. if (phead == NULL)
    2. 	{
    3. 		phead = newnode;
    4. 	}

    但这个做法对吗，显然不对，形参是实参的一份临时拷贝，改变形参不影响实参，出了这个作用域，这两个指针就销毁了，plist也没有改变。

    plist 是结构体类型的指针，要改变它的值，在函数中就需要传它的地址，也就是指针的地址。

    1. //第一个参数为头指针的拷贝（形参）
    2. void SListPushBack(SLTNode** pphead, SLTDataType x)
    3. {
    4.     SLTNode* newnode = BuySListNode(x);
    5. 	//如果链表为空
    6. 	//*pphead==plist
    7. 	if (*pphead == NULL)
    8. 	{
    9. 		*pphead = newnode;
    10. 	}
    11. 	else
    12. 	{
    13. 		SLTNode* tail = *pphead;
    14. 		//创建要插入的新节点
    15.  
    16. 		//遍历下一个节点指向为空的节点
    17. 		while (tail->next != NULL)
    18. 		{
    19. 			tail = tail->next;
    20. 		}//将该节点与新节点链接起来
    21. 		tail->next = newnode;
    22. 	}
    23. }

     总结：

    改变结构体用结构体指针；

    改变结构体指针用结构体二级指针；

    3.3.3头插

    本篇开头已经在函数外实现过了，现在在函数中实现一次。

    每一次头插都要改变 plist 头指针，因此也需要传二重指针

    1. // 单链表的头插
    2. void SListPushFront(SLTNode** pphead, SLTDataType x)
    3. {
    4. 	SLTNode* newnode = BuySListNode(x);
    5. 	newnode->next = *pphead;
    6. 	*pphead = newnode;
    7. }

    3.3.4尾删

    根据剩余节点的不同，分3种情况

    1.链表为空

    这是一种异常的情况，我们需要使用断言对参数加以限制，以防传空指针情况的出现。

    assert(*pphead);

    2.链表只剩一个节点

    再删掉就为空，这时候就需要释放节点的空间，并将头指针置空，就涉及到了头指针的改变，需要引用二级指针。

        if ((*pphead)->next == NULL)
        {
            free(*pphead);
            *pphead = NULL;
        }

    3.链表中包含>1个节点

    用 tail 找到末尾节点并将其删除，将倒数第二个节点置空，该情况下不需要二级指针。

    原理图：

    SLTNode* tailPre = NULL;
            SLTNode* tail = *pphead;
            while (tail->next != NULL)
            {
                tailPre = tail;
                tail = tail->next;
            }
            free(tail);
            tailPre->next = NULL;

    3.3.5头删

    让头指针指向第二个节点，将第一个节点释放。

    1. // 单链表头删
    2. void SListPopFront(SLTNode** pphead)
    3. {
    4. 	assert(*pphead);
    5. 	//第二个节点
    6. 	SLTNode* newhead = (*pphead)->next;
    7. 	//释放第一个节点
    8. 	free(*pphead);
    9. 	//让第二个节点成为新的头节点
    10. 	*pphead = newhead;
    11. }

    3.3.6查找

    在链表中查找值 x ，从头遍历一遍即可，遇到空节点停止。

    1. // 单链表查找
    2. SLTNode* SListFind(SLTNode* plist, SLTDataType x)
    3. {
    4. 	SLTNode* cur = plist;
    5. 	while (cur)
    6. 	{
    7. 		//找到了就返回地址
    8. 		if (cur->data == x)
    9. 		{
    10. 			return cur;
    11. 		}
    12. 		cur = cur->next;
    13. 	}
    14. 	//遍历完了还没找到
    15. 	return NULL;
    16. }

    3.3.7 在pos之前插入X,pos为节点的指针

    根据插入的位置分在第一个节点之前插入（头插）和其余的正常插入：

    头插：由于我们之前写过头插，这里我们可以直接复用，需要注意参数的传递和头插函数的参数保持一致，即我们需要改变的是头指针 plist，因此传它的地址（二级指针）；

    正常插入：单链表的在某节点之前插入相对双链表是比较麻烦的，我们需要先通过遍历找到 pos 之前节点的指针 prev，即 prev->next==pos，然后再将代插入的节点和 prev 以及 pos 链接起来。

    1. //在pos之前插入X,pos为节点的指针
    2. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    3. {
    4. 	//pos不能为空
    5. 	assert(pos);
    6. 	//如果为头插
    7. 	if (pos == *pphead)
    8. 	{
    9. 		SLTPushFront(pphead, x);
    10. 	}
    11. 	else
    12. 	{
    13. 		SLTNode* prev = *pphead;
    14. 		while (prev->next ！= pos)
    15. 		{
    16. 			prev = prev->next;
    17. 		}
    18. 		//待插入的新节点
    19. 		SLTNode* newnode = BuySLTNode(x);
    20. 		prev->next = newnode;
    21. 		newnode->next = pos;
    22. 	}
    23. }

    3.3.8 在pos之后插入X 

     相比在 pos 前插入就容易多了，直接将待插入的新节点和 pos 以及 pos 后面的节点 pos->next 链接起来即可，链接的时候需要注意顺序，先链接后者，再链接前者，否则 pos->next 就被新节点覆盖，找不到了。

    1. //在pos之后插入X
    2. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
    3. {
    4. 	assert(pos);
    5. 	SLTNode* newnode = BuySLTNode(x);
    6. 	//先链接新节点与pos之后的节点
    7. 	newnode->next = pos->next;
    8. 	//再链接pos与新节点
    9. 	pos->next = newnode;
    10. }

     3.3.9 删除pos位置的值

    仅仅头删比较特别，需要将目标节点释放掉，让头指针指向下一个节点。

    其余情况下先遍历找到上一个节点 prev，然后释放掉 pos 节点，让 prev 指向下一个节点。

    1. //删除pos位置
    2. void SLTErase(SLTNode** pphead, SLTNode* pos)
    3. {
    4. 	assert(pos);
    5. 	//如果pos为头节点
    6. 	if (pos == *pphead)
    7. 	{
    8. 		//直接复用，参数为二级指针
    9. 		SLTPopFront(pphead);
    10. 	}
    11. 	else
    12. 	{
    13. 		SLTNode* prev = *pphead;
    14. 		while (prev->next == pos)
    15. 		{
    16. 			prev = prev->next;
    17. 		}
    18. 		prev->next = pos->next;
    19. 		free(pos);
    20. 	}
    21. }

    3.3.10 删除 pos 的下一个

     这个方法不能删除头节点，也不能删除尾节点。

    1. //删除pos的后一个
    2. void SLTEraseAfter(SLTNode* pos)
    3. {
    4. 	assert(pos);
    5. 	//不能删尾
    6. 	assert(pos->next);
    7. 	//将pos的下一个节点保存下来
    8. 	SLTNode* posNext = pos->next;
    9. 	//将pos和下下个节点链接起来
    10. 	pos->next = posNext->next;
    11. 	//释放pos的下一个节点
    12. 	free(posNext);
    13. }

    3.3.11 顺序表的销毁

    依旧使用一个 cur 指针来遍历，在释放节点的时候有两种方式

    创建一个 next 指针来指向下一个节点，然后释放 cur，再让 cur 指向 next

    记录前一个节点 del ，cur 移动到后一个节点之后，释放 del

    1. // 顺序表销毁
    2. void SLTDestory(SLTNode** pphead)
    3. {
    4. 	assert(pphead);
    5. 	SLTNode* cur = *pphead;
    6. 	while (cur)
    7. 	{
    8. 		SLTNode* next = cur->next;
    9. 		free(cur);
    10. 		cur = next;
    11. 	}
    12. 	//销毁完毕，将头指针置空
    13. 	*pphead = NULL;
    14. }

    例题：

    给定一个无头单链表，要求删除 pos 位置的节点，该如何实现？

    常规的方法行不通，我们需要另辟蹊径

     即用替换法，将 pos 下一个节点的值赋给 pos ，然后删除下一个节点，不过该方法存在一个缺陷是无法用来删除尾节点。

    完整代码：

    头文件

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. typedef int SLTDataType;
    6. typedef struct SListNode
    7. {
    8. 	SLTDataType data;
    9. 	struct SListNode* next;
    10. }SLTNode;
    11. //打印链表
    12. void SLTPrint(SLTNode* pahead);
    13. //开辟一个节点并赋值
    14. SLTNode* BuySLTNode(SLTDataType X);
    15. // 单链表尾插
    16. void SLTPushBack(SLTNode** pphead, SLTDataType x);
    17. // 单链表的头插
    18. void SLTPushFront(SLTNode** pphead, SLTDataType x);
    19. // 单链表的尾删
    20. void SLTPopBack(SLTNode** pphead);
    21. // 单链表头删
    22. void SLTPopFront(SLTNode** pphead);
    23. //在pos之前插入X,pos为节点的指针
    24. void SLTInsert(SLTNode** pphead, SLTNode* pos,SLTDataType x);
    25. //在pos之后插入X
    26. void SLTInsertAfter(SLTNode* pos, SLTDataType x);
    27. //删除pos位置
    28. void SLTErase(SLTNode** pphead, SLTNode* pos);
    29. //删除pos的后一个
    30. void SLTEraseAfter(SLTNode* pos);
    31. // 单链表查找
    32. SLTNode* SLTFind(SLTNode* plist, SLTDataType x);
    33. // 顺序表销毁
    34. void SLTDestory(SLTNode** pphead);

     测试文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"SList.h"
    3. void TestSList1()
    4. {
    5. 	int n = 0;
    6. 	printf("请输入链表的长度\n");
    7. 	scanf("%d", &n);
    8. 	printf("请依次输入每个节点的值\n");
    9. 	//创建头指针
    10. 	SLTNode* plist = NULL;
    11. 	for (int i = 0; i < n; i++)
    12. 	{
    13. 		int val = 0;
    14. 		scanf("%d", &val);
    15. 		//开辟新节点
    16. 		SLTNode* newnode = BuySLTNode(val);
    17.  
    18. 		//头插
    19. 		//让新节点指向原来的头指针（节点），即新节点位于开头
    20. 		newnode->next = plist;
    21. 		//再让头指针（节点）指向新节点，新节点就成为了头节点
    22. 		plist = newnode;
    23. 	}
    24. 	SLTPushBack(&plist, 100);
    25. 	SLTPrint(plist);
    26. }
    27. void TestSList2()
    28. {
    29. 	SLTNode* plist = NULL;
    30. 	SLTPushBack(&plist, 1);
    31. 	SLTPushBack(&plist, 2);
    32. 	SLTPushBack(&plist, 3);
    33. 	SLTPushBack(&plist, 4);
    34. 	SLTPushBack(&plist, 5);
    35. 	SLTPrint(plist);
    36.  
    37. 	SLTPushFront(&plist, 10);
    38. 	SLTPushFront(&plist, 20);
    39. 	SLTPushFront(&plist, 30);
    40. 	SLTPushFront(&plist, 40);
    41. 	SLTPrint(plist);
    42. }
    43. void TestSList3()
    44. {
    45. 	SLTNode* plist = NULL;
    46. 	SLTPushBack(&plist, 1);
    47. 	SLTPushBack(&plist, 2);
    48. 	SLTPushBack(&plist, 3);
    49. 	SLTPushBack(&plist, 4);
    50. 	SLTPushBack(&plist, 5);
    51. 	SLTPrint(plist);
    52.  
    53.  
    54. 	SLTPopBack(&plist);
    55. 	SLTPrint(plist);
    56.  
    57. 	SLTPopBack(&plist);
    58. 	SLTPrint(plist);
    59.  
    60. 	SLTPopBack(&plist);
    61. 	SLTPrint(plist);
    62.  
    63. 	SLTPopBack(&plist);
    64. 	SLTPrint(plist);
    65.  
    66. 	SLTPopBack(&plist);
    67. 	SLTPrint(plist);
    68.  
    69. 	// SLTPopBack(&plist);
    70. 	// SLTPrint(plist);
    71. }
    72. void TestSList4()
    73. {
    74. 	SLTNode* plist = NULL;
    75. 	SLTPushBack(&plist, 1);
    76. 	SLTPushBack(&plist, 2);
    77. 	SLTPushBack(&plist, 3);
    78. 	SLTPushBack(&plist, 4);
    79. 	SLTPushBack(&plist, 5);
    80. 	SLTPrint(plist);
    81.  
    82. 	SLTPopFront(&plist);
    83. 	SLTPrint(plist);
    84.  
    85. 	SLTPopFront(&plist);
    86. 	SLTPrint(plist);
    87.  
    88. 	SLTPopFront(&plist);
    89. 	SLTPrint(plist);
    90.  
    91. 	SLTPopFront(&plist);
    92. 	SLTPrint(plist);
    93.  
    94. 	SLTPopFront(&plist);
    95. 	//SLTPopFront(&plist);
    96. 	SLTPrint(plist);
    97. }
    98. void TestSList5()
    99. {
    100. 	SLTNode* plist = NULL;
    101. 	SLTPushBack(&plist, 1);
    102. 	SLTPushBack(&plist, 2);
    103. 	SLTPushBack(&plist, 3);
    104. 	SLTPushBack(&plist, 4);
    105. 	SLTPushBack(&plist, 5);
    106. 	SLTPrint(plist);
    107.  
    108. 	SLTNode* pos = SLTFind(plist, 3);
    109. 	SLTInsert(&plist, pos, 30);
    110. 	SLTPrint(plist);
    111. }
    112. void TestSList6()
    113. {
    114. 	SLTNode* plist = NULL;
    115. 	SLTPushBack(&plist, 1);
    116. 	SLTPushBack(&plist, 2);
    117. 	SLTPushBack(&plist, 3);
    118. 	SLTPushBack(&plist, 4);
    119. 	SLTPushBack(&plist, 5);
    120. 	SLTPrint(plist);
    121.  
    122. 	int x;
    123. 	scanf("%d", &x);
    124. 	SLTNode* pos = SLTFind(plist, x);
    125. 	if (pos)
    126. 	{
    127. 		SLTInsertAfter(pos, x * 10);
    128. 	}
    129. 	SLTPrint(plist);
    130. }
    131.  
    132. void TestSList7()
    133. {
    134. 	SLTNode* plist = NULL;
    135. 	SLTPushBack(&plist, 1);
    136. 	SLTPushBack(&plist, 2);
    137. 	SLTPushBack(&plist, 3);
    138. 	SLTPushBack(&plist, 4);
    139. 	SLTPushBack(&plist, 5);
    140. 	SLTPrint(plist);
    141.  
    142. 	int x;
    143. 	scanf("%d", &x);
    144. 	SLTNode* pos = SLTFind(plist, x);
    145. 	if (pos)
    146. 	{
    147. 		//SLTErase(&plist, pos);
    148. 		SLTEraseAfter(pos);
    149. 		pos = NULL;
    150. 	}
    151. 	SLTPrint(plist);
    152.  
    153. 	SLTPopFront(&plist);
    154. 	SLTPrint(plist);
    155.  
    156. 	SLTPopFront(&plist);
    157. 	SLTPrint(plist);
    158.  
    159. 	SLTPopFront(&plist);
    160. 	SLTPrint(plist);
    161.  
    162. 	SLTPopFront(&plist);
    163. 	SLTPrint(plist);
    164.  
    165. }
    166. int main()
    167. {
    168. 	//TestSList1();
    169. 	//TestSList2();
    170. 	//TestSList3();
    171. 	//TestSList4();
    172. 	//TestSList5();
    173. 	//TestSList5();
    174. 	TestSList7();
    175. 	return 0;
    176. }

    实现文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include"SList.h"
    3. void SLTPrint(SLTNode* phead)
    4. {
    5. 	SLTNode* cur = phead;
    6. 	while (cur != NULL)
    7. 	{
    8. 		printf("%d->", cur->data);
    9. 		cur = cur->next;
    10. 	}
    11. 	//结束，打印空
    12. 	printf("NULL\n");
    13. }
    14. //开辟节点并赋值
    15. SLTNode* BuySLTNode(SLTDataType X)
    16. {
    17. 	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    18. 	if (newnode == NULL)
    19. 	{
    20. 		perror("malloc");
    21. 		exit(-1);
    22. 	}
    23. 	newnode->data = X;
    24. 	newnode->next = NULL;
    25.  
    26. 	return newnode;
    27. }
    28. // 单链表尾插
    29. //第一个参数为头指针的拷贝（形参）
    30. void SLTPushBack(SLTNode** pphead, SLTDataType x)
    31. {
    32.     SLTNode* newnode = BuySLTNode(x);
    33. 	//如果链表为空
    34. 	//*pphead==plist
    35. 	if (*pphead == NULL)
    36. 	{
    37. 		//改变结构体指针，用结构体二级指针
    38. 		*pphead = newnode;
    39. 	}
    40. 	else
    41. 	{
    42. 		SLTNode* tail = *pphead;
    43. 		//创建要插入的新节点
    44.  
    45. 		//遍历下一个节点指向为空的节点
    46. 		while (tail->next != NULL)
    47. 		{
    48. 			tail = tail->next;
    49. 		}
    50. 		//改变结构体用结构体指针，将该节点与新节点链接起来
    51. 		tail->next = newnode;
    52. 	}
    53. }
    54. // 单链表的头插
    55. void SLTPushFront(SLTNode** pphead, SLTDataType x)
    56. {
    57. 	SLTNode* newnode = BuySLTNode(x);
    58. 	newnode->next = *pphead;
    59. 	*pphead = newnode;
    60. }
    61. // 单链表的尾删
    62. void SLTPopBack(SLTNode** pphead)
    63. {
    64. 	//限制参数不为空
    65. 	assert(*pphead);
    66. 	//仅有一个节点的情况
    67. 	if ((*pphead)->next == NULL)
    68. 	{
    69. 		free(*pphead);
    70. 		*pphead = NULL;
    71. 	}
    72. 	//有两个及以上节点的情况
    73. 	else
    74. 	{
    75. 		//尾节点的前一个节点
    76. 		SLTNode* tailPre = NULL;
    77. 		SLTNode* tail = *pphead;
    78. 		while (tail->next != NULL)
    79. 		{
    80. 			tailPre = tail;
    81. 			//tail往后走之前赋给前一个指针
    82. 			tail = tail->next;
    83. 		}
    84. 		free(tail);
    85. 		tailPre->next = NULL;
    86. 	}
    87. }
    88. // 单链表头删
    89. void SLTPopFront(SLTNode** pphead)
    90. {
    91. 	assert(*pphead);
    92. 	//第二个节点
    93. 	SLTNode* newhead = (*pphead)->next;
    94. 	//释放第一个节点
    95. 	free(*pphead);
    96. 	//让第二个节点成为新的头节点
    97. 	*pphead = newhead;
    98. }
    99. // 单链表查找
    100. SLTNode* SLTFind(SLTNode* plist, SLTDataType x)
    101. {
    102. 	SLTNode* cur = plist;
    103. 	while (cur)
    104. 	{
    105. 		//找到了就返回地址
    106. 		if (cur->data == x)
    107. 		{
    108. 			return cur;
    109. 		}
    110. 		cur = cur->next;
    111. 	}
    112. 	//遍历完了还没找到
    113. 	return NULL;
    114. }
    115. //在pos之前插入X,pos为节点的指针
    116. void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    117. {
    118. 	//pos不能为空
    119. 	assert(pos);
    120. 	//如果为头插
    121. 	if (pos == *pphead)
    122. 	{
    123. 		SLTPushFront(pphead, x);
    124. 	}
    125. 	else
    126. 	{
    127. 		SLTNode* prev = *pphead;
    128. 		while (prev->next != pos)
    129. 		{
    130. 			prev = prev->next;
    131. 		}
    132. 		//待插入的新节点
    133. 		SLTNode* newnode = BuySLTNode(x);
    134. 		prev->next = newnode;
    135. 		newnode->next = pos;
    136. 	}
    137. }
    138. //在pos之后插入X
    139. void SLTInsertAfter(SLTNode* pos, SLTDataType x)
    140. {
    141. 	assert(pos);
    142. 	SLTNode* newnode = BuySLTNode(x);
    143. 	//先链接新节点与pos之后的节点
    144. 	newnode->next = pos->next;
    145. 	//再链接pos与新节点
    146. 	pos->next = newnode;
    147. }
    148. //删除pos位置
    149. void SLTErase(SLTNode** pphead, SLTNode* pos)
    150. {
    151. 	assert(pos);
    152. 	//如果pos为头节点
    153. 	if (pos == *pphead)
    154. 	{
    155. 		//直接复用，参数为二级指针
    156. 		SLTPopFront(pphead);
    157. 	}
    158. 	else
    159. 	{
    160. 		SLTNode* prev = *pphead;
    161. 		while (prev->next == pos)
    162. 		{
    163. 			prev = prev->next;
    164. 		}
    165. 		prev->next = pos->next;
    166. 		free(pos);
    167. 	}
    168. }
    169. //删除pos的后一个
    170. void SLTEraseAfter(SLTNode* pos)
    171. {
    172. 	assert(pos);
    173. 	//不能删尾
    174. 	assert(pos->next);
    175. 	//将pos的下一个节点保存下来
    176. 	SLTNode* posNext = pos->next;
    177. 	//将pos和下下个节点链接起来
    178. 	pos->next = posNext->next;
    179. 	//释放pos的下一个节点
    180. 	free(posNext);
    181. }
    182. // 顺序表销毁
    183. void SLTDestory(SLTNode** pphead)
    184. {
    185. 	assert(pphead);
    186. 	SLTNode* cur = *pphead;
    187. 	while (cur)
    188. 	{
    189. 		SLTNode* next = cur->next;
    190. 		free(cur);
    191. 		cur = next;
    192. 	}
    193. 	//销毁完毕，将头指针置空
    194. 	*pphead = NULL;
    195. }

  • 相关阅读:
    django的update和create高级操作
    React中如何提高组件的渲染效率
    Vue2+Vue3
    干货 | 精准化测试原理简介与实践探索
    ＜Python＞＜paddleocr＞基于python使用百度paddleocr实现图片文字识别与替换
    电脑提示找不到dinput8.dll，无法继续执行代码的解决办法，解决dinput8.dll丢失问题
    线程的控制与同步
    【Python深度学习】深度学习中框架和模型的区别
    第5章 - 二阶多智能体系统的协同控制 --＞ 连续时间系统一致性
    2023网络安全学习路线 非常详细 推荐学习
  • 原文地址：https://blog.csdn.net/dn235z/article/details/133656213