基于链表编写“猫吃老鼠”
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也是单向链表，但是目前还没有看过写得非常好的代码，感觉使用起来不如直接使用感觉利索。 本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！