/*
* Created on 2004-9-10
*
* 单链表中的结点类型声明.
*/
package org.arliang;
/**
* @author 李梁
*
* 单链表中的结点.
*/
public class node
{
private int data; //存放数据
private node link; //链接的下一个接点.
public static void main(String[]args)
{
}
/**
* @return Returns the data.
*/
public int getData()
{
return data;
}
/**
* @param data
* The data to set.
*/
public void setData(int data)
{
this.data = data;
}
/**
* @return Returns the link.
*/
public node getLink()
{
return link;
}
/**
* @param link
* The link to set.
*/
public void setLink(node link)
{
this.link = link;
}
/**
* @param linkList
* 链表中的头结点
* @param K
* 在链表中的位置
* @return 找到的结点,如果没有找到,则返加NULL
*/
public node findNode(node linkList, int k)
{
int i = 1;
node a;
// 初始化时,令a指向第一个元素,i为计数器.
a = linkList.getLink();
while (a != null && i < k)
{
a = a.getLink();
}
// 逐步的取下一个数.
return a;
}
/**
* @param linkList 链表的头结点
* @param k 插入的位置,将在这个位置之前插入
* @param elem 要插入的结点
* @return 是否成功,成功返回0
*/
public int insertNode(node linkList, int k, node elem)
{
node a, b;
if (k == 1)
{
elem.setLink(linkList);
}
else
{
a = findNode(linkList, k - 1);
if (a != null)
{
b = a.getLink();
a.setLink(elem);
elem.setLink(b);
}
else
return - 1;
}
return 0;
}
/**
* @param linkList 链表的头结点
* @param k 位置
* @return 是否成功,成功返回0
*/
public int deleteNode(node linkList, int k)
{
node a, b;
if (k == 1)
{
linkList.setLink(null);
}
else
{
a = findNode(linkList, k);
if (a != null)
{
b = a.getLink();
a.setLink(b.getLink());
return - 1;
}
}
return 0;
}
}
--------------------------------------------------------------------------------------
/*
* 创 建 人 Administrator
* 创建日期 2004-9-10
*
*/
package org.arliang;
/**
* @author Administrator
*
* 选首领.N个游戏者围成一圈,从第一个人开始顺序报数1,2,3.凡报到3者退出圈子,最后留在圈中的人为首领.
* 结点编号是从0开始而不是从1开始.
*/
public class selectHead
{
/**
* 创建链表.创建给定数目个数的链表,并将其首尾连起形成环.
*
* @param n
* @return 该链表的首节点
*/
public node createList(int n)
{
node headNode = new node();
int i = 1;
headNode.setData(0); //头节点
node a = headNode;
while (i < n)
{
node b = new node();
b.setData(i);
a.setLink(b);
a = b;
i++; //该循环不能丢,否则成为死循环
}
a.setLink(headNode); //形成环
return headNode;
}
/**
* 输出当前链表中的数据
*
* @param linkList 链表的头结点
*/
public void outputData(node linkList)
{
// 形成环之后要注意标识头结点的位置,对于只有一个了节点的链其可能形成死循环.
node a;
a = linkList;
node b = a.getLink();
while (b.getData() != a.getData())
{
//由于是环,故这样判断,但该判断并不严密
System.out.print(b.getData());
b = b.getLink(); //获取下一个节点
}
}
/**
* 执行该游戏
* @param linkList 链表的头结点
* @param n 该链表的总个数
*/
public void play(node linkList, int n)
{
int k;
node a = linkList;
node b;
k = n;
while (k > 1)
{
//从当前节点向下走一个节点后,则当前的报数应该是2
a = a.getLink(); //该节点的报数应该是2
b = a.getLink(); //该节点的报数应该是3,要删除
a.setLink(b.getLink()); //将B节点删除.
a = a.getLink(); //将当前节点换为删除节点之后的节点.
k--; //已删除一个节点
}
System.out.print("结果" + Integer.toString(a.getData()));
//输出最后还在圈中的节点
}
/**
* @param args
*/
public static void main(String[]args)
{
selectHead sh = new selectHead(); //创建对象
node a = sh.createList(9); //创建链表环
sh.outputData(a); //查看数据
sh.play(a, 9); //执行游戏.
}
}
