java 链表实现-codecraft-ChinaUnix博客

codecraft

首页　| 　博文目录　| 　关于我

codecraft

博客访问： 78760
博文数量： 22
博客积分： 1250
博客等级：中尉
技术积分： 305
用户组：普通用户
注册时间： 2007-04-19 09:44

文章分类

全部博文（22）

生活（0）
linux/unix（5）
网络方面（0）
数据库（2）
算法（1）
C语言（2）

随笔（2）
论历史（1）
java（10）
未分配的博文（1）

文章存档

2009年（2）

2008年（20）

我的朋友

最近访客

推荐博文

java 链表实现

分类：

2008-08-29 10:26:26

在网上闲逛，看到有一道题目如下：
n个人围成一圈，每人有一个各不相同的编号，选择一个人作为起点，然后顺时针从1到k数数，每数到k的人退出圈子，圈子缩小，然后从下一个人继续从1到k数数，重复上面过程。求最后推出圈子的那个人原来的编号。
这就是经典的约瑟夫环问题啊，所以，用java链表写了个。 shy

首先，创建一个链接节点类 LinkedNode.java

/**
* @author 李国庆
* @company leo (C) copyright
* @time 2007-4-12 下午04:29:10
* @version 1.0.0.0
* @package com.leo.node
* @project nodeDemo
*/
package com.leo.node;
/**
* @author leo
*
*/
public class LinkedNode {
public LinkedNode previous;// 前一节点
public LinkedNode next;// 后一节点
public int no; //节点序号
public Object object;// 节点中的数据
public LinkedNode(Object object, LinkedNode next,
LinkedNode previous) {
this.object = object;
this.next = next;
this.previous = previous;
}
/**
* 从链表中移去
*
*/
public void remove() {
previous.next = next;
next.previous = previous;
}
public String toString() {
return object.toString();
}
}

然后创建环形链表类：LinkedList.java

/**
* @author 李国庆
* @company leo (C) copyright
* @time 2007-4-12 下午04:14:14
* @version 1.0.0.0
* @package com.leo.note
* @project noteDemo
*/
package com.leo.node;
/**
* @author leo
*
* 链表集合
*
*/
public class LinkedList {
private LinkedNode head;
public LinkedList() {
head.next = head.previous = new LinkedNode("head", null, null);// 头节点
}
public LinkedList(LinkedNode _head) {
head = _head;// 头节点
head.next = head.previous = head;
}
/**
* 返回头节点
*
* @return
*/
public LinkedNode getFirst() {// 返回头节点后的第一个节点
// LinkedNode node = head.next;
// if (node == head) {
// return null;
// }
// return node;
return head;
}
/**
* 返回最后一个节点
*
* @return
*/
public LinkedNode getLast() {
LinkedNode node = head.previous;
if (node == head) {
return null;
}
return node;
}
/**
* 将节点加到头节点后
*
* @param node
* @return
*/
public LinkedNode addFirst(LinkedNode node) {
node.next = head.next;
node.previous = head;
node.previous.next = node;
node.next.previous = node;
return node;
}
/**
* 将节点加到头节点后
*
* @param object
* @return
*/
public LinkedNode addFirst(Object object) {
LinkedNode node = new LinkedNode(object, head.next, head);
node.previous.next = node;
node.next.previous = node;
return node;
}
/**
* 节点添加到链表最后
*
* @param object
* @return
*/
public LinkedNode addLast(Object object) {
LinkedNode node = new LinkedNode(object, head, head.previous);
node.previous.next = node;
node.next.previous = node;
// head.previous = node;
return node;
}
/**
* 清空列表
*
*/
public void clear() {// 清空链表
// Remove all references in the list.
LinkedNode node = getLast();
while (node != null) {
node.remove();
node = getLast();
}
// Re-initialize.
head.next = head.previous = head;
}
/**
* 返回对象值
*/
public String toString() {
LinkedNode node = head;
StringBuffer buf = new StringBuffer();
while (node != head) {
System.out.println("node.toString() in toString is :"
+ node.toString());
buf.append(node.toString()).append(", ");
node = node.next;
}
return buf.toString();
}
/**
* 返回链表的长度
*
* @return
*/
public int getLength() {
int _length = 0;
while (head.next != head)
_length++;
return _length;
}
}

/**
 * @author    李国庆
 * @company   leo (C) copyright
 * @time      2007-4-12  下午04:14:14
 * @version   1.0.0.0
 * @package   com.leo.note
 * @project   noteDemo
 */
package com.leo.node;

/**
 * @author leo
 * 
 * 链表集合
 * 
 */
