devbox
凡人多烦事01
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

单向链表的基本操作（常见面试题详解）_单项列表克服了数组的什么缺陷

作者：凡人多烦事01 | 2024-05-07 11:34:44

赞

踩

单项列表克服了数组的什么缺陷
一、什么是链表
     链表是一种常见的非常重要的数据结构，是动态进行存储分配的一种结构。其中数据元素的逻辑顺序是通过链表中的指针链接次序实现的，链表中的每一个元素都称为结点，链表就是由这一系列结点组成的，其结点可在运行时动态生成。每一个结点都是由两部分组成，一部分是存储数据元素的数据域，另一部分是存储下一结点地址的指针域。
    链表的类型有：单向链表、双向链表、循环链表。
    链表的优点：1、克服了数组预先知道数据大小的缺点；
                          2、动态管理内存空间，可充分利用内存空间；
                          3、可插入和移除表上任意位置的结点。
    链表的缺点：1、增加了指针域，空间开销大；
                          2、不能随机读取数据。
二、单向链表的基本操作
1、头插：从链表首部插入结点，只需要创建一块内存空间，将数据放进数据域，将原链表的首元素地址放进新创建的指针域当中。 
  1. void Pushfront(pList* plist, Datatype data)
  2. {
  3. 	assert(plist != NULL);
  4. 	pNode p = NULL;
  5. 	p =(pNode) malloc(sizeof(node_t));
  6. 	if (p == NULL)
  7. 	{
  8. 		perror("malloc()");
  9. 		exit(EXIT_FAILURE);
  10. 	}
  11. 	p->data = data;
  12. 	p->next = NULL;
  13. 	p->next = *plist;
  14. 	*plist = p;
  15. }
2、尾插：从链表尾部插入结点，需要创建一块内存空间，将地址放进原链表尾部的结点的指针域当中，然后将指针域制空即可。 
  1. void Pushback(pList* plist,Datatype data)
  2. {
  3. 	assert(plist != NULL);
  4. 	pNode cur = *plist;
  5. 	pNode p = NULL;
  6. 	p =(pNode) malloc(sizeof(node_t));
  7. 	if (p == NULL)
  8. 	{
  9. 		perror("malloc()");
  10. 		exit(EXIT_FAILURE);
  11. 	}
  12. 	memset(p, 0, sizeof(node_t));
  13. 	p->data = data;
  14. 	if (cur == NULL)
  15. 	{
  16. 		*plist = p;
  17. 	}
  18. 	else
  19. 	{
  20. 		while (cur->next)
  21. 		{
  22. 			cur = cur->next;
  23. 		}
  24. 		cur->next = p;
  25. 	}
  26. }
3、头删：释放掉第一个结点，头指针指向下一个结点，即可。 
  1. void Popfront(pList* plist)
  2. {
  3. 	assert(plist != NULL);
  4. 	pList cur = *plist;
  5. 	if (cur == NULL)
  6. 	{
  7. 		return;
  8. 	}
  9. 	else
  10. 	{
  11. 		*plist = cur->next;
  12. 		free(cur);
  13. 		cur->next = NULL;
  14. 	}
  15. }
4、尾删：释放掉最后一个结点，将倒数第二个结点的指针置为空指针。 
  1. void Popback(pList* plist)
  2. {
  3. 	assert(plist != NULL);
  4. 	pList fast = *plist;
  5. 	pList slow = NULL;
  6. 	if (*plist == NULL)
  7. 	{
  8. 		return;
  9. 	}
  10. 	while (fast!=NULL)
  11. 	{
  12. 		slow = fast;
  13. 		fast = fast->next;
  14. 	}
  15. 	if (slow != NULL)
  16. 	{
  17. 		slow->next = NULL;
  18. 		free(fast);
  19. 	}
  20. 	else
  21. 	{
  22. 		free(fast);
  23. 		*plist = NULL;
  24. 	}
  25. }
5、销毁链表：逐个释放结点所占的内存空间。 
  1. void Destroy(pList* plist)
  2. {
  3. 	assert(plist != NULL);
  4. 	pList cur = NULL;
  5. 	while (*plist)
  6. 	{
  7. 		cur = (*plist)->next;
  8. 		free(*plist);
  9. 		*plist = NULL;
  10. 		*plist = cur;
  11. 	}
  12. }
6、查找某一个结点。 
  1. pNode Find(pList plist, Datatype data)
  2. {
  3. 	pNode cur =plist;
  4. 	while (cur)
  5. 	{
  6. 		if (cur->data == data)
  7. 		{
  8. 			return cur;
  9. 		}
  10. 		cur = cur->next;
  11. 	}
  12. 	return NULL;
  13. }
7、链表的逆序：遍历一遍链表，将链表里每个结点的指针域里存放的地址更改为其上一个结点的地址，并将原链表的第一个结点的指针域存放空指针。 
  1. void Invert_list(pList *plist)
  2. {
  3. 	if (((*plist) == NULL) || ((*plist)->next == NULL))
  4. 	{
  5. 		return;
  6. 	}
  7. 	else
  8. 	{
  9. 		pList cur1 = *plist;
  10. 		pList cur2 = (*plist)->next;
  11. 		pList cur3 = (*plist)->next->next;
  12. 		pList tmp = NULL;
  13. 		while (1)
  14. 		{
  15. 			cur2->next = cur1;
  16. 			cur1->next = tmp;
  17. 			tmp = cur1;
  18. 			if (cur3 == NULL)
  19. 			{
  20. 				break;
  21. 			}
  22. 			else
  23. 			{
  24. 				cur1 = cur2;
  25. 				cur2 = cur3;
  26. 				cur3 = cur3->next;
  27. 			}
  28. 		}
  29. 		*plist = cur2;
  30. 	}
  31. }
