龙空技术网

数据结构与算法之线性表:java实现

数据杰构 153

前言:

今天小伙伴们对“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约瑟夫