猫吃老鼠的系统化算法

【 tulaoshi.com - C语言心得技巧 】

猫吃老鼠的系统化算法

作者：李斤询

下载本文示例源代码

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("nn");delete[] pMouseBuffer;}