• 线性表——单链表的增删查改

      本节复习链表的增删查改

    首先， 链表不是连续的， 而是通过指针联系起来的。 如图：

    这四个节点不是连续的内存空间， 但是彼此之间使用了一个指针来连接。 这就是链表。 

    现在我们来实现链表的增删查改。

    目录

    单链表的全部接口：

     准备文件

    建立结构体蓝图

    申请链表节点函数接口

    单链表的打印函数接口

    单链表尾插函数接口

    单链表头插函数接口

     单链表尾删函数接口

    单链表的头删函数接口

     单链表查找函数接口

    单链表pos位置之后插入数据接口

    单链表删除pos之后位置的数据

    单链表在pos位置之前插入数据接口

    单链表删除pos位置数据接口

    单链表的销毁

    单链表的全部接口：

    //申请链表节点函数接口
    SLNode* BuySListNode(SLTDataType x);
    //单链表的打印函数接口
    void SListPrint(SLNode* phead);
    //单链表尾插函数接口
    void SListPushBack(SLNode** pphead, SLTDataType x);
    //单链表头插函数接口
    void SListPushFront(SLNode** pphead, SLTDataType x);
    //单链表尾删函数接口
    void SListPopBack(SLNode** pphead);
    //单链表的头删函数接口
    void SListPopFront(SLNode** pphead);
    //单链表查找函数接口
    SLNode* SListFind(SLNode* phead, SLTDataType x);
    //单链表在pos位置之后插入数据接口
    void SListInsertAfter(SLNode* pos, SLTDataType x);
    //单链表在pos之后的位置删除数据
    void SListPopAfter(SLNode* pos);
    //单链表在pos位置之前插入数据接口
    void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
    //单链表在pos位置删除数据接口
    void SListPop(SLNode** pphead, SLNode* pos);
    //单链表的销毁函数接口
    void SLTDestory(SLNode** pphead);
     

    ---------------------------------------------------------------------------------------------------------------------------------

     准备文件

    首先准备好三个文件夹， 一个main.c文件夹， 一个.h文件夹用来声明链表的接口以及定义结构体等。 一个.c文件夹用来实现单链表。

    ---------------------------------------------------------------------------------------------------------------------------------

    建立结构体蓝图

    首先包含一下头文件， 定义一下数据类型。

    1. #include
    2. #include
    3. #include
    4.  
    5. typedef int SLTDataType;

    接着再建立一个链表的结构体

    1. #include
    2. #include
    3. #include
    4.  
    5. typedef int SLTDataType;
    6.  
    7. typedef struct SListNode 
    8. {
    9. 	struct SListNode* next;
    10. 	SLTDataType data;
    11. }SLNode;

    ---------------------------------------------------------------------------------------------------------------------------------

    申请链表节点函数接口

    申请链表的节点操作， 在尾插， 头插， 或者特定位置插入的时候都需要， 所以可以封装成一个函数。 后续直接进行复用就可以。

    .h函数声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode //创建结构体
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);

    .c函数实现

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }

     在实现的过程中，可以将数据直接储存到新节点中。 然后让新节点指向NULL， 然后返回该节点。 然后将链表直接连接到这个节点就可以。

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表的打印函数接口

    为了便于后续的函数接口的调试， 我们先实现单链表的打印操作。

    .h函数声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);

    .c函数实现

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表尾插函数接口

    .h函数声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);

    .c函数实现

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }
    33.  
    34. //单链表尾插函数接口
    35. void SListPushBack(SLNode** pphead, SLTDataType x) 
    36. {
    37. 	assert(pphead);
    38. 	SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点
    39.  
    40. 	SLNode* cur = *pphead; //让cur指向phead所指向空间
    41. 	if (cur == NULL) //cur == NULL代表着phead指向NULL， 这时候让phead改变指向。传送phead指针的原因就是
    42. 	{                                              //要改变phead的指向。
    43. 		*pphead = newnode;//
    44. 	}
    45. 	else 
    46. 	{
    47. 		while (cur->next != NULL) //让cur遍历到最后一个节点
    48. 		{
    49. 			cur = cur->next;
    50. 		}
    51. 		cur->next = newnode;//最后
    52. 	}
    53.  
    54. }

    尾插接口时传送phead的指针的原因是因为phead可能改变指向，从空指针变为指向一个节点。要改变phead的指向那就是意味着形参要相对于phead传址调用，  而phead本身就是一个一级指针， phead取地址就是一个二级指针， 所以形参是二级指针。

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表头插函数接口

    .h函数接口

    1.  
    2. 链表的增删查改///
    3. #include
    4. #include
    5. #include
    6.  
    7. typedef int SLTDataType;
    8.  
    9. typedef struct SListNode 
    10. {
    11. 	struct SListNode* next;
    12. 	SLTDataType data;
    13. }SLNode;
    14.  
    15. //链表接口声明/
    16.  
    17. //申请链表节点函数接口
    18. SLNode* BuySListNode(SLTDataType x);
    19. //单链表的打印函数接口
    20. void SListPrint(SLNode* phead);
    21. //单链表尾插函数接口
    22. void SListPushBack(SLNode** pphead, SLTDataType x);
    23. //单链表头插函数接口
    24. void SListPushFront(SLNode** pphead, SLTDataType x);

    .c函数实现

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }
    33.  
    34. //单链表尾插函数接口
    35. void SListPushBack(SLNode** pphead, SLTDataType x) 
    36. {
    37. 	assert(pphead);
    38. 	SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点
    39.  
    40. 	SLNode* cur = *pphead; //让cur指向phead所指向空间
    41. 	if (cur == NULL) //cur == NULL代表着phead指向NULL， 这时候让phead改变指向。传送phead指针的原因就是
    42. 	{                                              //要改变phead的指向。
    43. 		*pphead = newnode;//
    44. 	}
    45. 	else 
    46. 	{
    47. 		while (cur->next != NULL) //让cur遍历到最后一个节点
    48. 		{
    49. 			cur = cur->next;
    50. 		}
    51. 		cur->next = newnode;//最后
    52. 	}
    53.  
    54. }
    55.  
    56. //单链表头插函数接口
    57. void SListPushFront(SLNode** pphead, SLTDataType x) 
    58. {
    59. 	assert(pphead);
    60. 	SLNode* newnode = BuySListNode(x);
    61. 	//
    62. 	SLNode* cur = *pphead;
    63. 	newnode->next = cur;
    64. 	*pphead = newnode;
    65.  
    66. }

    现在我们来利用打印接口调试一下我们写的是否存在问题。 

    在main.c中输入如下代码

    1. void TestSListNode()
    2. {
    3. 	SLNode* phead = NULL;
    4. 	SListPushBack(&phead, 1);
    5. 	SListPushBack(&phead, 2);
    6. 	SListPushBack(&phead, 3);
    7. 	SListPushBack(&phead, 4);
    8. 	SListPushBack(&phead, 5);
    9. 	SListPushFront(&phead, 0);
    10.  
    11.  
    12.  
    13.  
    14. 	SListPrint(phead);
    15. 	printf("\n");
    16.  
    17. 	/*SListPopFront(&phead);
    18. 	SListPopFront(&phead);
    19. 	SListPopFront(&phead);
    20. 	SListPopBack(&phead);
    21. 	SListPrint(phead);
    22. 	printf("\n");
    24. 	SLTDestory(&phead);
    25. 	
    26. 	SListPrint(phead);
    27. 	printf("\n");*/
    28.  
    29. }
    30.  
    31. int main() 
    32. {
    33. //	TestTree();
    34. //	TestStack();
    35. //	TestQueue();
    36. //	TestSeqList();
    37. 	TestSListNode();
    38. //	TestDSLNode();
    39. //	TestOJ();
    40. 	return 0;
    41. }

    运行图如下： 

     通过检验，没有问题。 继续往下走。 

    ---------------------------------------------------------------------------------------------------------------------------------

     单链表尾删函数接口

    .h文件声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);

    .c函数实现

      首先pphead不能为空， 如果phead指向空的话就直接返回。 然后定义cur和prev两个指针， 遍历寻找尾节点。 cur领先prev一个节点， cur指向尾节点的时候， 就释放掉这个节点。 然后prev指向空节点。 寻找尾节点的过程是这样的：

    代码实现

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }
    33.  
    34. //单链表尾插函数接口
    35. void SListPushBack(SLNode** pphead, SLTDataType x) 
    36. {
    37. 	assert(pphead);
    38. 	SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点
    39.  
    40. 	SLNode* cur = *pphead; //让cur指向phead所指向空间
    41. 	if (cur == NULL) //cur == NULL代表着phead指向NULL， 这时候让phead改变指向。传送phead指针的原因就是
    42. 	{                                              //要改变phead的指向。
    43. 		*pphead = newnode;//
    44. 	}
    45. 	else 
    46. 	{
    47. 		while (cur->next != NULL) //让cur遍历到最后一个节点
    48. 		{
    49. 			cur = cur->next;
    50. 		}
    51. 		cur->next = newnode;//最后
    52. 	}
    53.  
    54. }
    55.  
    56. //单链表头插函数接口
    57. void SListPushFront(SLNode** pphead, SLTDataType x) 
    58. {
    59. 	assert(pphead);
    60. 	SLNode* newnode = BuySListNode(x);
    61. 	//
    62. 	SLNode* cur = *pphead;
    63. 	newnode->next = cur;
    64. 	*pphead = newnode;
    65.  
    66. }
    67.  
    68. //单链表尾删函数接口
    69. void SListPopBack(SLNode** pphead) 
    70. {
    71. 	assert(pphead);
    72. 	if (*pphead == NULL)
    73. 		return;
    74. 	//
    75. 	SLNode* cur = *pphead;
    76. 	SLNode* prev = *pphead;
    77. 	while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表
    78. 	{
    79. 		prev = cur;
    80. 		cur = cur->next;
    81. 	}
    82. 	if (prev == cur) 
    83. 	{
    84. 		free(cur);
    85. 		*pphead = NULL;
    86. 	}
    87. 	else 
    88. 	{
    89. 		free(cur);
    90. 		prev = NULL;
    91. 	}
    92. 	
    93. }

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表的头删函数接口

    .h函数声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);

    .c函数实现 

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }
    33.  
    34. //单链表尾插函数接口
    35. void SListPushBack(SLNode** pphead, SLTDataType x) 
    36. {
    37. 	assert(pphead);
    38. 	SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点
    39.  
    40. 	SLNode* cur = *pphead; //让cur指向phead所指向空间
    41. 	if (cur == NULL) //cur == NULL代表着phead指向NULL， 这时候让phead改变指向。传送phead指针的原因就是
    42. 	{                                              //要改变phead的指向。
    43. 		*pphead = newnode;//
    44. 	}
    45. 	else 
    46. 	{
    47. 		while (cur->next != NULL) //让cur遍历到最后一个节点
    48. 		{
    49. 			cur = cur->next;
    50. 		}
    51. 		cur->next = newnode;//最后
    52. 	}
    53.  
    54. }
    55.  
    56. //单链表头插函数接口
    57. void SListPushFront(SLNode** pphead, SLTDataType x) 
    58. {
    59. 	assert(pphead);
    60. 	SLNode* newnode = BuySListNode(x);
    61. 	//
    62. 	SLNode* cur = *pphead;
    63. 	newnode->next = cur;
    64. 	*pphead = newnode;
    65.  
    66. }
    67.  
    68. //单链表尾删函数接口
    69. void SListPopBack(SLNode** pphead) 
    70. {
    71. 	assert(pphead);
    72. 	if (*pphead == NULL)
    73. 		return;
    74. 	//
    75. 	SLNode* cur = *pphead;
    76. 	SLNode* prev = *pphead;
    77. 	while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表
    78. 	{
    79. 		prev = cur;
    80. 		cur = cur->next;
    81. 	}
    82. 	if (prev == cur) 
    83. 	{
    84. 		free(cur);
    85. 		*pphead = NULL;
    86. 	}
    87. 	else 
    88. 	{
    89. 		free(cur);
    90. 		prev = NULL;
    91. 	}
    92. 	
    93. }
    94.  
    95. //单链表的头删函数接口
    96. void SListPopFront(SLNode** pphead) 
    97. {
    98. 	assert(pphead);
    99. 	if (*pphead == NULL)
    100. 		return;
    101. 	//
    102. 	SLNode* cur = *pphead;
    103. 	*pphead = cur->next;
    104. 	free(cur);
    105. }

    代码的意思是， 首先pphead不能为空， 然后phead不能指向空。 然后让一个cur指针指向头节点。 然后修改phead的指向， 使其指向第二个节点（当第二个节点是空的时候， 就是指向空）。然后释放cur指向的节点也就是头节点。 如图为过程：

    ---------------------------------------------------------------------------------------------------------------------------------

     单链表查找函数接口

    .h接口声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);

    .c接口实现

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }
    33.  
    34. //单链表尾插函数接口
    35. void SListPushBack(SLNode** pphead, SLTDataType x) 
    36. {
    37. 	assert(pphead);
    38. 	SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点
    39.  
    40. 	SLNode* cur = *pphead; //让cur指向phead所指向空间
    41. 	if (cur == NULL) //cur == NULL代表着phead指向NULL， 这时候让phead改变指向。传送phead指针的原因就是
    42. 	{                                              //要改变phead的指向。
    43. 		*pphead = newnode;//
    44. 	}
    45. 	else 
    46. 	{
    47. 		while (cur->next != NULL) //让cur遍历到最后一个节点
    48. 		{
    49. 			cur = cur->next;
    50. 		}
    51. 		cur->next = newnode;//最后
    52. 	}
    53.  
    54. }
    55.  
    56. //单链表头插函数接口
    57. void SListPushFront(SLNode** pphead, SLTDataType x) 
    58. {
    59. 	assert(pphead);
    60. 	SLNode* newnode = BuySListNode(x);
    61. 	//
    62. 	SLNode* cur = *pphead;
    63. 	newnode->next = cur;
    64. 	*pphead = newnode;
    65.  
    66. }
    67.  
    68. //单链表尾删函数接口
    69. void SListPopBack(SLNode** pphead) 
    70. {
    71. 	assert(pphead);
    72. 	if (*pphead == NULL)
    73. 		return;
    74. 	//
    75. 	SLNode* cur = *pphead;
    76. 	SLNode* prev = *pphead;
    77. 	while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表
    78. 	{
    79. 		prev = cur;
    80. 		cur = cur->next;
    81. 	}
    82. 	if (prev == cur) 
    83. 	{
    84. 		free(cur);
    85. 		*pphead = NULL;
    86. 	}
    87. 	else 
    88. 	{
    89. 		free(cur);
    90. 		prev = NULL;
    91. 	}
    92. 	
    93. }
    94.  
    95. //单链表的头删函数接口
    96. void SListPopFront(SLNode** pphead) 
    97. {
    98. 	assert(pphead);
    99. 	if (*pphead == NULL)
    100. 		return;
    101. 	//
    102. 	SLNode* cur = *pphead;
    103. 	*pphead = cur->next;
    104. 	free(cur);
    105. }
    106.  
    107.  
    108. //单链表查找函数接口
    109. SLNode* SListFind(SLNode* phead, SLTDataType x) 
    110. {
    111. 	SLNode* cur = phead;//定义一个指向头节点的指针， 用于遍历
    112. 	while (cur != NULL) //向后遍历
    113. 	{
    114. 		if (cur->data == x) //找到节点后就返回节点的地址。
    115. 		{
    116. 			return cur;
    117. 		}
    118. 		cur = cur->next;
    119. 	}
    120. 	return NULL;
    121. }

     代码太长， 之后.c文件的代码只展示相应接口的代码

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表pos位置之后插入数据接口

    .h接口声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);
    30. //单链表在pos位置之后插入数据接口
    31. void SListInsertAfter(SLNode* pos, SLTDataType x);

    .c接口实现 

    1.  
    2. //单链表在pos位置之后插入数据接口
    3. void SListInsertAfter(SLNode* pos, SLTDataType x) 
    4. {
    5. 	assert(pos);
    6. 	SLNode* newnode = BuySListNode(x);
    7. 	//
    8. 	SLNode* cur = pos->next;
    9. 	newnode->next = cur;
    10. 	pos->next = newnode;
    11. }

     该接口的实现过程如下：

    令指针cur指向pos的下一个节点， newnode的next指向cur， pos的next指向newnode

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表删除pos之后位置的数据

    .h接口声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);
    30. //单链表在pos位置之后插入数据接口
    31. void SListInsertAfter(SLNode* pos, SLTDataType x);
    32. //单链表在pos之后的位置删除数据
    33. void SListPopAfter(SLNode* pos);

    .c接口实现

    1.  
    2. //单链表在pos之后的位置删除数据
    3. void SListPopAfter(SLNode* pos) 
    4. {
    5. 	assert(pos);
    6. 	//
    7. 	SLNode* cur = pos->next;
    8. 	pos->next = pos->next->next;
    9. 	free(cur);
    10. }

    该接口实现和单链表在pos位置之后插入数据接口实现方式类似， 都是利用一个cur指针指向pos之后的位置作为记忆保存，然后进行插入或者删除操作。 

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表在pos位置之前插入数据接口

    该接口的实现有点复杂， 但是实现该接口之后， 对于尾插还有头插就很好实现了， 尾插和头插是该接口的两个特殊情况。 假如pos是头节点，就是头插， 假如pos是尾节点， 就是尾插。

    .h接口声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);
    30. //单链表在pos位置之后插入数据接口
    31. void SListInsertAfter(SLNode* pos, SLTDataType x);
    32. //单链表在pos之后的位置删除数据
    33. void SListPopAfter(SLNode* pos);
    34. //单链表在pos位置之前插入数据接口
    35. void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);

    .c接口实现

    1.  
    2. //单链表在pos位置之前插入数据接口
    3. void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) 
    4. {
    5. 	assert(pphead);
    6.  
    7. 	//
    8. 	SLNode* newnode = BuySListNode(x);
    9. 	//
    10. 	if (*pphead == NULL) 
    11. 	{
    12. 		*pphead = newnode;
    13. 		return;
    14. 	}
    15. 	//
    16. 	if (*pphead == pos) 
    17. 	{
    18. 		newnode->next = pos;
    19. 		*pphead = newnode;
    20. 		return;
    21. 	}
    22. 	SLNode* cur = *pphead;
    23. 	while (cur != NULL && cur->next != pos) 
    24. 	{
    25. 		cur = cur->next;
    26. 	}
    27. 	newnode->next = pos;
    28. 	cur->next = newnode;
    29. }

    该接口分为三种情况：

    第一种是链表为空， 这个时候直接插入节点。

    第二种情况是pos的位置在第一个节点的位置， 这个时候需要改变phead的指向。 

    第三种情况就是最普通的情况， 在除头节点， 链表的任意节点前插入。如图：

     

    ---------------------------------------------------------------------------------------------------------------------------------

    单链表删除pos位置数据接口

    和pos位置插入数据接口一样， 实现了该接口对于尾删， 头删接口就很简单了。 头删， 尾删都是单链表删除pos位置数据接口的特殊情况。 pos是头节点， 就是头删， pos是尾节点。 就是尾删。 

    .h接口声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);
    30. //单链表在pos位置之后插入数据接口
    31. void SListInsertAfter(SLNode* pos, SLTDataType x);
    32. //单链表在pos之后的位置删除数据
    33. void SListPopAfter(SLNode* pos);
    34. //单链表在pos位置之前插入数据接口
    35. void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
    36. //单链表在pos位置删除数据接口
    37. void SListPop(SLNode** pphead, SLNode* pos);

    .c接口实现

    1.  
    2. //单链表在pos位置删除数据接口
    3. void SListPop(SLNode** pphead, SLNode* pos) 
    4. {
    5. 	assert(pphead);
    6. 	//
    7. 	if (*pphead == pos) 
    8. 	{
    9. 		*pphead = (*pphead)->next;
    10. 		free(pos);
    11. 	}
    12. 	else 
    13. 	{
    14. 		SLNode* cur = *pphead;
    15. 		while (cur->next != pos) 
    16. 		{
    17. 			cur->next = pos->next;
    18. 			free(pos);
    19. 		}
    20. 	}
    21. }

    pos位置删除分两种情况

    一种是头删， 需要phead改变指向。

     一种是其他位置删除节点

    单链表的销毁

     链表使用完之后应该销毁， 放置内存泄漏

    .h接口声明

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);
    30. //单链表在pos位置之后插入数据接口
    31. void SListInsertAfter(SLNode* pos, SLTDataType x);
    32. //单链表在pos之后的位置删除数据
    33. void SListPopAfter(SLNode* pos);
    34. //单链表在pos位置之前插入数据接口
    35. void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
    36. //单链表在pos位置删除数据接口
    37. void SListPop(SLNode** pphead, SLNode* pos);
    38. //单链表的销毁函数接口
    39. void SLTDestory(SLNode** pphead);

    .c接口实现 

    1.  
    2. //单链表的销毁函数接口
    3. void SLTDestory(SLNode** pphead) 
    4. {
    5. 	assert(pphead);
    6. 	if (*pphead == NULL) 
    7. 	{
    8. 		return;
    9. 	}
    10. 	SLNode* prev = (*pphead);
    11. 	SLNode* cur = (*pphead)->next;
    12. 	if (cur == NULL) 
    13. 	{
    14. 		*pphead = NULL;
    15. 		free(prev);
    16. 	}
    17. 	else 
    18. 	{
    19. 		*pphead = NULL;
    20. 		while(cur != NULL)
    21. 		{
    22. 			free(prev);
    23. 			prev = cur;
    24. 			cur = cur->next;
    25. 		}
    26. 		free(prev);
    27. 	}
    28.  
    29. }

    销毁需要一步一步的进行， 如下图：

    现在来看一下总体代码：

    .h文件

    1. 链表的增删查改///
    2. #include
    3. #include
    4. #include
    5.  
    6. typedef int SLTDataType;
    7.  
    8. typedef struct SListNode 
    9. {
    10. 	struct SListNode* next;
    11. 	SLTDataType data;
    12. }SLNode;
    13.  
    14. //链表接口声明/
    15.  
    16. //申请链表节点函数接口
    17. SLNode* BuySListNode(SLTDataType x);
    18. //单链表的打印函数接口
    19. void SListPrint(SLNode* phead);
    20. //单链表尾插函数接口
    21. void SListPushBack(SLNode** pphead, SLTDataType x);
    22. //单链表头插函数接口
    23. void SListPushFront(SLNode** pphead, SLTDataType x);
    24. //单链表尾删函数接口
    25. void SListPopBack(SLNode** pphead);
    26. //单链表的头删函数接口
    27. void SListPopFront(SLNode** pphead);
    28. //单链表查找函数接口
    29. SLNode* SListFind(SLNode* phead, SLTDataType x);
    30. //单链表在pos位置之后插入数据接口
    31. void SListInsertAfter(SLNode* pos, SLTDataType x);
    32. //单链表在pos之后的位置删除数据
    33. void SListPopAfter(SLNode* pos);
    34. //单链表在pos位置之前插入数据接口
    35. void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);
    36. //单链表在pos位置删除数据接口
    37. void SListPop(SLNode** pphead, SLNode* pos);
    38. //单链表的销毁函数接口
    39. void SLTDestory(SLNode** pphead);

    .c文件

    1. 单链表函数实现函数接口
    2.  
    3. //单链表申请节点函数接口
    4. SLNode* BuySListNode(SLTDataType x) 
    5. {
    6. 	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
    7. 	if (NewNode == NULL) 
    8. 	{
    9. 		printf("申请节点失败\n");
    10. 		return;
    11. 	}
    12. 	//
    13. 	NewNode->data = x;
    14. 	NewNode->next = NULL;
    15. }
    16.  
    17. //单链表的节点打印操作
    18. void SListPrint(SLNode* phead) 
    19. {
    20. 	SLNode* cur = phead;
    21.  
    22. 	while (cur != NULL) 
    23. 	{
    24. 		printf("%d->", cur->data);
    25. 		cur = cur->next;
    26. 	}
    27. 	if (cur == NULL)//最后打印一个NULL
    28. 	{
    29. 		printf("NULL");
    30. 	}
    31. 	
    32. }
    33.  
    34. //单链表尾插函数接口
    35. void SListPushBack(SLNode** pphead, SLTDataType x) 
    36. {
    37. 	assert(pphead);
    38. 	SLNode* newnode = BuySListNode(x);//利用申请节点函数申请节点
    39.  
    40. 	SLNode* cur = *pphead; //让cur指向phead所指向空间
    41. 	if (cur == NULL) //cur == NULL代表着phead指向NULL， 这时候让phead改变指向。传送phead指针的原因就是
    42. 	{                                              //要改变phead的指向。
    43. 		*pphead = newnode;//
    44. 	}
    45. 	else 
    46. 	{
    47. 		while (cur->next != NULL) //让cur遍历到最后一个节点
    48. 		{
    49. 			cur = cur->next;
    50. 		}
    51. 		cur->next = newnode;//最后
    52. 	}
    53.  
    54. }
    55.  
    56. //单链表头插函数接口
    57. void SListPushFront(SLNode** pphead, SLTDataType x) 
    58. {
    59. 	assert(pphead);
    60. 	SLNode* newnode = BuySListNode(x);
    61. 	//
    62. 	SLNode* cur = *pphead;
    63. 	newnode->next = cur;
    64. 	*pphead = newnode;
    65.  
    66. }
    67.  
    68. //单链表尾删函数接口
    69. void SListPopBack(SLNode** pphead) 
    70. {
    71. 	assert(pphead);
    72. 	if (*pphead == NULL)
    73. 		return;
    74. 	//
    75. 	SLNode* cur = *pphead;
    76. 	SLNode* prev = *pphead;
    77. 	while (cur->next != NULL) //对链表进行遍历。 cur最终会指向尾节点。 prev用来维护链表
    78. 	{
    79. 		prev = cur;
    80. 		cur = cur->next;
    81. 	}
    82. 	if (prev == cur) 
    83. 	{
    84. 		free(cur);
    85. 		*pphead = NULL;
    86. 	}
    87. 	else 
    88. 	{
    89. 		free(cur);
    90. 		prev = NULL;
    91. 	}
    92. 	
    93. }
    94.  
    95. //单链表的头删函数接口
    96. void SListPopFront(SLNode** pphead) 
    97. {
    98. 	assert(pphead);
    99. 	if (*pphead == NULL)
    100. 		return;
    101. 	//
    102. 	SLNode* cur = *pphead;
    103. 	*pphead = cur->next;
    104. 	free(cur);
    105. }
    106.  
    107.  
    108. //单链表查找函数接口
    109. SLNode* SListFind(SLNode* phead, SLTDataType x) 
    110. {
    111. 	SLNode* cur = phead;//定义一个指向头节点的指针， 用于遍历
    112. 	while (cur != NULL) //向后遍历
    113. 	{
    114. 		if (cur->data == x) //找到节点后就返回节点的地址。
    115. 		{
    116. 			return cur;
    117. 		}
    118. 		cur = cur->next;
    119. 	}
    120. 	return NULL;
    121. }
    122.  
    123. //单链表在pos位置之后插入数据接口
    124. void SListInsertAfter(SLNode* pos, SLTDataType x) 
    125. {
    126. 	assert(pos);
    127. 	SLNode* newnode = BuySListNode(x);
    128. 	//
    129. 	SLNode* cur = pos->next;
    130. 	newnode->next = cur;
    131. 	pos->next = newnode;
    132. }
    133.  
    134.  
    135. //单链表在pos之后的位置删除数据
    136. void SListPopAfter(SLNode* pos) 
    137. {
    138. 	assert(pos);
    139. 	//
    140. 	SLNode* cur = pos->next;
    141. 	pos->next = pos->next->next;
    142. 	free(cur);
    143. }
    144.  
    145. //单链表在pos位置之前插入数据接口
    146. void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) 
    147. {
    148. 	assert(pphead);
    149.  
    150. 	//
    151. 	SLNode* newnode = BuySListNode(x);
    152. 	//
    153. 	if (*pphead == NULL) 
    154. 	{
    155. 		*pphead = newnode;
    156. 		return;
    157. 	}
    158. 	//
    159. 	if (*pphead == pos) 
    160. 	{
    161. 		newnode->next = pos;
    162. 		*pphead = newnode;
    163. 		return;
    164. 	}
    165. 	SLNode* cur = *pphead;
    166. 	while (cur != NULL && cur->next != pos) 
    167. 	{
    168. 		cur = cur->next;
    169. 	}
    170. 	newnode->next = pos;
    171. 	cur->next = newnode;
    172. }
    173.  
    174. //单链表在pos位置删除数据接口
    175. void SListPop(SLNode** pphead, SLNode* pos) 
    176. {
    177. 	assert(pphead);
    178. 	//
    179. 	if (*pphead == pos) 
    180. 	{
    181. 		*pphead = (*pphead)->next;
    182. 		free(pos);
    183. 	}
    184. 	else 
    185. 	{
    186. 		SLNode* cur = *pphead;
    187. 		while (cur->next != pos) 
    188. 		{
    189. 			cur->next = pos->next;
    190. 			free(pos);
    191. 		}
    192. 	}
    193. }
    194.  
    195. //单链表的销毁函数接口
    196. void SLTDestory(SLNode** pphead) 
    197. {
    198. 	assert(pphead);
    199. 	if (*pphead == NULL) 
    200. 	{
    201. 		return;
    202. 	}
    203. 	SLNode* prev = (*pphead);
    204. 	SLNode* cur = (*pphead)->next;
    205. 	if (cur == NULL) 
    206. 	{
    207. 		*pphead = NULL;
    208. 		free(prev);
    209. 	}
    210. 	else 
    211. 	{
    212. 		*pphead = NULL;
    213. 		while(cur != NULL)
    214. 		{
    215. 			free(prev);
    216. 			prev = cur;
    217. 			cur = cur->next;
    218. 		}
    219. 		free(prev);
    220. 	}
    221.  
    222. }

  • 相关阅读:
    MySQL 8.0 Clone Plugin 详解
    skywalking--链路追踪
    31.JavaScript数组进阶，一网打尽数组操作函数slice、filter、map、reduce、some、every、find、splice
    Allatori工具混淆jar包class
    基于图搜索的规划算法之 A* 家族（八）：Theta* 算法
    Python之作业（一）
    Machine Learning（一）KNN算法
    测试 C、Python、Java 等 16 种编程语言的 Hello World：7 种存在 Bug？
    若依3.6.0使用Mybatis-plus分页失效以及完美替换Pagehelper【已解决】
    HarmonyOS入门开发(二) Toast使用
  • 原文地址：https://blog.csdn.net/strive_mianyang/article/details/136751789