猫吃老鼠的系统化算法

猫吃老鼠的系统化算法

作者：李斤询

下载本文示例源代码

typedef struct MouseNode
{
	int nNO;
	MouseNode *pNext;
	MouseNode *pPre;

	MouseNode() { nNO = 0; pNext = NULL; pPre = NULL; }
	MouseNode(int NO) { nNO = NO; pNext = NULL; pPre = NULL; }

}MouseNode;

		

 // CatEatMouses 
/*
本函数只吃一圈老鼠，循环调用它来吃完老鼠
	参数		本次要吃掉的老鼠
	返回		下一圈吃老鼠时候要吃的第一个老鼠
				若返回值为空，则说明老鼠已经吃完了
*/
MouseNode *CatEatMouses(MouseNode *pStartMouse)
{
	MouseNode *pFirst = pStartMouse;
	MouseNode *pFirstNotEatMouse = pFirst->pNext;
	if(pFirst == pFirstNotEatMouse)
	{
		printf("%d ", pFirst->nNO);
		return NULL; // 吃完了 
	}
	bool bCanEat = true;
	while (true)
	{
		if(pFirst == pFirstNotEatMouse)
		{
			if(bCanEat)
			{
				return pFirstNotEatMouse;
			}
			else
			{
				return pFirstNotEatMouse->pNext;
			}
		}
		if(bCanEat)
		{
			pFirst->pPre->pNext = pFirst->pNext;
			pFirst->pNext->pPre = pFirst->pPre;
			printf("%d ", pFirst->nNO);
			pFirst = pFirst->pNext;
			bCanEat = false;
		}
		else
		{
			pFirst = pFirst->pNext;
		}
	}
}

void DemoEatMouse(int nMouseCount)
{
	if(nMouseCount <= 1)
	{
		printf("1");
		return ;
	}
	// 开辟N个老鼠内存并初始化 
	MouseNode *pMouseBuffer = new MouseNode[nMouseCount];
	
	// 初始化双向链表 
	pMouseBuffer[0].pNext = &pMouseBuffer[1];
	pMouseBuffer[0].pPre = &pMouseBuffer[nMouseCount - 1];
	pMouseBuffer[0].nNO = 1;
	pMouseBuffer[nMouseCount - 1].pNext = &pMouseBuffer[0];
	pMouseBuffer[nMouseCount - 1].pPre = &pMouseBuffer[nMouseCount - 2];
	pMouseBuffer[nMouseCount - 1].nNO = nMouseCount;
	for(int i = 1;i < nMouseCount - 1;i++)
	{
		pMouseBuffer[i].pPre = &pMouseBuffer[i - 1];
		pMouseBuffer[i].pNext = &pMouseBuffer[i + 1];
		
		pMouseBuffer[i].nNO = i + 1;
	}
	
	// 开始吃老鼠 
	MouseNode *pNextEatMouse = &pMouseBuffer[0];
	while (pNextEatMouse)
	{
		if(pNextEatMouse->pNext == pNextEatMouse)
		{
			printf("\n最后一只老鼠是 ");
		}
		pNextEatMouse = CatEatMouses(pNextEatMouse);
	}
	
	printf("\n\n");
	
	delete[] pMouseBuffer;
}