前言:
今天小伙伴们对“java约瑟夫”大概比较注意,你们都想要学习一些“java约瑟夫”的相关知识。那么小编也在网上网罗了一些有关“java约瑟夫””的相关内容,希望小伙伴们能喜欢,我们一起来学习一下吧!我们每天做着和昨天一样的事情,却又希望明天的结果与今天不一样。呵呵!!!前言
程序 = 数据结构 + 算法。其重要性不言而喻,不多说,直接进入正题。
线性表是由零个或多个元素组成的有限序列,通俗来说就是具有线性一样的性质----好家伙,说了跟没说一样。
线性表从存储方式来看可以分为顺序存储与链式存储。顺序表有几个基础操作,插入,删除,及查询。当然,还有一些很多其它的操作,为了简单,本例将通过代码实现顺序存储与链式存储。
一、顺序存储
如下图,按照顺序存储下去,一般采用数组实现
插入:
删除:
第一步,将待删除数据删除
第二步,将后面数据往前挪
查询:
可直接通过索引位置查询。
不多说,直接上代码。
public class ZListImpl implements ZList { // 数据集合 private ZElement[] datas; // 数组最大长度 private final int maxLength; /** * 数组初始长度为0 */ private int length = 0; public ZListImpl(int maxLength) { this.maxLength = maxLength; this.datas = new ZElement[maxLength]; } @Override public void delete(int index) { if (index < 0 || index > length - 1) { System.err.println("index越界"); } // 当前索引位置数据后面的往前挪一位 for (int i = index; i < length; i++) { datas[i] = datas[i+1]; } //数组长度减一 length--; } @Override public void add(ZElement zElement) { // 不允许插入空值 if (zElement.getData() == null) { return; } // 当前数组长度大于最大长度,暂不支持动态扩容 if (length >= maxLength) { System.err.println("该链表数据已满"); } datas[length] = zElement; // 数组长度增加 length++; } @Override public int getId(ZElement element) { // -1 表示不存在该元素 if (element.getData() == null) { return -1; } // 如果有多个元素匹配,返回第一个索引值 for (int i = 0; i < length; i++) { if (datas[i].getData().equals(element.getData())) { return i; } } return -1; } @Override public int length() { return length; }}二、链式存储
链式存储的特性节点信息存储着两部分内容,数据与上/下一个节点的地址,这里以单链表为例。
插入,画的略显粗糙
如图,我们要在节点2后面插入5,需要将节点5的后继指向节点2下一个节点-即3,然后再将节点2和后继节点指向5,完成插入操作
删除
第一步,当前节点的后继节点指向待删除节点的后继节点
第二步,。。。。,对没有了
查询
使用游标,从头节点开始,如果查询不到,游标往后走,遍历到下一个节点,直到查询到数据或全部链表查询完成。
代码如下(删除的代码)
import javax.xml.soap.Node;public class ZLinkImpl implements ZLinkInterface { // 初始化头节点 ZNode head = null; // 链表长度 public int size = 0; @Override public void add(String target, String data) { ZNode targetNode = get(target); if (targetNode == null) { add(data); } else { ZNode zNode = new ZNode(data); zNode.setNext(targetNode.getNext()); targetNode.setNext(zNode); size++; } } @Override public void delete(String data) { ZNode pNode = getPreNode(data); ZNode next = pNode.getNext(); // 不是最后一个节点 if (next != null) { // 上一节点数据指向当前节点的下一个节点 pNode.setNext(next.getNext()); } else { pNode.setNext(null); } this.size--; } @Override public ZNode get(String data) { if (this.size != 0 && data != null) { ZNode next = head; while (next != null) { if (data.equals(next.getData())) { return next; } else { next = next.getNext(); } } } return null; } public ZNode getPreNode(String data) { if (this.size != 0 && data != null) { ZNode next = head.getNext(); while (next != null) { if (data.equals(next.getNext().getData())) { return next; } else { next = next.getNext(); } } } return null; } // 没有目标,采用尾插法插入到链表最后 public void add(String data) { // 当前链表为空 if (this.size == 0) { head = new ZNode(data); } else { // 当前链表游标,获取链表最后游标 ZNode thisCur = head; while (thisCur != null && thisCur.getNext() != null) { thisCur = thisCur.getNext(); } // 待插入链表插入到当前节点后面 ZNode willNode = new ZNode(data); thisCur.setNext(willNode); } size++; }}
主类
public class ZLinkMain { public static void main(String[] args) { ZLinkImpl zLink = new ZLinkImpl(); zLink.add("1"); zLink.add("2"); zLink.add("3"); zLink.add("4"); zLink.add("2","5"); System.out.println(zLink.size); }}
调试看到的结果 1 -> 2 -> 5- > 3 ->4
三、总结
顺序存储相对于链式存储来说
优点:快速存取元素,无需记录元素关联的数据
缺点:数据碎片化,插入删除效率较低
当然,其实里面还有一些bug以及很多设计的不完善的地方,最完整的代码可以看看jdk List集合的源码,里面有各种各样的api,例如倒置,两个线性表之间 操作,底层还有自动扩容等,都是需要我们大量时间去研究和学习的,话说回来,理解了与写代码是两回事儿。
还有快慢指针(可用来查询链表中间值),静态链表(数组实现了链式存储,虽然现在基本上不用,其中的思考方式值得我们学习),约瑟夫算法以及魔术师发牌的实现,有机会我会把这几个算法整理一下发出来。从一个学习者来说,我已经懂了,如果要结合代码将这个问题讲清楚,我还得再学习,反之,如果我能把这些问题全部都写出来,那我肯定掌握了这些内容,这也是我写文章的初衷。最后,希望大家做时间的朋友,共勉。最最后附上代码地址。
标签: #java约瑟夫