/* * 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); //执行游戏. } }
本文地址：http://com.8s8s.com/it/it15597.htm