关于java:数据结构之线性表只需一文看清实操

8次阅读

共计 9072 个字符，预计需要花费 23 分钟才能阅读完成。

 线性表全名线性存储构造是最根本、最简略、也是最罕用的一种数据结构，专门用于存储逻辑关系为 "一对一" 的数据。

数据类型统一
数据的逻辑关系都具备一对一关系
数据元素无限 (专业术语为：存在惟一一个被称为“第一个”的数据元素，存在惟一一个被称为“最初一个”的数据元素)
是有序序列（专业术语为：除第一个元素外，每个元素都有惟一的一个”间接前驱“。除最初一个元素外，每一个元素都有惟一的”间接后继“）

 线性表，基于数据在理论物理空间中的存储状态，又可细分为 ** 程序表（顺序存储构造）** 和 ** 链表（链式存储构造）**。

 程序表，个别应用数组实现。也就是在内存中找个初始地址，而后数据元素顺次排队，数组大小有两种形式指定——动态调配和是动静扩大。

随机拜访：可通过首地址和元素序号在单位工夫 O(1) 内找到指定的元素。
存储密度高：存储密度高是因为每个结点存储空间指用来存储数据元素，没有别的额定开销。
物理地位相邻：物理地位和逻辑地位一样，放弃相邻，因而插入和删除元素须要挪动大量元素，比拟耗时。这是物理构造相邻的所有数据结构的通病，尽管拜访快，然而如果有频繁的增删挪动操作，就会效率很低。

长处：
空间利用率高（理由：间断寄存）
存取速度高效，通过下标间接进行存储和读取。（想想排队哈）
顺序存储，随机读取（不算是长处，算是特点）

插入和删除比较慢。（想想插队，前面的全副须要往后移一个位）
程序表开始时就要定义一个长度，因而是存在空间限度的。当须要存储的元素个数可能多于程序表元素时，可能呈现“溢出”问题。

 用一组任意的存储单元存储线性表的数据元素（这组存储单元能够是间断的，也能够是不间断的），包含数据域和指针域，数据域存数据，指针域批示其后继的信息。

 随机存储、程序读取：物理地位和逻辑地位不同，物理地位随机存储，但都通过指针域连成线，能够按逻辑程序读取

插入和删除的速度快，保留原有的物理程序（只扭转下指针。想想上述的插队问题就明确了）。
没有空间限度，根本只与内存空间大小无关。（满天飞）
随机存储，程序读取（算是特点）

查找元素比较慢（不能进行索引拜访，只能从头结点开始程序查找）
占用额定的空间用来存储指针（不是间断寄存的（满天飞理解下），空间碎片多）
造成空间节约。

/**
 * 线性表接口
 * @author gxw
 * @date 2021/11/1 早晨 21:50
 */
public interface LinearList {

    /**
     * 查找办法
     */

    // 查找，是否蕴含 g 元素
    boolean contains(Object g);

    // 查找，返回 g 元素所在位置
    int indexOf(Object g);

    // 查找，返回第 i 地位的元素
    Object getByIndex(int i);

    /**
     * 增加办法
     */
    // 将元素插入到第 i 个地位
    void add(int i, Object g) throws Exception ;

    // 将元素插入到最初
    void add(Object g) throws Exception ;

    // 将 g 元素插入到 x 元素之前
    boolean addBefore(Object x, Object g) throws Exception;

    // 将 g 元素插入到 x 元素之后
    boolean addAfter(Object x, Object g) throws Exception;


    /**
     * 删除办法
     */

    // 删除第 i 个元素
    void remove(int i) throws Exception ;

    // 删除第一个为 g 的元素
    void remove(Object g) throws Exception ;

    /**
     * 批改办法
     */

    // 将第 i 个元素替换为 g
    boolean replace(int i, Object g);

    // 将 x 元素全副替换为 g
    boolean replaceAll(Object x, Object g);

    /**
     * 返回线性表大小
     */
    int getSize();

    /**
     * 判断线性表是否为空
     */
    boolean isEmpty();

    /**
     * 输入线性表
     */
    void display();}

/**
 * 线性表之程序表（顺序存储构造）* @author gxw
 * @date 2021/11/1 早晨 21:51
 */
public class SequenceList implements LinearList {
    // 申明大小为 maxSize 的程序表
    private Object[] myList;// 程序表的存储空间
    private int size;// 程序表以后的长度
    private int maxSize;// 程序表最大的长度

    // 构造方法来初始化程序表
    public SequenceList(int maxSizeParam){
        // 设置程序表的初始长度为 0
        size = 0;
        // 设置程序表的最大长度
        maxSize = maxSizeParam;
        // 实例化程序表
        myList = new Object[maxSize];
    }

