C语言实现通用链表初步(二)

谁践踏了优雅 2022-08-27 03:22 115阅读 0赞

接着上次的内容，我们继续！

还是无头单向非循环链表。假如要删除某个节点，如何实现？

//删除成功返回0，失败返回-1
    int slist_del(struct node_info *node, struct slist_info *info)
    {
    	assert(info != NULL && node != NULL);
    	assert(!slist_is_empty(info));
    	if(node==info->first)//如果要删除的就是第一个节点
    	{
    		info->first = node->next;
    		free(node);
    		return 0;
    	}
    	//如果不是第一个，那么是哪个呢？要删除必须先找到，可是找到就可以了吗？
    	//因为是单向链表，我们只能知道这个节点的后面那个，而不知道前面是谁，那怎么删除呢？
    	//所以，在遍历的过程中，还要把前面的一个节点保存起来	
    	else
    	{
    		struct node_info *pre = info->first;
    		struct node_info *cur = pre->next;
    		while(cur!=NULL&&cur!=node)
    		{
    			pre = pre->next;
    			cur = cur->next;
    		}
    		if(cur==NULL)
    			return -1; // the node to delete is not in the list
    		pre->next = cur->next;//delete
    		free(cur);
    		return 0;
    	}
    	
    }

假设有个程序员很粗心，让最后一个节点的next指针指向了链表中的某一个节点，你能检查出来吗？

1----2----3----4----5----6----7----8----9

|                           |

|----------------------|

比如这个图，1是第一个，9的后面是5，构成了一个环。

思路是这样的：假设2个人，一个人每次走1步，另一个每次走2步。同时出发，如果有环存在，那么这两个人肯定会相遇的！因为两个人都要在圈里面绕，步长差1，那么快的那个肯定会追赶慢的那个，总会追上的！------此思路我们称为“追赶法”！

int slist_is_dead_loop(struct slist_info *info)
    {
    	assert(info != NULL);
    	assert(!slist_is_empty(info));
    
    	assert(info->first->next!=NULL);//节点数不少于两个
    	struct  node_info *slow = info->first;
    	struct  node_info *fast = info->first;
    	
    	while (fast!= NULL && fast->next != NULL) { //che 2014.4.28
    
    		fast = fast->next->next;
    		slow = slow->next;
    		if (fast == slow) {
    			break;//相遇
    		}
    		
    	}
    	
    	if (fast != slow) {
    		return 0; //无死环
    	}
    	//此时相遇。怎么求环的长度呢？
    	//fast固定，每次移动1步slow,再次相遇的时候，移动的步数就是环的长度
    	int step = 1;
    	slow = slow->next;
    	
    	while(fast!=slow)
    	{
    		slow = slow->next;
    		++step;
    	}
    	printf("the circle = %d\n",step);
    	
    	//怎么求环前面那段链子的长度？

O----------------------------------------E-----------------------A-------

|------------------------------- |

如图，假设E点是环的起点，设OE长为x,环的长度是L.

我们安排一个场景，甲乙两个人，乙先出发，走到A点时候，甲出发了，两个人的速度是一样的，在E点的时候，两人相遇了！这时候甲走的步数就是链子的长度！问题是A点是哪里呢？

我们可以列出等式   x+L = 乙先走的（OA）+乙后走的(也就是甲走的x)

所以，OA=L

也就是说，先让乙走L步，然后两个人都走，相遇的时候，甲走的就是所求，接着上面的代码

//设环的长度为L,让两个人都回到起点，先让P2向前走L步。
    	//然后p1,p2每次往前走一步，当他们相遇的时候，p1移动的步数就是所求
    	fast = slow = info->first;
    	while(step--)
    		fast = fast->next; //P2向前走L步
    	
    	step = 0;
    	while(fast!=slow)
    	{
    		slow = slow->next;
    		fast = fast->next;
    		++step;
    	}
    	printf("the line = %d\n",step);//链子的长度
    	return 1; //有死环
    }

关于测试代码，下次再说。