| |
/*
* 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); //执行游戏.
}
}
|
|