    // 是否蕴含 g 元素
    @Override
    public boolean contains(Object g) {// 工夫复杂度 O(n)
        for (Object x : myList) {if(x.equals(g))
                return true;
        }
        return false;
    }

    // 获取 g 元素在第几个地位
    @Override
    public int indexOf(Object g) {// 工夫复杂度 O(n)
        for(int i = 0;i < size;i++){if(myList[i].equals(g))
                return i;
        }
        return -1;
    }

    // 获取第 i 地位的元素
    @Override
    public Object getByIndex(int i) {// 工夫复杂度 O(1)
        // 判断是否合乎现有长度
        if(i < 0 || i > size)
            return null;
        return myList[i];
    }

    @Override
    public void add(int i, Object g) throws Exception {// 工夫复杂度 O(n)
        // 判断程序表是否曾经满员
        if(size == maxSize)
            throw new Exception("程序表已满员，不可插入！");// 手动抛出异样

        // 判断 i 是否在正确范畴内
        if(i < 0 || i > size)
            throw new Exception("插入地位不合理，不可插入！");// 手动抛出异样

        // 筹备执行插入，在插入之前，将要插入地位的元素往后移
        for(int j = size;j > i;j--){myList[j] = myList[j - 1];
        }
        // 执行插入
        myList[i] = g;
        // 现有程序表长度减少 1
        size++;
    }

    @Override
    public void add(Object g) throws Exception {// 工夫复杂度 O(1)
        // 判断程序表是否曾经满员
        if(size == maxSize)
            throw new Exception("程序表已满员，不可插入！");// 手动抛出异样
        // 执行插入，插入到最初
        myList[size] = g;
        // 现有长度加一
        size++;
    }

    @Override
    public boolean addBefore(Object x, Object g) throws Exception {// 工夫复杂度 O(n)
        // 判断程序表是否曾经满员
        if(size == maxSize)
            return false;

        // 先获取 x 元素所在位置
        int index = indexOf(x);

        if(index < 0)
            return false;

        // 将 x 元素以及后继元素往后移
        add(index, g);
        return true;
    }

    @Override
    public boolean addAfter(Object x, Object g) throws Exception {// 工夫复杂度 O(n)
        // 判断程序表是否曾经满员
        if(size == maxSize)
            return false;

        // 先获取 x 元素所在位置
        int index = indexOf(x);

        if (index < 0)
            return false;
        // 将 x 元素的后继元素往后移
        add(index + 1, g);
        return true;
    }

    @Override
    public void remove(int i) throws Exception {// 工夫复杂度 O(n)
        // 判断程序表是否曾经为空
        if(size == 0)
            throw new Exception("程序表已空，无奈删除！");// 手动抛出异样

        // 判断 i 元素是否在 0 -size 范畴内
        if(i < 0 || i > size)
            throw new Exception("角标超出范围，无奈删除！");// 手动抛出异样

        // 将 i 元素之后后继元素往前移
        for(int j = i;j < size;j++){myList[j] = myList[j + 1];
        }
        // 程序表长度减一
        size--;
    }

    @Override
    public void remove(Object g) throws Exception {// 工夫复杂度 O(n)
        // 判断程序表是否曾经为空
        if(size == 0)
            throw new Exception("程序表已空，无奈删除！");// 手动抛出异样
        // 查找元素的地位
        int index = indexOf(g);

        if(index >= 0){
            // 删除元素，并将后继元素往前移
            remove(index);
        }else{throw new Exception("程序表无此元素，无奈删除！");// 手动抛出异样
        }

    }

    @Override
    public boolean replace(int i, Object g) {// 工夫复杂度 O(1)
        // 判断程序表是否曾经为空
        if(size == 0)
            return false;

        // 判断 i 是否在 0 -size 范畴内
        if(i < 0 || i > size)
            return false;

        // 执行替换，将 i 元素的值替换为 g
        myList[i] = g;
        return true;
    }

    @Override
    public boolean replaceAll(Object x, Object g) {// 工夫复杂度 O(n)
        // 判断程序表是否曾经为空
        if(size == 0)
            return false;
        // 暂存角标字符串
        String indexStr = "";
        // 取出元素为 x 的所有角标
        for (int i = 0;i < size;i++){if(myList[i].equals(x)){indexStr += i + ",";}
        }
        indexStr = indexStr.substring(0, indexStr.length() - 1);
        String[] indexArr = indexStr.split(",");
        // 将取出的所有角标全替换为 g 元素
        for (int i = 0;i < indexStr.split(",").length;i++){int index = Integer.parseInt(indexArr[i]);
            // 设置值
            myList[index] = g;
        }
        return true;
    }