8、顺序打印链表 
  1. void Display(pList plist)
  2. {
  3. 	pList cur = plist;
  4. 	for (; cur != NULL; cur = cur->next)
  5. 	{
  6. 		printf("%d--->", cur->data);
  7. 	}
  8. 	printf("over\n");
  9. }
  10.  
  11.
9、逆序打印链表：最简便的方法莫过于递归实现。 
  1. void Invert_display(pList plist)
  2. {
  3. 	if(plist!=NULL)
  4. 	{
  5. 		Invert_display(plist->next);
  6. 		printf("%d--->", plist->data);
  7. 	}
  8. 	else
  9. 	{
  10. 		return;
  11. 	}
  12. }
10、删除一个非尾结点：找到要删除的结点的下一个结点，将该节点的内容放进要删除的结点中，释放该结点。 


  1. void Del_Not_Tail(pNode pos)
  2. {
  3. 	assert(pos != NULL);
  4. 	pNode cur = pos->next;
  5. 	if (cur != NULL)
  6. 	{
  7. 		pos->next = cur->next;
  8. 		pos->data = cur->data;
  9. 	}
  10. 	else
  11. 	{
  12. 		return;
  13. 	}
  14. 	free(cur);
  15. 	cur = NULL;
  16. }
11、在指定位置前插入一个结点：创建一个结点，将该结点插入到指定位置后，然后将指定位置的数据放入创建的结点中，指定位置的数据域存放需要新加入的数据。 



  1. void Insert_Front_Node(pNode pos, Datatype data)
  2. {
  3. 	assert(pos != NULL);
  4. 	pNode p = NULL;
  5. 	p = (pNode)malloc(sizeof(node_t));
  6. 	if (p == NULL)
  7. 	{
  8. 		perror("malloc()");
  9. 		exit(EXIT_FAILURE);
  10. 	}
  11. 	p->next = pos->next;
  12. 	p->data = pos->data;
  13. 	pos->data = data;
  14. 	pos->next = p;
  15. }
12、合并有序链表 
  1. pList Merge(pList* plist1, pList* plist2)
  2. {
  3. 	assert(plist1 != NULL);
  4. 	assert(plist2 != NULL);
  5. 	pList head = NULL;
  6. 	pList p = NULL;
  7. 	pList cur1 = *plist1;
  8. 	pList cur2 = *plist2;
  9. 	if (cur1->data < cur2->data)
  10. 	{
  11. 		head = cur1;
  12. 		cur1 = cur1->next;
  13. 	}
  14. 	else
  15. 	{
  16. 		head = cur2;
  17. 		cur2 = cur2->next;
  18. 	}
  19. 	p = head;
  20. 	while ((cur1 != NULL) && (cur2 != NULL))
  21. 	{
  22. 		if (cur1->data < cur2->data)
  23. 		{
  24. 			p->next = cur1;
  25. 			cur1 = cur1->next;
  26. 		}
  27. 		else
  28. 		{
  29. 			p->next = cur2;
  30. 			cur2 = cur2->next;
  31. 		}
  32. 		p = p->next;
  33. 	}
  34. 	if (cur1 == NULL)
  35. 	{
  36. 		p->next = cur2;
  37. 	}
  38. 	else if (cur2 == NULL)
  39. 	{
  40. 		p->next = cur1;
  41. 	}
  42. 	return head;
  43. }
13、约瑟夫环问题：一共有n个人，开始报数，报到第k个的人自杀，然后从下一个继续报数，问最后自杀的人是谁？
        通过链表，我们不仅可以找出最后自杀的人，还可以将n个人自杀的顺序找出来。遍历链表，利用计数器，每数到k,就将此时指针所指向的结点释放，将下一个结点挂到上一个节点上。 
  1. void JosephCycle(pList plist, int k)
  2. {
  3. 	pList cur1 = plist;
  4. 	pList cur2 = plist;
  5. 	
  6. 	if (k >= 2)
  7. 	{
  8. 		while (1)
  9. 		{
  10. 			int count = k;
  11. 			pNode tmp = NULL;
  12. 			if (cur1 == cur1->next)
  13. 			{
  14. 				printf("%d\n", cur1->data);
  15. 				break;
  16. 			}
  17. 			while (--count > 0)
  18. 			{
  19. 				cur1 = cur2;
  20. 				cur2 = cur2->next;
  21. 			}
  22. 			tmp = cur2;
  23. 			printf("%d  ", tmp->data);
  24. 			cur1->next = cur2->next;
  25. 			cur2 = cur2->next;
  26. 			free(tmp);
  27. 			tmp = NULL;
  28. 		}
  29. 	}
  30. 	else
  31. 	{
  32. 		return;
  33. 	}
  34. }
14、寻找链表的中间结点，要求只能遍历一次链表：用两个指针同时指向链表首部，利用循环，快指针一次走两步，慢指针一次走一步，直到快的指针走到链表尾部，此时慢的指针指向的结点就是中间结点。 
  1. pNode Find_Mid_Node(pList plist)
  2. {
  3. 	pList fast = plist;
  4. 	pList slow = plist;
  5. 	
  6. 	while (fast != NULL&&fast->next != NULL)
  7. 	{
  8. 		fast = fast->next->next;
  9. 		slow = slow->next;
  10. 	}
  11.  
  12. 	printf("中间结点为：%d\n", slow->data);
  13. 	return slow;
  14. }
15、对链表进行冒泡排序。 
  1. void BubbleSort(pList plist)
  2. {
  3. 	pList cur = plist;
  4.  
  5. 	if (plist == NULL || plist->next == NULL)
  6. 	{
  7. 		return;
  8. 	}
  9.  
  10. 	for (; cur->next != NULL; cur = cur->next)
  11. 	{
  12. 		pList pre = plist;
  13. 		Datatype tmp = 0;
  14. 		for (pre ; pre->next != NULL; pre = pre->next)
  15. 		{
  16. 			if (pre->data > pre->next->data)
  17. 			{
  18. 				tmp=pre->data;
  19. 				pre->data = pre->next->data;
  20. 				pre->next->data = tmp;
  21. 			}
  22. 		}
  23. 	}
  24. }
16、删除倒数第k个元素：两个指针，快的指针先遍历k个结点，然后快慢指针同时走，每次遍历一个结点，知道快指针走到链表尾部，此时慢指针指向的结点就是倒数第k个结点。 
  1. void Del_K_Node(pList plist, int k)
  2. {
  3. 	pList cur1 = plist;
  4. 	pList cur2 = plist;
  5. 	int count = k;
  6.  
  7. 	if (k == 1)
  8. 	{
  9. 		cur1 = cur1->next;
  10. 		while (cur1->next != NULL)
  11. 		{
  12. 			cur1 = cur1->next;
  13. 			cur2 = cur2->next;
  14. 		}
  15. 		cur2->next = NULL;
  16. 		free(cur1);
  17. 		cur1 = NULL;
  18. 	}
  19. 	else if (k >= 2)
  20. 	{
  21. 		while (--count)
  22. 		{
  23. 			cur1 = cur1->next;
  24. 		}
  25. 		pList tmp = NULL;
  26. 		while (cur1->next != NULL)
  27. 		{
  28. 			cur1 = cur1->next;
  29. 			cur2 = cur2->next;
  30. 		}
  31. 		tmp = cur2->next;
  32. 		cur2->data = tmp->data;
  33. 		cur2->next = tmp->next;
  34. 		free(tmp);
  35. 		tmp = NULL;
  36. 	}
  37. 	else
  38. 	{
  39. 		return;
  40. 	}
  41. }
17、判断链表是否带环：两个指针，快指针每次走两步，慢指针每次走一步，当两个指针相遇，说明链表带环，否则，链表不带环。 
  1. pNode Check_Cycle(pList plist)
  2. {
  3. 	pList fast = plist;
  4. 	pList slow = plist;
  5.  
  6. 	while ((fast != NULL) && (fast->next != NULL))
  7. 	{
  8. 		fast = fast->next->next;
  9. 		slow = slow->next;
  10. 		if (fast == slow)
  11. 		{
  12. 			return fast;
  13. 		}
  14. 	}
  15. 	return NULL;
  16. }
18、求带环链表的入口点（此问题后续详解）。 
  1. pNode Get_Circle_Entry_Node(pNode meet, pList plist)
  2. {
  3. 	assert(meet != NULL);
  4. 	assert(plist != NULL);
  5.  
  6. 	pList cur = plist;
  7. 	pNode node = meet;
  8. 	while (cur != node)
  9. 	{
  10. 		cur = cur->next;
  11. 		node = node->next;
  12. 	}
  13. 	return cur;
  14. }
19、求带环链表的长度。 
  1. int Get_Circle_Length(pNode meet)
  2. {
  3. 	pNode node = meet;
  4. 	Datatype count = 1;
  5.  
  6. 	meet = meet->next;
  7. 	while (meet != node)
  8. 	{
  9. 		meet = meet->next;
  10. 		count += 1;
  11. 	}
  12. 	return count;
  13. }
20、判断两个不带环链表是否相交：只需判断两条链表的尾结点是否相同即可。 
  1. pNode Check_Cross(pList plist1, pList plist2)
  2. {
  3. 	assert(plist1 != NULL);
  4. 	assert(plist2 != NULL);
  5.  
  6. 	pList cur1 = plist1;
  7. 	pList cur2 = plist2;
  8.  
  9. 	while (cur1->next != NULL)
  10. 	{
  11. 		cur1 = cur1->next;
  12. 	}
  13. 	while (cur2->next != NULL)
  14. 	{
  15. 		cur2 = cur2->next;
  16. 	}
  17. 	if (cur1 == cur2)
  18. 	{
  19. 		return cur1;
  20. 	}
  21. 	else
  22. 	{
  23. 		return NULL;
  24. 	}
  25. }
21、求两个相交不带环链表的交点：将其中一条链表构成环，即就成了求环入口点问题。 
  1. pNode Check_Cross_Meet(pList plist1, pList plist2)
  2. {
  3. 	pList cur1 = plist1;
  4. 	pList cur2 = plist2;
  5. 	pNode meet = NULL;
  6. 	pNode pre = NULL;
  7. 	pNode node = Check_Cross(plist1, plist2);//判断两条链表是否相交
  8.  
  9. 	if (node == NULL)
  10. 	{
  11. 		return NULL;
  12. 	}
  13. 	node->next = cur1;//将其中一条链表的尾节点接到头结点，构成一个环
  14. 	meet = Check_Cycle(plist2);//判断链表2是否已经带环
  15. 	pre = Get_Circle_Entry_Node(meet, plist2);//求出环的入口点
  16. 	node->next = NULL;//将环拆开
  17. 	return pre;
  18. }
