基于連結清單編寫“貓吃老鼠”

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也是單向連結清單，但是目前還沒有看過寫得非常好的代碼，感覺使用起來不如直接使用感覺利索。

來自為知筆記(Wiz)

目前方向：圖像拼接融合、圖像識别

聯系方式：[email protected]