    @Override
    public int getSize() {return size;}

    @Override
    public boolean isEmpty() {return size == 0;}

    @Override
    public void display() {for (int i = 0;i < size;i++){System.out.print(myList[i] + " ");
        }
        System.out.println("展现程序表完结：一共长度为：" + size);
    }
}

public static void main(String[] args) throws Exception {
        /**
         * 程序表
         */
        SequenceList sequenceList = new SequenceList(10);
        // 增加
        sequenceList.add("sequence");
        sequenceList.add("hello");
        sequenceList.add("world!");
        sequenceList.add("hello");
        sequenceList.display();
        // 指定角标增加
        sequenceList.add(1, "哈哈");
        sequenceList.display();
        // 在指定元素之前增加
        sequenceList.addBefore("哈哈", "呼呼");
        sequenceList.display();
        // 在指定元素之后增加
        sequenceList.addAfter("哈哈", "嘿嘿");
        sequenceList.display();
        // 替换
        sequenceList.replace(1, "略略");
        sequenceList.display();
        // 将指定元素值全都替换成设置元素值
        sequenceList.replaceAll("hello", "HELLO");
        sequenceList.display();
        // 删除
        sequenceList.remove(1);
        sequenceList.display();
        // 指定元素删除
        sequenceList.remove("HELLO");
        sequenceList.display();}

后果：

/**
 * 单链表采纳了结点，所以须要以下定义
 * 次要两个属性，一个是数据域 (存放数据内容)，一个是指针域 (寄存下一个的结点的地址)
 */
public class Node {
    // 数据域
    private Object data;
    // 指针域
    private Node next;

    public Node(){this.data = new Object();
        this.next = null;
    }

    public Node(Object data, Node next){
        this.data = data;
        this.next = next;
    }

    public Node(Object data){this.data = data;}

    public Object getData() {return data;}

    public void setData(Object data) {this.data = data;}

    public Node getNext() {return next;}

    public void setNext(Node next) {this.next = next;}
}

/**
 * 线性表之链表（链式存储构造）* @author gxw
 * @date 2021/11/1 早晨 21:53
 */
public class LinkedList implements LinearList {private Node headNode = new Node();// 定义一个头空结点
    private int size;// 定义一共有几个结点

    @Override
    public boolean contains(Object g) {
        Node node = headNode;// 从头结点开始
        for(int i = 0;i < size;i++){if(node.getData().equals(g)){return true;}
            // 拜访下一个结点
            node = node.getNext();}
        return false;
    }

    @Override
    public int indexOf(Object g) {
        Node node = headNode;// 从头结点开始
        // 因为头结点不存数据，所以间接获取子结点数据
        node = node.getNext();
        for(int i = 0;i < size;i++){if(node.getData().equals(g)){return i;}
            // 拜访下一个结点
            node = node.getNext();}
        return -1;
    }

    @Override
    public Object getByIndex(int i) {
        Node node = headNode;// 从头结点开始
        for(int j = 0;j < i;j++){
            // 拜访下一个结点, 直到拜访的第 i 个地位
            node = node.getNext();}
        return node.getData();}

    @Override
    public void add(int i, Object g) throws Exception {
        // 如果 i 不在 0 -size 范畴
        if(i < 0 || i > size)
            throw new Exception("角标超出失常范畴 i：" + i);

        // 获取到第 i 个后面的结点，只须要让后面的结点指针域指到新要增加的结点上，// 本人的指针域指到第 i 个前面的结点上，就能够实现增加了
        Node node = headNode;
        for(int j = 0;j < i;j++){node = node.getNext();// 继续拜访指针域，直到拜访到第 i 个结点
        }
        // 创立新要增加的结点
        Node newNode = new Node();
        // 设置新结点的数据域
        newNode.setData(g);
        // 设置新结点的指针域，将后面获取到的结点的指针域的值，赋值给新要增加的结点
        newNode.setNext(node.getNext());
        // 而后让后面取得的结点的指针域指向新增加的指针，即可胜利增加
        node.setNext(newNode);
        // 结点数加一
        size++;
    }

    @Override
    public void add(Object g) throws Exception {
        // 在最初增加结点
        add(size, g);
    }

    @Override
    public boolean addBefore(Object x, Object g) throws Exception {
        // 获取结点所在位置
        int index = indexOf(x);

        // 如果没有匹配的结点
        if(index < 0)
            return false;

        // 在 x 结点前增加结点，相当于就是查找到结点地位以后地位
        add(index, g);
        return true;
    }

