[求助]一个关于链表的编程题的解法. - 编程论坛

#2

song42007-01-18 08:45

N年了
链表好实现吧

#3

jishuai2007-01-18 13:41

看看数据结构里面的链表嘛
自己应该可以写出来的啊

#4

dragonfly2007-01-18 14:21

链表的最末一个指向第一个,就成了圆的了,每次向下找第n个,删除(但要把断点接上,让被删除的上一个指向被删除的下一个)...

#5

icelake2007-01-18 16:50

[讨论]链表

数据结构还没学，怎么做，麻烦指导一下。 qq451127649感谢!!

#6

icelake2007-01-18 17:00

[讨论]链表

具体点，用C++编哦！

#7

olivezhang2007-01-19 17:59

这是个约瑟夫问题，给你个例程作参考吧：
题目：
//猴子选大王: 有M个猴子围成一圈，每个有一个编号，编号从1到M。打算从中选出
//一个大王。经过协商，决定选大王的规则如下：从第一个开始，每隔N个，数到的
//猴子出圈，最后剩下来的就是大王。
/*
* name : FindKingOfMonkey
* desc : Find the king from nMonkeyNum monkeys.
* in : nMonkeyNum - All monkeys' numbers.
nCount - Every time we count nCount monkeys.
* out : --
* ret : The ring of monkey.
*/
int FindKingOfMonkey(int nMonkeyNum, int nCount);

实现：
//----------------------------------------------------------------------------*
int ari::FindKingOfMonkey(int nMonkeyNum, int nCount)
{

struct Monkey
{
int nNextMonkey; //Point to the next monkey.
int nNotOutFlg; //Flag of monkey whether is out. 1 - not out,
//0 - out.
};

struct Monkey *pMonkeyLink = new struct Monkey[nMonkeyNum + 1];
assert(NULL != pMonkeyLink);

int i, j, k;
i = j = k = 0;
for (i=1; i<=nMonkeyNum; i++)
{ //The element 0 is not used. ºï×Ó×ÜÊýÎªnMonkeyNum, 0ºÅÔªËØÃ»ÓÐÊ¹ÓÃ.
pMonkeyLink[i].nNextMonkey = i + 1; //Point to next monkey.
pMonkeyLink[i].nNotOutFlg = 1; //At beginning, all monkeys are not
//out.
}
pMonkeyLink[nMonkeyNum].nNextMonkey = 1; //The last pointer point to the
//first monkey. Now we have
//constructed circulation of link.

int nOutCount = 1; //The counter of monkey who is out.
int nIndexOfMonkey = nMonkeyNum; //Ö¸ÏòÒÑ¾´¦ÀíÍê±ÏµÄÊý×éÔªËØ£¬´Ó
//pMonkeyLink[nIndexOfMonkey]Ö¸ÏòµÄºï×Ó¿ª
//Ê¼¼ÆÊý, ´ËÎª´ÓµÚÒ»Ö»ºï×Ó¿ªÊ¼Êý.

//Let nMonkeyNum monkeys out, and only left the king.
for (nOutCount=1; nOutCount<nMonkeyNum; nOutCount++)
{
for (k=0; k<nCount; )
{
//È¡³öÏÂÒ»ºï×ÓµÄË÷ÒýÏÂ±êÖµ.
nIndexOfMonkey = pMonkeyLink[nIndexOfMonkey].nNextMonkey;

//Êý¾¹ýÁËµÄºï×ÓÊý.Èç¹ûnNotOutflg == 0, ±íÊ¾¸Ãºï×ÓÒÑ¾³öÈ¦.Ìø¹ý¸Ã
//ºï×Ó.
k += pMonkeyLink[nIndexOfMonkey].nNotOutFlg;
}

pMonkeyLink[nIndexOfMonkey].nNotOutFlg = 0; //The monkey at
//nIndexOfMonkey is out.
}

int nKingOfMonkey = 0;

//Find the king of monkey whose nNotOutFlg == 1.
for (i=1; i<=nMonkeyNum; i++)
{
if (1 == pMonkeyLink[i].nNotOutFlg)
{
nKingOfMonkey = i;
break;
}
}

delete [] pMonkeyLink;

return nKingOfMonkey;
}

#8

olivezhang2007-01-19 18:00

抱歉，有的comment乱码，重新整理：

实现：

//----------------------------------------------------------------------------*
int ari::FindKingOfMonkey(int nMonkeyNum, int nCount)
{

struct Monkey
{
int nNextMonkey; //Point to the next monkey.
int nNotOutFlg; //Flag of monkey whether is out. 1 - not out,
//0 - out.
};

struct Monkey *pMonkeyLink = new struct Monkey[nMonkeyNum + 1];
assert(NULL != pMonkeyLink);

int i, j, k;
i = j = k = 0;
for (i=1; i<=nMonkeyNum; i++)
{ //The element 0 is not used. 猴子总数为nMonkeyNum, 0号元素没有使用.
pMonkeyLink[i].nNextMonkey = i + 1; //Point to next monkey.
pMonkeyLink[i].nNotOutFlg = 1; //At beginning, all monkeys are not
//out.
}
pMonkeyLink[nMonkeyNum].nNextMonkey = 1; //The last pointer point to the
//first monkey. Now we have
//constructed circulation of link.

int nOutCount = 1; //The counter of monkey who is out.
int nIndexOfMonkey = nMonkeyNum; //指向已经处理完毕的数组元素，从
//pMonkeyLink[nIndexOfMonkey]指向的猴子开
//始计数, 此为从第一只猴子开始数.

//Let nMonkeyNum monkeys out, and only left the king.
for (nOutCount=1; nOutCount<nMonkeyNum; nOutCount++)
{
for (k=0; k<nCount; )
{
//取出下一猴子的索引下标值.
nIndexOfMonkey = pMonkeyLink[nIndexOfMonkey].nNextMonkey;

//数经过了的猴子数.如果nNotOutflg == 0, 表示该猴子已经出圈.跳过该
//猴子.
k += pMonkeyLink[nIndexOfMonkey].nNotOutFlg;
}

pMonkeyLink[nIndexOfMonkey].nNotOutFlg = 0; //The monkey at
//nIndexOfMonkey is out.
}

int nKingOfMonkey = 0;

//Find the king of monkey whose nNotOutFlg == 1.
for (i=1; i<=nMonkeyNum; i++)
{
if (1 == pMonkeyLink[i].nNotOutFlg)
{
nKingOfMonkey = i;
break;
}
}

delete [] pMonkeyLink;

return nKingOfMonkey;
}

#9

icelake2007-01-19 18:13

谢谢