本文主要是介绍基于链表编写“猫吃老鼠”,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
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)
这篇关于基于链表编写“猫吃老鼠”的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!