基于链表编写“猫吃老鼠”

简介: http://pan.baidu.com/s/1nvaTki1 这是一个简单的链表操作问题 "现有n个老鼠围成一圆圈,有一只猫从任意位置开始吃老鼠,每次都隔一个老鼠吃,请给出最后一个老鼠的编号?" 题目的具体要求是给出任给老鼠数n,输出猫最后吃的老鼠的编号。

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;}
};
老鼠的结构,除了自己的编号,关键的是定义了下一个指向。
然后编写“吃老鼠动作”
MouseNodeC猫吃老鼠链表操作Dlg::CatEatmouses(MouseNodepStartMouse)
{
 
    MouseNodepThis  = 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也是单向链表,但是目前还没有看过写得非常好的代码,感觉使用起来不如直接使用感觉利索。





目前方向:图像拼接融合、图像识别 联系方式:jsxyhelu@foxmail.com
目录
相关文章
|
8月前
|
算法 C语言
C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2
C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2
68 0
|
5月前
|
算法 C++
F : 吃奶酪(深搜)
这篇文章提供了一个使用深度优先搜索(DFS)解决的算法问题,即“吃奶酪”问题,其中包含C++代码实现,目标是计算一只小老鼠吃掉所有奶酪的最少距离,通过预处理奶酪间的距离和使用剪枝技术来优化搜索过程。
|
7月前
|
人工智能 测试技术 Windows
技术心得:威威猫系列之吃鸡腿
技术心得:威威猫系列之吃鸡腿
40 0
|
7月前
|
算法 Python
利用深度优先搜索算法解决老鼠吃奶酪问题(python)
利用深度优先搜索算法解决老鼠吃奶酪问题(python)
47 0
|
8月前
|
算法
OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!)
OJ刷题:《剑指offer》之单身狗1、2 !(巧用位操作符,超详细讲解!)
|
存储 算法
经典算法题之 找出一个数组中的两个“单身狗”
经典算法题之 找出一个数组中的两个“单身狗”
|
编译器 C语言 C++
缺省参数!C++教你如何成为一名优秀的舔狗
缺省参数!C++教你如何成为一名优秀的舔狗
缺省参数!C++教你如何成为一名优秀的舔狗
L1-063 吃鱼还是吃肉 (10 分)
L1-063 吃鱼还是吃肉 (10 分)
226 0
L1-063 吃鱼还是吃肉 (10 分)
|
算法
蓝桥杯 算法 猴子吃包子、 查找整数
蓝桥杯 算法 猴子吃包子、 查找整数
130 0