三、完整代码如下：
Linklist.h 
  1. #ifndef __LINK_LIST_H__
  2. #define __LINK_LIST_H__
  3.  
  4. #include <stdio.h>
  5. #include <string.h>
  6. #include <stdlib.h>
  7. #include <assert.h>
  8.  
  9. typedef int Datatype;
  10.  
  11. typedef struct Node
  12. {
  13. 	Datatype data;
  14. 	struct Node *next;
  15. }node_t,*pList,*pNode;
  16.  
  17. void Initlist(pList* plist);//初始化
  18.  
  19. void Display(pList plist);//打印链表
  20.  
  21. void Pushfront(pList* plist, Datatype data);//头插
  22.  
  23. void Popfront(pList* plist);//头删
  24.  
  25. void Pushback(pList* plist, Datatype data);//尾插
  26.  
  27. void Popback(pList* plist);//尾删
  28.  
  29. void Destroy(pList* plist);//销毁链表
  30.  
  31. pNode Find(pList plist, Datatype data);//查找某个节点
  32.  
  33. void Invert_list(pList* plist);//链表的逆序
  34.  
  35. void Invert_display(pList plist);//链表的逆序打印
  36.  
  37. void Del_Not_Tail(pNode pos);//删除一个非尾节点
  38.  
  39. void Insert_Front_Node(pNode pos,Datatype data);//在指定位置前插入一个节点
  40.  
  41. pList Merge(pList* plist1, pList* plist2);//合并链表
  42.  
  43. void JosephCycle(pList plist,int k);//约瑟夫环
  44.  
  45. pNode Find_Mid_Node(pList plist);//寻找链表的中间节点，只能遍历一遍链表
  46.  
  47. void BubbleSort(pList plist);//链表进行冒泡排序
  48.  
  49. void Del_K_Node(pList plist, int k);//删除倒数第k个元素
  50.  
  51. pNode Check_Cycle(pList plist);//判断链表是否有环
  52.  
  53. pNode Get_Circle_Entry_Node(pNode meet, pList plist);//求带环链表的环入口点
  54.  
  55. int Get_Circle_Length(pNode meet);//求带环链表长度
  56.  
  57. pNode Check_Cross(pList plist1,pList plist2);//判断两个不带环的链表是否相交
  58.  
  59. pNode Check_Cross_Meet(pList plist1, pList plist2);//求两个相交不带环链表的交点
  60.  
  61.  
  62.  
  63. #endif

