一、什么是线性表

1、定义

线性表数据元素虽然不同，但同一线性表中的元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序偶关系。
诸如此类由n（n≥0）个数据特性相同的元素构成的有限序列称为线性表。当n=0时，称之为空表。

2、特性

存在唯一的一个被称作“第一个”的数据元素
存在唯一的一个被称作“最后一个”的数据元素
除第一个之外，结构中的每个数据元素均只有一个前驱
除最后一个之外，结构中的每个数据元素均只有一个后继

二、线性表顺序储存表示

线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示也称作线性表的顺序存储结构或顺序映像。通常，称这种存储结构的线性表为顺序表（Sequential List）。其特点是，逻辑上相邻的数据元素，其物理次序也是相邻的。
假设线性表的每个元素需占用len个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储起始位置。
则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：

    LOC(ai+1)=LOC(ai)+len
复制代码

一般来说，线性表的第i个数据元素ai的存储位置为：

LOC(ai)=LOC(a1)+(i−1) ×len
复制代码

所以只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

JAVA代码实现线性表的顺序存储结构

package com.company.struct;

/**
 * @Description SequenceList
 * @Author stopping
 * @date: 2021/6/20 21:26
 */

public class SequenceList<T> {
    /**
     * 最大长度
     * */
    private static final int MAX_SIZE = 100;

    /**
     * 列表长度
     * */
    public int size;

    /**
     * 存储数组对象
     * */
    private T[] listArray;

    /**
     * 构造函数
     * */
    public SequenceList() {
        size = 0;
        listArray = (T[]) new Object[MAX_SIZE];
    }

    /**
     * 添加元素
     * */
    public int add(T t){
        int index = size;
        listArray[size++] = t;
        return index;
    }

    /**
     * 获取集合
     * */
    public T get(int i){
        sure(i);
        return listArray[i];
    }
    /**
     * 删除元素
     * */
    public boolean remove(int i){
        /**
         * 1 2 3 4 5
         *       ^
         * remove index -> 3
         * 1 2 3 5
         * */
        sure(i);
        for (int j = i ; j < size ; j++){
            listArray[j] = listArray[j+1];
        }
        subSize();
        return true;
    }

    /**
     * 检查下标是否异常
     * */
    private boolean sure(int i){
        if (i > MAX_SIZE){
            throw new RuntimeException("最长长度为"+MAX_SIZE);
        }
        if (i > size){
            throw new RuntimeException("下标越界异常");
        }
        return true;
    }

    /**
     *  长度下标减少
     * */
    private void subSize(){
        size --;
    }

    /**
     *  长度下标增加
     * */
    private void incSize(){
        size ++;
    }
}

复制代码

三、线性表链式存储表示

1. 链式线性表

每个元素之间通过后续指针来关联，例如每个元素ai与直接后续元素ai+1通过ai的后续指针保存ai+1的存储位置。所以每个数据除了需要存储数据本身之外还需要保存后继指针。
它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点（ai（1≤i≤n）的存储映像）链结成一个链表，即为线性表。
(a1, a2,…, an)
根据指针的个数、指针方向和指针连接方式可以区分为

单链表：只有一个指针域
循环链表：尾部指针指向头部指针
双向链表：有两个指针域
二叉链表
十字链表
邻接表

2. 特征

存储单元可以是连续的，也可以是不连续的
由于每个数据元素通过指针域指向下个节点，所以无法随机读取。
但是便于插入和删除

3. 存储结构示例

线性表的单链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点（即第一个数据元素的存储映像，也称首元结点）的存储位置。同时，由于最后一个数据元素没有直接后继，则单链表中最后一个结点的指针为空（NULL）。

4. java代码实现

package com.company.struct;

/**
 * @Description LinkList 链表
 * @Author stopping
 * @date: 2021/6/23 23:17
 */

public class LinkList<T> {
    /**
     * 数据域
     * */
    private T data;
    /**
     * 指针域
     * */
    private LinkList next;

    /**
     * 增加数据元素
     * */
    public void add(T t){
        this.next = new LinkList<>(t,next);
    }

    /**
     * 获取数据元素
     * */
    public T get(int i){
        int y = 0;
        //下一个指针域
        LinkList list = next;
        //数据域不为空且下标在范围内
        while (list.data != null && y<i){
            list = list.next;
            y++;
        }
        if (list.data == null || y>i){
            throw new RuntimeException("下标越界");
        }
        return (T) list.data;
    }
    public LinkList() {
    }

    public LinkList(T data, LinkList next) {
        this.data = data;
        this.next = next;
    }

    public LinkList(T data) {
        this.data = data;
    }
}
复制代码

文章版权归作者所有，未经允许请勿转载。

THE END

后端