public class LinkedList {

private LinkedNode head;

public LinkedList() {
    head.next = head.previous = new LinkedNode("head", null, null);// 头节点
  }

public LinkedList(LinkedNode _head) {
    head = _head;// 头节点
    head.next = head.previous = head;
  }

/**
   * 返回头节点
   *
   * @return
   */
  public LinkedNode getFirst() {// 返回头节点后的第一个节点
    // LinkedNode node = head.next;
    // if (node == head) {
    // return null;
    // }
    // return node;
    return head;
  }

/**
   * 返回最后一个节点
   *
   * @return
   */
  public LinkedNode getLast() {
    LinkedNode node = head.previous;
    if (node == head) {
      return null;
    }
    return node;
  }

/**
   *  将节点加到头节点后
   *
   * @param node
   * @return
   */
  public LinkedNode addFirst(LinkedNode node) {
    node.next = head.next;
    node.previous = head;
    node.previous.next = node;
    node.next.previous = node;
    return node;
  }

/**
   *  将节点加到头节点后
   *
   * @param object
   * @return
   */
  public LinkedNode addFirst(Object object) {
    LinkedNode node = new LinkedNode(object, head.next, head);
    node.previous.next = node;
    node.next.previous = node;
    return node;
  }

/**
   *  节点添加到链表最后
   *
   * @param object
   * @return
   */
  public LinkedNode addLast(Object object) {
    LinkedNode node = new LinkedNode(object, head, head.previous);
    node.previous.next = node;
    node.next.previous = node;
    // head.previous = node;
    return node;
  }

/**
   *  清空列表
   *
   */
  public void clear() {// 清空链表
    // Remove all references in the list.
    LinkedNode node = getLast();
    while (node != null) {
      node.remove();
      node = getLast();
    }
    // Re-initialize.
    head.next = head.previous = head;
  }

/**
   *  返回对象值
   */
  public String toString() {
    LinkedNode node = head;
    StringBuffer buf = new StringBuffer();
    while (node != head) {
      System.out.println("node.toString() in toString is :"
          + node.toString());
      buf.append(node.toString()).append(", ");
      node = node.next;
    }
    return buf.toString();
  }

/**
   * 返回链表的长度
   * 
   * @return
   */
  public int getLength() {
    int _length = 0;
    while (head.next != head)
      _length++;
    return _length;
  }

}

最后一个测试类 Josephus.java

/**
* @author 李国庆
* @company leo (C) copyright
* @time 2007-4-12 下午04:34:21
* @version 1.0.0.0
* @package com.leo.node
* @project nodeDemo
*/
package com.leo.node;
/**
* @author leo
*
*/
public class Josephus {
public LinkedList _list = null;
public int start = 0;
public Josephus(int start) {
this.start = start;
}
/**
* 移除一个子节点
*
* @param node
*/
public void removeOneNode(LinkedNode node) {
node.remove();
}
/**
* 执行踢出
*
* @param limit
*/
public void doLogic(int limit) {
LinkedNode _node_next_frist = _list.getFirst();
while (limit > 1) {
LinkedNode _node_remove = null;
for (int i = 1; i < start; i++) {
if (i == 1) {
_node_remove = _node_next_frist.next;
} else {
_node_remove = _node_remove.next;
}
}
_node_next_frist = _node_remove.next;
System.out.println(String.valueOf(_node_remove.object)
+ " is removed!");
removeOneNode(_node_remove);
limit--;
}
System.out.println(String.valueOf(_node_next_frist.object)
+ " is the last element!");
}
/**
*
*
* @param person
*/
public void addNode(String person) {
_list.addLast(person);
}
/**
* 添加到链表
*
* @param person
*/
public void addNode(String[] person) {
_list = new LinkedList(new LinkedNode(person[0], null, null));
for (int i = 1; i < person.length; i++)
_list.addLast(person[i]);
}
/**
*
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int _persion = 4;//被踢出人的位置
String[] _personList = { "老二", "张三", "李四", "王五", "赵六",
"钱七", "孙八", "刘九", "周十", "老大" };//所有人的列队
Josephus jp = new Josephus(_persion);
jp.addNode(_personList);// 添加数组到链表中
jp.doLogic(_personList.length);// 执行算法
}
}

/**
 * @author    李国庆
 * @company   leo (C) copyright
 * @time      2007-4-12  下午04:34:21
 * @version   1.0.0.0
 * @package   com.leo.node
 * @project   nodeDemo
 */
package com.leo.node;

/**
 * @author leo
 * 
 */
public class Josephus {

public LinkedList _list = null;

public int start = 0;

public Josephus(int start) {
    this.start = start;
  }

/**
   * 移除一个子节点
   *
   * @param node
   */
  public void removeOneNode(LinkedNode node) {
    node.remove();
  }

/**
   * 执行踢出
   *
   * @param limit
   */
  public void doLogic(int limit) {
    LinkedNode _node_next_frist = _list.getFirst();
    while (limit > 1) {
      LinkedNode _node_remove = null;
      for (int i = 1; i < start; i++) {
        if (i == 1) {
          _node_remove = _node_next_frist.next;
        } else {
          _node_remove = _node_remove.next;
        }
      }
      _node_next_frist = _node_remove.next;
      System.out.println(String.valueOf(_node_remove.object)
          + " is removed!");
      removeOneNode(_node_remove);
      limit--;
    }
    System.out.println(String.valueOf(_node_next_frist.object)
        + " is the last element!");
  }

/**
   * 
   * 
   * @param person
   */
  public void addNode(String person) {
    _list.addLast(person);
  }

/**
   * 添加到链表
   * 
   * @param person
   */
  public void addNode(String[] person) {
    _list = new LinkedList(new LinkedNode(person[0], null, null));
    for (int i = 1; i < person.length; i++)
      _list.addLast(person[i]);
  }

/**
   * 
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    
    int _persion = 4;//被踢出人的位置
    String[] _personList = { "老二", "张三", "李四", "王五", "赵六",
        "钱七", "孙八", "刘九", "周十", "老大" };//所有人的列队
    
    Josephus jp = new Josephus(_persion);
    jp.addNode(_personList);// 添加数组到链表中
    jp.doLogic(_personList.length);// 执行算法
  }
}

ok，输出结果如下：

王五 is removed!
刘九 is removed!
张三 is removed!
孙八 is removed!
李四 is removed!
老大 is removed!
周十 is removed!
老二 is removed!
钱七 is removed!
赵六 is the last element!

阅读(1887) | 评论(0) | 转发(0) |

上一篇：JAVA HASHTABLE

下一篇：java 实现压缩与解压缩ZIP

给主人留下些什么吧！~~

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6