Java数据结构顺序表用法详解

  • Z时代
  • 2024-01-10
  • 分类：IT

1.什么是顺序表

在程序中，经常需要将一组（通常是同为某个类型的）数据元素作为整体管理和使用，需要创建这种元素组，用变量记录它们，传进传出函数等。一组数据中包含的元素个数可能发生变化（可以增加或删除元素）。

对于这种需求，最简单的解决方案便是将这样一组元素看成一个序列，用元素在序列里的位置和顺序，表示实际应用中的某种有意义的信息，或者表示数据之间的某种关系。

这样的一组序列元素的组织形式，我们可以将其抽象为线性表。一个线性表是某类元素的一个集合，还记录着元素之间的一种顺序关系。线性表是最基本的数据结构之一，在实际程序中应用非常广泛，它还经常被用作更复杂的数据结构的实现基础。

顺序表是建立在数组的基础上的，我们需要在数组的基础上实现它的特定API功能，具体有什么功能以下

2.顺序表的基本功能和结构

public class SequenceList<T> implements Iterable<T> {
    //存储元素的数据
    private T[] arr;
    //记录当前顺序表中的元素个数
    private int N;
    //构造方法
    public SequenceList(int capacity) {
        this.arr= (T[]) new Object[capacity];
        this.N=0;
    }

解析：首先我们需要一个底层的arr数组来存储元素，这里的T指的是泛型，因为我们还没确定放入的元素类型，有可能放int，String等等，所以先用泛型表示，不明白泛型的可以了解了解。其次用一个N来统计顺序表中的元素个数。在构造方法中，capacity表示我们创建时arr的初始长度，因为泛型是无法直接实例化的，这里我们可以new一个Object数组，因为Object是任何类的父类，所以T为任何类型我们都可以将Object强转为我们需要的数组，N刚开始为0即可。

下面是顺序表需要实现的基本功能

public boolean isEmpty()判断线性表是否为空
public T get(int i)获取指定位置的元素
public void add(T t)向线性表中添加元素t
public void insert(int i,T t)在i元素处插入元素t
public T remove(int i)删除指定位置i处的元素,并返回该元素
public int indexOf(T t)查找t第一次出现的位置
public void reSize(int newLength)手动实现扩容功能

3.顺序表基本功能的实现和解析

1.判断线性表是否为空

//将一个线性表置为空表
    public void clear(){
        this.N=0;
    }
    //判断当前线性表是否为空表
    public boolean isEmpty(){
        return N==0;
    }

解析：判断线性表是否为空，我们只需要返回N是否等于0即可。

2.获取指定位置的元素

    //获取指定位置的元素
    public  T get(int i){
        return arr[i];
    }

解析：数组可以直接索引对应位置的元素

3.向线性表表添加元素

//向线性表中添加元素t
    public void add(T t){
        if(N== arr.length){
            reSize(2*N);
        }
        arr[N++]=t;
    }

解析：添加时，我们首先判断数组arr是否已经装满，如果满了会先调用我们的扩容方法增加数组长度，在后面会详细解析。然后arr[N]这个位置加入元素即可，然后N会自增1，表示元素个数多了一个。

4.在位置i处插入元素

//在i元素处插入元素t
    public void insert(int i,T t){
        if(N== arr.length){
            reSize(2*N);
        }
        //把i元素开始后面的元素都向后移一位
        for(int j=N-1;j>=i;j--){
            arr[j+1]=arr[j];
        }
        N++;
        arr[i]=t;
    }

解析：插入元素我们仍然需要判断是否需要对数组进行扩容，然后我们需要通过循环将i位置后的元素都向后移一个位置，最后将t放入arr【i】位置即可，别忘记N也需要加1。

5.删除指定位置的元素，并返回该元素

//删除指定位置i处的元素,并返回该元素
    public T remove(int i){
        if(N<arr.length/4){
            reSize(N/2);
        }
        T t=arr[i];
        for(int j=i;j<N;j++){
            arr[j]=arr[j+1];
        }
        N--;
        return t;
    }

解析：在这里我们也调用了扩容方法，但这里其实我们是判断数组是否过长，当我们的存储元素的个数小于数组长度的1/4，我们最好将数组长度缩小一半，以防止对内存的浪费。这里我们先将i处的元素用一个变量t保存。然后将i处后的元素依次向前移动一位，然后让N减1，最后返回变量t即可。

6.查找t第一次出现的位置

public int indexOf(T t){
        for (int i = 0; i < N; i++) {
            if(arr[i]==t) return i;
        }
        return -1;
    }

解析：这里我们直接使用暴力遍历查找位置，当然有很多更好的查找算法可以实现，比如二分查找等等，元素不多的情况下使用哪种都可以。如果没查询到我们返回一个-1表示该表中没有需要查询的t元素。

7.手动扩容方法

 //手写扩容方法
    public void reSize(int newLength){
        T[] a=arr;
        T[] list = (T[]) new Object[N*2];
        for (int i = 0; i < arr.length; i++) {
            list[i]=a[i];
        }
        arr=list;
    }

解析：扩容方法的实现其实非常简单，就是判断直接生成一个长度为原数组两倍的数组，并把旧数组的元素遍历进新数组，然后将新数组赋值给就数组即可。之所以要会手动扩容，因为java中的集合类ArrayList就有自动扩容的功能，它的功能与逻辑结构类似我们的顺序表，懂得手动扩容使我们更容易阅读ArrayList的源码，更好的理解和掌握它。

总结：顺序表是非常简单且入门的一种数据结构，他与我们的数组几乎一致，但越是简单的东西越不能大意，我们需要做到可以熟练的手动写成它的各种功能，达到信手拈来的地步。基础学好才更易于我们学习后面更复杂的数据结构。

到此这篇关于Java数据结构顺序表用法详解的文章就介绍到这了,更多相关Java 顺序表内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持！

以上是 Java数据结构顺序表用法详解 的全部内容， 来源链接： utcz.com/p/249896.html

回到顶部