基於鏈表編寫「貓吃老鼠」
http://pan.baidu.com/s/1nvaTki1
這是一個簡單的鏈表操作問題
"現有n個老鼠圍成一圓圈，有一隻貓從任意位置開始吃老鼠，每次都隔一個老鼠吃，請給出最後一個老鼠的編號？"
題目的具體要求是給出任給老鼠數n，輸出貓最後吃的老鼠的編號。
思考這樣的一個問題，由於涉及到從數據隊列中間刪除數據（相對於從開頭和結尾刪除數據），所以需要使用鏈表。
在現在的編程環境中，鏈表的操作可以使用std，也可以使用自己編寫的鏈表。由於這裏是kata，所以兩種方式都採用。
鏈表分爲單向鏈表和雙向鏈表，由於「貓吃老鼠」是一個單向循環的操作，所以採用單向鏈表就可以。
首先定義數據結構
typedef struct MouseNode
{
int iNO;
MouseNode *pNext;
MouseNode(){iNO = 0;pNext = nullptr;}
MouseNode(int i){iNO = i;pNext = nullptr;}
};
老鼠的結構，除了自己的編號，關鍵的是定義了下一個指向。
然後編寫「吃老鼠動作」
MouseNode* C貓吃老鼠鏈表操作Dlg::CatEatmouses(MouseNode* pStartMouse)
{
MouseNode* pThis = pStartMouse;
pThis->pNext = pThis->pNext->pNext;
pThis = pThis->pNext;
return pThis;
}
最後編寫事件驅動
void C貓吃老鼠鏈表操作Dlg::OnBnClickedOk()
{
// TODO: 在此添加控件通知處理程序代碼
int nMouseCount = GetDlgItemInt(IDC_EDIT_INPUT);
if(nMouseCount <= 1)
{
m_iResult = 1;//結果爲1
return ;
}
// 開闢N個老鼠內存並初始化
MouseNode *pMouseBuffer = new MouseNode[nMouseCount];
// 初始化雙向鏈表
pMouseBuffer[0].pNext = &pMouseBuffer[1];
pMouseBuffer[0].iNO = 1;
pMouseBuffer[nMouseCount - 1].pNext = &pMouseBuffer[0];
pMouseBuffer[nMouseCount - 1].iNO = nMouseCount;
for(int i = 1;i < nMouseCount - 1;i++)
{
pMouseBuffer[i].pNext = &pMouseBuffer[i + 1];
pMouseBuffer[i].iNO = i + 1;
}
// 開始吃老鼠
MouseNode *pNextEatMouse = &pMouseBuffer[nMouseCount-1];
while (TRUE)
{
if(pNextEatMouse->pNext == pNextEatMouse)
{
break; //當鏈表中只有一個元素的時候退出
}
pNextEatMouse = CatEatmouses(pNextEatMouse);
}
m_iResult = pNextEatMouse->iNO;
delete[] pMouseBuffer;
SetDlgItemInt(IDC_EDIT_RESULT,m_iResult);
}
並且實現界面
雖然std::forward_list也是單向鏈表，但是目前還沒有看過寫得非常好的代碼，感覺使用起來不如直接使用感覺利索。