Linklist.c 
  1. #include "Linklist.h"
  2.  
  3. //链表的初始化
  4. void Initlist(pList* plist)
  5. {
  6. 	plist = NULL;
  7. }
  8.  
  9. //打印链表
  10. void Display(pList plist)
  11. {
  12. 	pList cur = plist;
  13. 	for (; cur != NULL; cur = cur->next)
  14. 	{
  15. 		printf("%d--->", cur->data);
  16. 	}
  17. 	printf("over\n");
  18. }
  19.  
  20. //头插
  21. void Pushfront(pList* plist, Datatype data)
  22. {
  23. 	assert(plist != NULL);
  24. 	pNode p = NULL;
  25. 	p =(pNode) malloc(sizeof(node_t));
  26. 	if (p == NULL)
  27. 	{
  28. 		perror("malloc()");
  29. 		exit(EXIT_FAILURE);
  30. 	}
  31. 	p->data = data;
  32. 	p->next = NULL;
  33. 	p->next = *plist;
  34. 	*plist = p;
  35. }
  36.  
  37. //头删
  38. void Popfront(pList* plist)
  39. {
  40. 	assert(plist != NULL);
  41. 	pList cur = *plist;
  42. 	if (cur == NULL)
  43. 	{
  44. 		return;
  45. 	}
  46. 	else
  47. 	{
  48. 		*plist = cur->next;
  49. 		free(cur);
  50. 		cur->next = NULL;
  51. 	}
  52. }
  53.  
  54. //尾插
  55. void Pushback(pList* plist,Datatype data)
  56. {
  57. 	assert(plist != NULL);
  58. 	pNode cur = *plist;
  59. 	pNode p = NULL;
  60. 	p =(pNode) malloc(sizeof(node_t));
  61. 	if (p == NULL)
  62. 	{
  63. 		perror("malloc()");
  64. 		exit(EXIT_FAILURE);
  65. 	}
  66. 	memset(p, 0, sizeof(node_t));
  67. 	p->data = data;
  68. 	if (cur == NULL)
  69. 	{
  70. 		*plist = p;
  71. 	}
  72. 	else
  73. 	{
  74. 		while (cur->next)
  75. 		{
  76. 			cur = cur->next;
  77. 		}
  78. 		cur->next = p;
  79. 	}
  80. }
  81.  
  82. //尾删
  83. void Popback(pList* plist)
  84. {
  85. 	assert(plist != NULL);
  86. 	pList fast = *plist;
  87. 	pList slow = NULL;
  88. 	if (*plist == NULL)
  89. 	{
  90. 		return;
  91. 	}
  92. 	while (fast!=NULL)
  93. 	{
  94. 		slow = fast;
  95. 		fast = fast->next;
  96. 	}
  97. 	if (slow != NULL)
  98. 	{
  99. 		slow->next = NULL;
  100. 		free(fast);
  101. 	}
  102. 	else
  103. 	{
  104. 		free(fast);
  105. 		*plist = NULL;
  106. 	}
  107. }
  108.  
  109. //销毁链表
  110. void Destroy(pList* plist)
  111. {
  112. 	assert(plist != NULL);
  113. 	pList cur = NULL;
  114. 	while (*plist)
  115. 	{
  116. 		cur = (*plist)->next;
  117. 		free(*plist);
  118. 		*plist = NULL;
  119. 		*plist = cur;
  120. 	}
  121. }
  122.  
  123. //查找某个结点
  124. pNode Find(pList plist, Datatype data)
  125. {
  126. 	pNode cur =plist;
  127. 	while (cur)
  128. 	{
  129. 		if (cur->data == data)
  130. 		{
  131. 			return cur;
  132. 		}
  133. 		cur = cur->next;
  134. 	}
  135. 	return NULL;
  136. }
  137.  
  138. //链表的逆序
  139. void Invert_list(pList *plist)
  140. {
  141. 	if (((*plist) == NULL) || ((*plist)->next == NULL))
  142. 	{
  143. 		return;
  144. 	}
  145. 	else
  146. 	{
  147. 		pList cur1 = *plist;
  148. 		pList cur2 = (*plist)->next;
  149. 		pList cur3 = (*plist)->next->next;
  150. 		pList tmp = NULL;
  151. 		while (1)
  152. 		{
  153. 			cur2->next = cur1;
  154. 			cur1->next = tmp;
  155. 			tmp = cur1;
  156. 			if (cur3 == NULL)
  157. 			{
  158. 				break;
  159. 			}
  160. 			else
  161. 			{
  162. 				cur1 = cur2;
  163. 				cur2 = cur3;
  164. 				cur3 = cur3->next;
  165. 			}
  166. 		}
  167. 		*plist = cur2;
  168. 	}
  169. }
  170.  
  171. //链表的逆序打印
  172. void Invert_display(pList plist)
  173. {
  174. 	if(plist!=NULL)
  175. 	{
  176. 		Invert_display(plist->next);
  177. 		printf("%d--->", plist->data);
  178. 	}
  179. 	else
  180. 	{
  181. 		return;
  182. 	}
  183. }
  184.  
  185. //删除一个非尾结点
  186. void Del_Not_Tail(pNode pos)
  187. {
  188. 	assert(pos != NULL);
  189. 	pNode cur = pos->next;
  190. 	if (cur != NULL)
  191. 	{
  192. 		pos->next = cur->next;
  193. 		pos->data = cur->data;
  194. 	}
  195. 	else
  196. 	{
  197. 		return;
  198. 	}
  199. 	free(cur);
  200. 	cur = NULL;
  201. }
  202.  
  203. //在指定位置前插入一个结点
  204. void Insert_Front_Node(pNode pos, Datatype data)
  205. {
  206. 	assert(pos != NULL);
  207. 	pNode p = NULL;
  208. 	p = (pNode)malloc(sizeof(node_t));
  209. 	if (p == NULL)
  210. 	{
  211. 		perror("malloc()");
  212. 		exit(EXIT_FAILURE);
  213. 	}
  214. 	p->next = pos->next;
  215. 	p->data = pos->data;
  216. 	pos->data = data;
  217. 	pos->next = p;
  218. }
  219.  
  220. //合并有序链表
  221. pList Merge(pList* plist1, pList* plist2)
  222. {
  223. 	assert(plist1 != NULL);
  224. 	assert(plist2 != NULL);
  225. 	pList head = NULL;
  226. 	pList p = NULL;
  227. 	pList cur1 = *plist1;
  228. 	pList cur2 = *plist2;
  229. 	if (cur1->data < cur2->data)
  230. 	{
  231. 		head = cur1;
  232. 		cur1 = cur1->next;
  233. 	}
  234. 	else
  235. 	{
  236. 		head = cur2;
  237. 		cur2 = cur2->next;
  238. 	}
  239. 	p = head;
  240. 	while ((cur1 != NULL) && (cur2 != NULL))
  241. 	{
  242. 		if (cur1->data < cur2->data)
  243. 		{
  244. 			p->next = cur1;
  245. 			cur1 = cur1->next;
  246. 		}
  247. 		else
  248. 		{
  249. 			p->next = cur2;
  250. 			cur2 = cur2->next;
  251. 		}
  252. 		p = p->next;
  253. 	}
  254. 	if (cur1 == NULL)
  255. 	{
  256. 		p->next = cur2;
  257. 	}
  258. 	else if (cur2 == NULL)
  259. 	{
  260. 		p->next = cur1;
  261. 	}
  262. 	return head;
  263. }
  264.  
  265. //约瑟夫环
  266. void JosephCycle(pList plist, int k)
  267. {
  268. 	pList cur1 = plist;
  269. 	pList cur2 = plist;
  270. 	
  271. 	if (k >= 2)
  272. 	{
  273. 		while (1)
  274. 		{
  275. 			int count = k;
  276. 			pNode tmp = NULL;
  277. 			if (cur1 == cur1->next)
  278. 			{
  279. 				printf("%d\n", cur1->data);
  280. 				break;
  281. 			}
  282. 			while (--count > 0)
  283. 			{
  284. 				cur1 = cur2;
  285. 				cur2 = cur2->next;
  286. 			}
  287. 			tmp = cur2;
  288. 			printf("%d  ", tmp->data);
  289. 			cur1->next = cur2->next;
  290. 			cur2 = cur2->next;
  291. 			free(tmp);
  292. 			tmp = NULL;
  293. 		}
  294. 	}
  295. 	else
  296. 	{
  297. 		return;
  298. 	}
  299. }
  300.  
  301. //寻找链表的中间结点，只遍历一次链表
  302. pNode Find_Mid_Node(pList plist)
  303. {
  304. 	pList fast = plist;
  305. 	pList slow = plist;
  306. 	
  307. 	while (fast != NULL&&fast->next != NULL)
  308. 	{
  309. 		fast = fast->next->next;
  310. 		slow = slow->next;
  311. 	}
  312.  
  313. 	printf("中间结点为：%d\n", slow->data);
  314. 	return slow;
  315. }
  316.  
  317. //链表进行冒泡排序
  318. void BubbleSort(pList plist)
  319. {
  320. 	pList cur = plist;
  321.  
  322. 	if (plist == NULL || plist->next == NULL)
  323. 	{
  324. 		return;
  325. 	}
  326.  
  327. 	for (; cur->next != NULL; cur = cur->next)
  328. 	{
  329. 		pList pre = plist;
  330. 		Datatype tmp = 0;
  331. 		for (pre ; pre->next != NULL; pre = pre->next)
  332. 		{
  333. 			if (pre->data > pre->next->data)
  334. 			{
  335. 				tmp=pre->data;
  336. 				pre->data = pre->next->data;
  337. 				pre->next->data = tmp;
  338. 			}
  339. 		}
  340. 	}
  341. }
  342.  
  343. //删除倒数第k个元素
  344. void Del_K_Node(pList plist, int k)
  345. {
  346. 	pList cur1 = plist;
  347. 	pList cur2 = plist;
  348. 	int count = k;
  349.  
  350. 	if (k == 1)
  351. 	{
  352. 		cur1 = cur1->next;
  353. 		while (cur1->next != NULL)
  354. 		{
  355. 			cur1 = cur1->next;
  356. 			cur2 = cur2->next;
  357. 		}
  358. 		cur2->next = NULL;
  359. 		free(cur1);
  360. 		cur1 = NULL;
  361. 	}
  362. 	else if (k >= 2)
  363. 	{
  364. 		while (--count)
  365. 		{
  366. 			cur1 = cur1->next;
  367. 		}
  368. 		pList tmp = NULL;
  369. 		while (cur1->next != NULL)
  370. 		{
  371. 			cur1 = cur1->next;
  372. 			cur2 = cur2->next;
  373. 		}
  374. 		tmp = cur2->next;
  375. 		cur2->data = tmp->data;
  376. 		cur2->next = tmp->next;
  377. 		free(tmp);
  378. 		tmp = NULL;
  379. 	}
  380. 	else
  381. 	{
  382. 		return;
  383. 	}
  384. }
  385.  
  386. //判断链表是否带环
  387. pNode Check_Cycle(pList plist)
  388. {
  389. 	pList fast = plist;
  390. 	pList slow = plist;
  391.  
  392. 	while ((fast != NULL) && (fast->next != NULL))
  393. 	{
  394. 		fast = fast->next->next;
  395. 		slow = slow->next;
  396. 		if (fast == slow)
  397. 		{
  398. 			return fast;
  399. 		}
  400. 	}
  401. 	return NULL;
  402. }
  403.  
  404. //求带环链表的环入口点
  405. pNode Get_Circle_Entry_Node(pNode meet, pList plist)
  406. {
  407. 	assert(meet != NULL);
  408. 	assert(plist != NULL);
  409.  
  410. 	pList cur = plist;
  411. 	pNode node = meet;
  412. 	while (cur != node)
  413. 	{
  414. 		cur = cur->next;
  415. 		node = node->next;
  416. 	}
  417. 	return cur;
  418. }
  419.  
  420. //求带环链表的长度
  421. int Get_Circle_Length(pNode meet)
  422. {
  423. 	pNode node = meet;
  424. 	Datatype count = 1;
  425.  
  426. 	meet = meet->next;
  427. 	while (meet != node)
  428. 	{
  429. 		meet = meet->next;
  430. 		count += 1;
  431. 	}
  432. 	return count;
  433. }
  434.  
  435. //判断两个不带环链表是否相交
  436. pNode Check_Cross(pList plist1, pList plist2)
  437. {
  438. 	assert(plist1 != NULL);
  439. 	assert(plist2 != NULL);
  440.  
  441. 	pList cur1 = plist1;
  442. 	pList cur2 = plist2;
  443.  
  444. 	while (cur1->next != NULL)
  445. 	{
  446. 		cur1 = cur1->next;
  447. 	}
  448. 	while (cur2->next != NULL)
  449. 	{
  450. 		cur2 = cur2->next;
  451. 	}
  452. 	if (cur1 == cur2)
  453. 	{
  454. 		return cur1;
  455. 	}
  456. 	else
  457. 	{
  458. 		return NULL;
  459. 	}
  460. }
  461.  
  462. //求两个相交不带环链表的交点
  463. pNode Check_Cross_Meet(pList plist1, pList plist2)
  464. {
  465. 	pList cur1 = plist1;
  466. 	pList cur2 = plist2;
  467. 	pNode meet = NULL;
  468. 	pNode pre = NULL;
  469. 	pNode node = Check_Cross(plist1, plist2);//判断两条链表是否相交
  470.  
  471. 	if (node == NULL)
  472. 	{
  473. 		return NULL;
  474. 	}
  475. 	node->next = cur1;//将其中一条链表的尾节点接到头结点，构成一个环
  476. 	meet = Check_Cycle(plist2);//判断链表2是否已经带环
  477. 	pre = Get_Circle_Entry_Node(meet, plist2);//求出环的入口点
  478. 	node->next = NULL;//将环拆开
  479. 	return pre;
  480. }

