与单链表有关的算法问题

左手的ㄟ右手 2022-08-23 05:52 236阅读 0赞

单链表结构的定义：

typedef int DataType;
    typedef struct LinkNode
    {
    	DataType data;
    	struct LinkNode *next;
    }LinkNode, *pLinkNode;
    typedef struct Linklist
    {
    	LinkNode *phead;
    }LinkList, *pLinkList;    //封装头节点，便于更好的维护单链表

1、单链表插入排序：

首先我们都知道，所谓的插入排序，即是一种把要排序的数据元素看成两组，分别是无序组和有序组，开始使有序组的元素个数为一个，无序组为n-1个，我们遍历无序组的数据元素，把无序组的数据插入到有序组的合适位置，直到无序组的元素的个数为0为止，现在排序的数据类型从数组换成了单链表，我们知道单链表只能从前向后遍历，所以用其实现插入排序的难度是大于数组的，但其基本算法思想都是一样的，下面我们来介绍一下单链表的插入排序：

![SouthEast][]

首先，我们要对单链表进行分割，分割成有序部分和无序部分，分割后有序部分的最后一个元素让其指向空；定义一个head指针让其指向无序部分的第一个元素。

随后，我们遍历无序部分的节点，如果无序部分的要插入有序链表中的节点小于有序链表的最后一个节点的数据元素，便遍历有序链表，直到找到大于要插入的节点的位置，并把要插入的节点插入到所找到的位置之前。如果大于有序链表的最后一个元素，则直接尾插到有序链表的最后一个节点后，并把尾指针plast向后移动指向新插入的节点。直到无序表的节点的个数为0我们才停止插入排序的过程。

void Insert_sort(pLinkList plist)
    {
    	assert(plist);
    	pLinkNode  head = NULL;     //定义无序链表的头节点
    	pLinkNode pcur2 = NULL;;    //遍历无序链表的指针
    	pLinkNode pcur1 = NULL;     //遍历有序链表的指针
    	pLinkNode plast = NULL;
    	if (plist->phead==NULL)
    	{
    		return;
    	}
    	head = plist->phead->next;    //head指向无序表中的第一个节点
    	plist->phead->next = NULL;    //拆分有序链表和无序链表
    	pcur2 = head;
    	plast = plist->phead;
    	while (pcur2)
    	{
    		pLinkNode pIns = pcur2;
    		head = head->next;
    		pcur1 = plist->phead;
    		if (pIns->data < plast->data)                  //有序表的最后一个人元素大于所要插入的元素
    		{
    			pLinkNode prev = NULL;
    			while (pcur1)       //找到插入的位置
    			{
    			    if (pcur1->data>pIns->data)
    					break;
    				prev = pcur1;
    				pcur1 = pcur1->next;
    			}
    			if (pcur1 == plist->phead)
    			{
    				pIns->next = plist->phead;
    				plist->phead = pIns;
    			}
    			else
    			{
    				pIns->next = prev->next;
    				prev->next = pIns;
    			}
    		}
    		else                                       //有序表的最后一个元素小于所要插入的元素
    		{                                          //直接把元素插到表尾，并更换尾指针的位置
    			plast->next = pIns;
    			pIns->next = NULL;
    			plast = pIns;
    		}
    		pcur2 = head;
    	}
    	
    }

2、约瑟夫环：

##  问题背景：约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。 ##

约瑟夫环问题的具体描述是：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。

问题分析：我们可以借助单链表来解决这个问题，编号1，2，3，。。。。n围城一个圈，从第一个开始报数，我们把这个问题可以抽象成一种循环且单向的数据结构类型，即：循环单链表，我们遍历单链表，每次找到”报数的“数据元素后便把该节点从链表中删除，并且指针指向下一个节点，周而复始的，我们便能找到最后一个报数的节点，即幸存者。

<span style="font-size:18px;">LinkNode *Yuesefu_huan(pLinkList plist, pLinkNode pos, int k)
    {
    	assert(plist);
    	assert(pos);
    	assert(k > 0);
    	int num = k;
    	pLinkNode cur = plist->phead;
    	pLinkNode del = NULL;
    	pLinkNode prev = plist->phead;
    	while (prev->next)               //找到尾节点
    	{
    		prev = prev->next;
    	}
    	prev->next = plist->phead;
    	cur = pos;
    	while (cur->next != cur)
    	{
    	   while (--num)
    	  {
    		prev = cur;
    		cur = cur->next;
    	   }
    	   printf("将要删除的节点是%d\n", cur->data);
    	   num = k;
    	   prev->next = cur->next;
    	   del = cur;
    	   cur = cur->next;
    	   free(del);
    	   del = NULL;
    	}
    	return cur;
    }</span>

3：链表带环问题：

![SouthEast 1][]

对于单链表的带环结构，我们可以看成是由一段直线部分和一段环状部分所组成的链表结构，那怎么判断单恋表是否带环呢？

首先，单链表如果带环，其尾指针的一定不会为空，用一个指针来遍历肯定是无法循环遍历完的，因此我们不能用单个的指针来遍历单链表，但我们可以采用一种间接的方法：定义两个指针，一个指针一次走两个节点，另外一个指针一次走一个节点，走的快的指针肯定先进入环状结构，并且能把走得慢的指针进行”套环“，所以如果快慢指针相遇，那么说明单链表带有环状结构：

int CheckCycle(pLinkList plist)                      //判断单链表是否带环,如果带环，则返回1，否则返回0
    {
    	assert(plist);
    	pLinkNode fast = plist->phead;
    	pLinkNode slow = plist->phead;
    	while (fast&&fast->next)
    	{
    		fast = fast->next->next;
    		slow = slow->next;
    		if (fast == slow)
    			break;
    	}
    	if (fast != NULL&&fast->next!=NULL)
    		return 1;
    	else
    		return 0;
    }

那我们如何能找到环的入口点呢，根据上图，我们设链表从头到环的入口的节点数为a，带环链表的节点数为b，快慢指针相遇时具体环的入口节点处有x个节点，于是我们有如下推导过程：

第一次相遇时，设慢指针的距离为s, s=a+x;

则快指针走过的距离为2s,且2s=a+nr+x ;

由此可以推出a+x=nr,即x=nr-a，a + x = (n – 1)r +r = (n-1)r + L - a

所以我们可以定义两个指针，一个指向单链表的头节点，另外一个指向快慢指针第一次相遇时的位置，分别让两指针一直走，当两指针相遇时，相遇的节点便是环的入口点：

pLinkNode FindCycleEnter(pLinkList plist)               //查找带环链表的环的入口，并返回入口节点
    {
    	assert(plist);
    	pLinkNode fast = plist->phead;
    	pLinkNode slow = plist->phead;
    	while (fast->next&&fast)
    	{
    		fast = fast->next->next;
    		slow = slow->next;
    		if (slow == fast)
    			break;
    	}
    	if (fast->next == NULL&&fast == NULL)
    	{
    		return NULL;
    	}
    	else
    	{
    		slow = plist->phead;
    		while (fast != slow)
    		{
    			fast = fast->next;
    			slow = slow->next;
    		}
    		return fast;
    	}
    }

[SouthEast]: /images/20220721/f47e2b32934d497aa64046b830e1d885.png
[SouthEast 1]: /images/20220721/10c87aa924c44b7aaa428c09157e3148.png