用java学习数据结构--单链表

王朝java/jsp·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

/*

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

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航