test.c 
  1. #include "Linklist.h"
  2.  
  3. void test1()//头插  头删  销毁
  4. {
  5. 	pList plist = NULL;
  6. 	Initlist(&plist);
  7. 	Pushfront(&plist, 1);
  8. 	Pushfront(&plist, 2);
  9. 	Pushfront(&plist, 3);
  10. 	Pushfront(&plist, 4);
  11. 	Pushfront(&plist, 5);
  12. 	Display(plist);
  13.  
  14. 	Destroy(&plist);
  15. 	Display(plist);
  16.  
  17. 	/*Popfront(&plist);
  18. 	Display(plist);
  19. 	Popfront(&plist);
  20. 	Display(plist);
  21. 	Popfront(&plist);
  22. 	Display(plist);
  23. 	Popfront(&plist);
  24. 	Display(plist);
  25. 	Popfront(&plist);
  26. 	Display(plist);*/
  27. }
  28.  
  29. void test2()//尾插  尾删
  30. {
  31. 	pList plist = NULL;
  32. 	Initlist(&plist);
  33. 	Pushback(&plist, 1);
  34. 	Pushback(&plist, 2);
  35. 	Pushback(&plist, 3);
  36. 	Pushback(&plist, 4);
  37. 	Pushback(&plist, 5);
  38. 	Display(plist);
  39. 	Popback(&plist);
  40. 	Display(plist);
  41. 	Popback(&plist);
  42. 	Display(plist);
  43. 	Popback(&plist);
  44. 	Display(plist);
  45. 	Popback(&plist);
  46. 	Display(plist);
  47. 	Popback(&plist);
  48. 	Display(plist);
  49. }
  50.  
  51. void test3()   //查找   逆序  逆序打印
  52. {
  53. 	pList plist = NULL;
  54. 	Initlist(&plist);
  55. 	Pushfront(&plist, 1);
  56. 	Pushfront(&plist, 2);
  57. 	Pushfront(&plist, 3);
  58. 	Pushfront(&plist, 4);
  59. 	Pushfront(&plist, 5);
  60. 	Display(plist);
  61. 	pNode ret=Find(plist,6);
  62. 	printf("%d\n", ret->data);
  63. 	Invert_list(&plist);
  64. 	Display(plist);
  65.  
  66. 	Invert_display(plist);
  67. }
  68.  
  69. void test4()   //删除一个非尾结点
  70. {
  71. 	pList plist = NULL;
  72. 	pNode pnode = NULL;
  73. 	Initlist(&plist);
  74. 	Pushfront(&plist, 1);
  75. 	Pushfront(&plist, 2);
  76. 	Pushfront(&plist, 3);
  77. 	Pushfront(&plist, 4);
  78. 	Pushfront(&plist, 5);
  79. 	Display(plist);
  80.  
  81. 	pnode = Find(plist, 4);
  82.  
  83. 	Del_Not_Tail(pnode);
  84.  
  85. 	Display(plist);
  86. }
  87.  
  88. void test5()   //在指定位置前增加一个结点
  89. {
  90. 	pList plist = NULL;
  91. 	pNode pnode = NULL;
  92. 	Initlist(&plist);
  93. 	Pushfront(&plist, 1);
  94. 	Pushfront(&plist, 2);
  95. 	//Pushfront(&plist, 3);
  96. 	Pushfront(&plist, 4);
  97. 	Pushfront(&plist, 5);
  98. 	Display(plist);
  99.  
  100. 	pnode = Find(plist,2);
  101.  
  102. 	Insert_Front_Node(pnode, 3);
  103.  
  104. 	Display(plist);
  105. }
  106.  
  107. void test6()   //合并有序链表
  108. {
  109. 	pList plist1 = NULL;
  110. 	pList plist2 = NULL;
  111. 	pList head = NULL;
  112. 	Initlist(&plist1);
  113. 	Initlist(&plist2);
  114. 	Pushfront(&plist1, 10);
  115. 	Pushfront(&plist2, 9);
  116. 	Pushfront(&plist1, 8);
  117. 	Pushfront(&plist2, 7);
  118. 	Pushfront(&plist1, 6);
  119. 	Pushfront(&plist2, 5);
  120. 	Pushfront(&plist1, 4);
  121. 	Pushfront(&plist2, 3);
  122. 	Pushfront(&plist1, 2);
  123. 	Pushfront(&plist2, 1);
  124. 	Display(plist1);
  125. 	Display(plist2);
  126.  
  127. 	head=Merge(&plist1, &plist2);
  128. 	Display(head);
  129.  
  130. 	Display(plist1);
  131. 	Display(plist2);
  132. }
  133.  
  134. void test7()   //约瑟夫环
  135. {
  136. 	pList plist = NULL;
  137. 	Initlist(&plist);
  138. 	Pushfront(&plist, 10);
  139. 	Pushfront(&plist,9);
  140. 	Pushfront(&plist, 8);
  141. 	Pushfront(&plist, 7);
  142. 	Pushfront(&plist, 6);
  143. 	Pushfront(&plist, 5);
  144. 	Pushfront(&plist, 4);
  145. 	Pushfront(&plist, 3);
  146. 	Pushfront(&plist, 2);
  147. 	Pushfront(&plist, 1);
  148. 	Display(plist);
  149.  
  150. 	Find(plist, 10)->next = plist;
  151.  
  152. 	JosephCycle(plist,1);
  153. }
  154.  
  155. void test8()   //寻找链表的中间结点，只遍历一次链表
  156. {
  157. 	pList plist = NULL;
  158. 	pNode pnode = NULL;
  159. 	Initlist(&plist);
  160. 	Pushfront(&plist, 10);
  161. 	Pushfront(&plist, 9);
  162. 	Pushfront(&plist, 8);
  163. 	Pushfront(&plist, 7);
  164. 	Pushfront(&plist, 6);
  165. 	Pushfront(&plist, 5);
  166. 	Pushfront(&plist, 4);
  167. 	Pushfront(&plist, 3);
  168. 	Pushfront(&plist, 2);
  169. 	Pushfront(&plist, 1);
  170. 	Display(plist);
  171.  
  172. 	pnode=Find_Mid_Node(plist);
  173. }
  174.  
  175. void test9()    //链表进行冒泡排序
  176. {
  177. 	pList plist = NULL;
  178. 	Initlist(&plist);
  179. 	Pushfront(&plist, 9);
  180. 	Pushfront(&plist, 5);
  181. 	Pushfront(&plist, 2);
  182. 	Pushfront(&plist, 6);
  183. 	Pushfront(&plist, 8);
  184. 	Pushfront(&plist, 1);
  185. 	Pushfront(&plist, 4);
  186. 	Pushfront(&plist, 7);
  187. 	Pushfront(&plist, 10);
  188. 	Pushfront(&plist, 3);
  189. 	Display(plist);
  190.  
  191. 	BubbleSort(plist);
  192. 	Display(plist);
  193. }
  194.  
  195. void test10()    //删除倒数第k个元素
  196. {
  197. 	pList plist = NULL;
  198. 	Initlist(&plist);
  199. 	Pushfront(&plist, 10);
  200. 	Pushfront(&plist, 9);
  201. 	Pushfront(&plist, 8);
  202. 	Pushfront(&plist, 7);
  203. 	Pushfront(&plist, 6);
  204. 	Pushfront(&plist, 5);
  205. 	Pushfront(&plist, 4);
  206. 	Pushfront(&plist, 3);
  207. 	Pushfront(&plist, 2);
  208. 	Pushfront(&plist, 1);
  209. 	Display(plist);
  210.  
  211. 	Del_K_Node(plist,1);
  212. 	Display(plist);
  213. }
  214.  
  215. void test11()    //判断链表是否带环    求带环链表的环入口点   求带环链表的长度
  216. {
  217. 	pList plist = NULL;
  218. 	pNode meet = NULL;
  219. 	pNode entry = NULL;
  220. 	int ret = 0;
  221.  
  222. 	Initlist(&plist);
  223. 	Pushfront(&plist, 10);
  224. 	Pushfront(&plist, 9);
  225. 	Pushfront(&plist, 8);
  226. 	Pushfront(&plist, 7);
  227. 	Pushfront(&plist, 6);
  228. 	Pushfront(&plist, 5);
  229. 	Pushfront(&plist, 4);
  230. 	Pushfront(&plist, 3);
  231. 	Pushfront(&plist, 2);
  232. 	Pushfront(&plist, 1);
  233. 	Display(plist);
  234.  
  235. 	Find(plist, 10)->next = Find(plist,5);
  236.  
  237. 	meet=Check_Cycle(plist);
  238. 	//printf("%d\n", ret);
  239.  
  240. 	entry = Get_Circle_Entry_Node(meet, plist);
  241. 	printf("环入口点为：%d\n", entry->data);
  242.  
  243. 	ret = Get_Circle_Length(meet);
  244. 	printf("链表长度为：%d\n", ret);
  245. }
  246.  
  247. void test12()   //判断两个不带环链表是否相交    求两个相交的不带环链表的交点
  248. {
  249. 	pList plist1 = NULL;
  250. 	pList plist2 = NULL;
  251. 	pNode node = NULL;
  252. 	pNode meet = NULL;
  253.  
  254. 	Initlist(&plist1);
  255. 	Initlist(&plist2);
  256.  
  257. 	Pushfront(&plist1, 10);
  258. 	Pushfront(&plist1, 9);
  259. 	Pushfront(&plist1, 8);
  260. 	Pushfront(&plist1, 7);
  261. 	Pushfront(&plist1, 6);
  262. 	Pushfront(&plist1, 4);
  263. 	Pushfront(&plist1, 2);
  264. 	Display(plist1);
  265.  
  266. 	Pushfront(&plist2, 5);
  267. 	Pushfront(&plist2, 4);
  268. 	Pushfront(&plist2, 3);
  269. 	Pushfront(&plist2, 2);
  270. 	Pushfront(&plist2, 1);
  271. 	Display(plist2);
  272.  
  273. 	Find(plist2, 5)->next = Find(plist1, 6);
  274. 	Display(plist1);
  275. 	Display(plist2);
  276.  
  277. 	node=Check_Cross(plist1, plist2);
  278. 	
  279. 	meet = Check_Cross_Meet(plist1, plist2);
  280. 	printf("交点为：%d\n", meet->data);
  281. }
  282. int main()
  283. {
  284. 	test12();
  285. 	return 0;
  286. }
























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

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

  

闽ICP备14008679号