    @Override
    public boolean addAfter(Object x, Object g) throws Exception {
        // 获取结点所在位置
        int index = indexOf(x);

        // 如果没有匹配的结点
        if(index < 0)
            return false;

        // 在 x 结点后增加结点
        add(index + 1, g);
        return true;
    }

    @Override
    public void remove(int i) throws Exception {
        // 如果 i 不在 0 -size 范畴
        if(i < 0 || i > size)
            throw new Exception("角标超出失常范畴 i：" + i);

        // 删除结点，原理就是让此结点的前一个结点的指针域，指到此结点的下一个结点
        Node node = headNode;
        for (int j = 0;j < i;j++){node = node.getNext();
        }
        // 将前一个结点的指针域，指到此结点的下一个结点
        node.setNext(node.getNext().getNext());
        // 结点数减 1
        size--;
    }

    @Override
    public void remove(Object g) throws Exception {
        // 查找元素所在位置
        int index = indexOf(g);

        // 执行删除
        remove(index);
    }

    @Override
    public boolean replace(int i, Object g) {
        // 如果 i 不在 0 -size 范畴
        if(i < 0 || i > size)
            return false;

        // 找到第 i 个结点
        Node node = headNode;
        for (int j = 0;j < i + 1;j++){ // 因为头结点是空结点，所以须要略过，就 i + 1
            node = node.getNext();}
        // 而后将第 i 个结点的数据域更换为 g
        node.setData(g);

        return true;
    }

    @Override
    public boolean replaceAll(Object x, Object g) {return false;}

    @Override
    public int getSize() {return size;}

    @Override
    public boolean isEmpty() {return size == 0;}

    @Override
    public void display() {
        Node node = headNode;
        for (int i = 0;i < size;i++){node = node.getNext();
            System.out.print(node.getData() + " ");
        }
        System.out.println("展现实现，结点长度为：" + size);
    }
}

public static void main(String[] args) throws Exception {
      
        /**
         * 单链表
         */
        LinkedList linkedList = new LinkedList();
        // 增加
        linkedList.add("1");
        linkedList.add("2");
        linkedList.add("3");
        linkedList.display();

        // 在 2 之前增加
        linkedList.addBefore("2", "4");
        linkedList.display();

        // 在 2 之后增加
        linkedList.addAfter("2", "5");
        linkedList.display();

        // 查找地位
        System.out.println(linkedList.indexOf("1"));
        System.out.println(linkedList.indexOf("2"));
        System.out.println(linkedList.indexOf("3"));

        // 替换
        linkedList.replace(1, "22");
        linkedList.display();

        // 删除
        linkedList.remove("3");
        linkedList.display();}

后果：

 数据结构中，一组数据中的每个个体被称为“数据元素”（简称“元素”）。

间接前驱：

 某一元素的左侧相邻元素称为“间接前驱”

前驱元素：

 位于此元素左侧的所有元素都统称为“前驱元素”

间接后继：

 某一元素的右侧相邻元素称为“间接后继”

后继元素：

 位于此元素右侧的所有元素都统称为“后继元素”

————————————END—————————————
数据结构之线性表篇，在此完结，学习中的总结，心愿能够帮忙认真学习的你，如果总结有问题，也心愿贵人忘请斧正，谢谢！

正文完

java

发表至： java

2021-11-03

0

关于java:Synchronized解析

关于java:LeetCode–0～n1中缺失的数字

关于java:如何集成开源图表及报表到自研项目中

关于java:Scheduled的使用

关于前端:纯-Git-实现前端-CICD

关于java:数据结构之线性表只需一文看清实操

定义：

个性：

存储形式：

程序表（顺序存储构造）：

定义：

特点：

长处：

毛病：

链式存储构造：

定义：

特点：

长处：

毛病：

实操：

创立线性表接口类

程序表：

第一步：创立程序表实现类

第二步：测试

链表：

第一步：因为单链表依赖于 Node，所以创立 Node 类

第二步：创立单链表实现类

第三步：测试

其它补充：

前驱：

后继

站内搜索

关于java:数据结构之线性表只需一文看清实操

定义：

个性：

存储形式：

程序表（顺序存储构造）：

定义：

特点：

长处：

毛病：

链式存储构造：

定义：

特点：

长处：

毛病：

实操 ：

创立线性表接口类

程序表：

第一步：创立程序表实现类

第二步：测试

链表：

第一步：因为单链表依赖于 Node，所以创立 Node 类

第二步：创立单链表实现类

第三步：测试

其它补充：

前驱：

后继

站内搜索

实操：