Question

如何将一个链表作为一个函数的参数

Answer 1

这就是个猴子选大王的游戏变形
游戏描述:
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子(m个)按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
其实这个问题就是约瑟夫环的应用，主要应用循环链表来解决。以下是它的源程序:
#includeiostream.h
class node //建立节点类
{
private:
node *next;//nesxt为节点内的指针
public:
int data;//节点内的数据域
node(void);//节点构造函数
node(int obj);//带一个参数的节点构造函数
insertnode(node *p);//插入节点函数声明 *p为指针类型参数
node *deletenode(void);//删除节点函数声明
node *nextnode(void) const; //查找下一节点函数声明 返回一个node类型的指针变量
};
//具体函数实现
node::node(void)//节点构造函数实现
{
next=this;//使节点的指针指向自己
}
node::node(int obj)//带一个参数的节点构造函数实现
{
next=this; //同上
data=obj;
}
node::insertnode(node *p)//插入节点函数实现
{
p-next=next;
next=p;
}
node *node::deletenode(void)//删除节点函数实现
{
node *ptr=next;//*ptr指针指向要删除的节点
if(ptr==this) //如果ptr指向自己，即循环链表中没有节点可删除，然后返回
return NULL;
next=ptr-next;//使前一个节点的指针(即next)指向要删除节点的下一个节点
return ptr; //返回要删除的节点指针
}
node *node::nextnode(void) const//查找下一节点函数实现
{
return next;
}
void creatmonkey_list(node *header,int n)//建立循环链表
{
node *current_ptr=header,*newnode_ptr;//current_ptr为当前指针，newnode_ptr为新建节点的指针
int i;
for(i=1;i=n;i++)
{
newnode_ptr=new node(i);//创建一个新节点
current_ptr-insertnode(newnode_ptr);//将这个节点插入到循环链表中
current_ptr=newnode_ptr;//向后移动指针
}
}