Java两种方式实现约瑟夫环完整版
2018-11-20 03:21:10来源:博客园 阅读 ()
学校作业,顺便分享
单向循环链表:
package test1; /** * 约瑟夫环(单向链表) * * @author Xu Yiqing * */ public class JosephCircle1 { private MyLinkedList linkedlist; private Integer size; /** * 由单向链表生成单向循环链表 * * @param linkedlist 单项链表 * @return 生成的约瑟夫环的第一个Node */ public Node<Integer> getJosephCircle(MyLinkedList linkedlist) { try { this.linkedlist = linkedlist; this.size = this.linkedlist.getLinkedListSize(); Node<Integer> head = linkedlist.getHeadNode(); Node<Integer> tail = linkedlist.getLastNode(); tail.setNext(head); this.linkedlist.beginNode = null; return head; } catch (Exception e) { e.printStackTrace(); return null; } } /** * 删除约瑟夫环的一个Node * * @param node 想要删除的Node * @return 返回删除Node的前一个Node */ @SuppressWarnings({ "rawtypes", "unchecked" }) public Node deleteFromCircle(Node node) { Node flag = node.next; for (int i = 0; i < this.size - 2; i++) { flag = flag.next; } flag.next = flag.next.next; node = flag; this.size--; return node; } /** * 自定义链表类 * * @author Xu Yiqing * */ static class MyLinkedList { private Integer size; @SuppressWarnings("rawtypes") private Node beginNode; /** * 构造方法 */ public MyLinkedList() { doClear(); this.beginNode = new JosephCircle1().new Node<Integer>(null, null); } /** * 获取第一个Node * * @return 第一个Node */ @SuppressWarnings("unchecked") public Node<Integer> getHeadNode() { return beginNode.next; } /** * 在尾部添加一个新Node * * @param value Node的值 */ @SuppressWarnings({ "rawtypes", "unchecked" }) public void addAtTail(Integer value) { Node newNode = new JosephCircle1().new Node<Integer>(value, null); if (this.size == 0) { beginNode.next = newNode; } else { getNode(this.size - 1).next = newNode; } this.size++; } /** * 获取指定的Node * * @param index Node索引 * @return 获取到的Node */ @SuppressWarnings({ "finally", "unchecked" }) public Node<Integer> getNode(Integer index) { if (index < 0 || index >= size) { try { throw new Exception("越界"); } catch (Exception e) { e.printStackTrace(); } finally { return null; } } else { @SuppressWarnings("rawtypes") Node flag = beginNode; for (int i = 0; i <= index; i++) { flag = flag.getNext(); } return flag; } } /** * 删除指定的Node * * @param index 删除的Node的索引 */ @SuppressWarnings({ "rawtypes", "finally", "unchecked" }) public void deleteNode(Integer index) { if (index < 0 || index >= size) { try { throw new Exception("越界"); } catch (Exception e) { e.printStackTrace(); } finally { return; } } else { if (this.beginNode != null) { Node flag = beginNode; for (int i = 0; i <= index; i++) { flag = flag.getNext(); } flag.next = flag.getNext().getNext(); } } this.size--; } /** * 清空链表 */ private void doClear() { this.size = 0; this.beginNode = null; } /** * 获取最后一个Node * * @return 最后一个Node */ public Node<Integer> getLastNode() { return getNode(this.size - 1); } /** * 获取链表的大小 * * @return 大小 */ @SuppressWarnings("unchecked") public Integer getLinkedListSize() { Integer size = 0; Node<Integer> flag = beginNode; while ((flag = flag.getNext()) != null) { size++; } return size; } } /** * 自定义链表节点 * * @author Xu Yiqing * * @param <Type> 泛型 */ class Node<Type> { private Type value; private Node<Type> next; public Node(Type value, Node<Type> next) { super(); this.value = value; this.next = next; } public Type getValue() { return value; } public void setValue(Type value) { this.value = value; } public Node<Type> getNext() { return next; } public void setNext(Node<Type> next) { this.next = next; } } }
单向循环链表测试类:
package test1; import java.util.Scanner; import test1.JosephCircle1.MyLinkedList; import test1.JosephCircle1.Node; /** * 测试类 * @author Xu Yiqing * */ public class Test1 { @SuppressWarnings("rawtypes") public static void main(String[] args) { JosephCircle1 circle = new JosephCircle1(); MyLinkedList linkedlist = new MyLinkedList(); Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int num = sc.nextInt(); for (int i = 0; i < num; i++) { linkedlist.addAtTail(i + 1); } Node node = circle.getJosephCircle(linkedlist); for(int i=0;i<num;i++) { for (int j = 0; j < (m-1); j++) { node = node.getNext(); } //由于要删除,需要先显示出来 System.out.print(node.getValue()); node=circle.deleteFromCircle(node); node=node.getNext(); } sc.close(); } }
顺序表:
package test1; /** * 顺序表实现约瑟夫环 * * @author Xu Yiqing * */ public class JosephCircle2 { /** * 约瑟夫环构造方法 * * @param number 将数据添加到顺序表 * @param start 约瑟夫环开始索引 * @param distance 删除元素间隔 */ public JosephCircle2(int number[], int start, int distance) { MyLinearList list = new MyLinearList(number.length); for (int i = 0; i < number.length; i++) { list.append(number[i]); } int i = start; while (list.length() > 1) { i = (i + distance - 1) % list.length(); System.out.print(list.get(i)); list.remove(i); } System.out.print(list.get(0)); } /** * 自定义顺序表 * * @author Xu Yiqing * */ class MyLinearList { private Integer[] elements; private Integer len; /** * 构造方法 * * @param 拷贝顺序表 */ public MyLinearList(MyLinearList list) { this.len = list.len; this.elements = new Integer[list.elements.length]; for (int i = 0; i < list.elements.length; i++) { this.elements[i] = list.elements[i]; } } /** * 构造方法 * * @param size 大小 */ public MyLinearList(int size) { this.elements = new Integer[size]; this.len = 0; } /** * 判空 * * @return */ public boolean isEmpty() { return this.len == 0; } /** * 大小 * * @return 大小 */ public int length() { return this.len; } /** * 获取某个元素 * * @param index 所有 * @return 元素 */ public Integer get(int index) { if (index >= 0 && index < this.len) { return this.elements[index]; } else { return null; } } /** * 设置某个元素 * * @param i 索引 * @param value 值 */ public void set(int i, Integer value) { if (i >= 0 && i < this.len) this.elements[i] = value; else try { throw new Exception("无法设置"); } catch (Exception e) { e.printStackTrace(); } } /** * 插入某个元素 * * @param i 索引 * @param value 值 */ public void insert(int i, Integer value) { if (i < 0) { i = 0; } if (i > this.len) { i = this.len; } if (this.len == this.elements.length) { Integer[] temp = this.elements; this.elements = new Integer[this.elements.length + 1]; for (int j = 0; j < temp.length; j++) { this.elements[j] = temp[j]; } } for (int j = this.len - 1; j >= i; j--) { this.elements[j + 1] = this.elements[j]; } this.elements[i] = value; this.len++; } /** * 在尾部添加 * * @param value 值 */ public void append(Integer value) { this.insert(this.len, value); } /** * 删除某个元素 * * @param i 索引 * @return 删除是否成功 */ public boolean remove(int i) { if (this.len == 0 || i < 0 || i >= this.len) { return false; } for (int j = i; j < this.len - 1; j++) { this.elements[j] = this.elements[j + 1]; } this.elements[this.len - 1] = null; this.len--; return true; } /** * 清除 * * @return */ public boolean removeAll() { this.len = 0; return true; } /** * 销毁 * * @return */ public boolean destroy() { this.removeAll(); this.elements = null; return true; } /** * 搜寻某个元素是否存在 * * @param value 值 * @return 找不到返回-1 */ public Integer search(Integer value) { int index = this.indexOf(value); return index == -1 ? null : this.elements[index]; } /** * 根据值定位第一个索引 * * @param value 值 * @return 第一个索引 */ private int indexOf(Integer value) { for (int i = 0; i < this.len; i++) { if (this.elements[i].equals(value)) { return i; } } return -1; } /** * 是否包含 * * @param value 值 * @return 第一个值的索引 */ public boolean contain(Integer value) { return this.indexOf(value) >= 0; } /** * 判断某个对象是否和该顺序表一致 */ public boolean equals(Object object) { if (this == object) return true; if (object instanceof MyLinearList) { MyLinearList list = (MyLinearList) object; if (list.length() == this.length()) { for (int i = 0; i < list.length(); i++) { if (!this.get(i).equals(list.get(i))) return false; } return true; } } return false; } } }
测试类:
package test1; import java.util.Scanner; /** * 测试类 * @author Xu Yiqing * */ public class Test2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n=sc.nextInt(); int[] arr=new int[n]; for(int i=0;i<arr.length;i++) { arr[i]=i+1; } new JosephCircle2(arr, 0, m); sc.close(); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 国外程序员整理的Java资源大全(全部是干货) 2020-06-12
- 2020年深圳中国平安各部门Java中级面试真题合集(附答案) 2020-06-11
- 2020年java就业前景 2020-06-11
- 04.Java基础语法 2020-06-11
- Java--反射(框架设计的灵魂)案例 2020-06-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash