一。线性表 

 

线性表（ linear list ） 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见 的线性表：顺序表、链表、栈、队列、字符串…

 

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储 时，通常以数组和链式结构的形式存储。

 

二。顺序表

 

1.概念及结构

 

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

 

而顺序表一般可以分为两类：静态顺序表、动态顺序表

 

2.顺序表的实现

 

首先我们将顺序表的成员属性以及构造函数写好，接下来实现具体接口

 

public class MyArrayList {

 

    public int[] elem;

 

    public int usedSize;//有效的数据个数，默认值为0

 

    public MyArrayList（） {//初始化一个数组，容量为5

 

        this.elem = new int[5];

 

    }

 

}

 

打印顺序表

 

只需要遍历完数组，然后将其打印出来即可

 

具体的代码实现：

 

// 打印顺序表

 

    public void display（） {

 

        for （int i = 0; i <this.usedSize ; i++） {

 

            System.out.print（elem[i]+" "）;

 

        }

 

        System.out.println（）;

 

    }

 

获取顺序表的有效长度

 

有效长度就是已经用过的元素，返回usedSize即可 

 

具体的代码实现：

 

// 获取顺序表的有效数据长度

 

    public int size（） {

 

            return usedSize;

 

    }

 

在pos位置新增元素

 

具体的操作分为四步：

 

1、判断pos位置是否合法，即pos既不能小于0，也不能大于有效数据个数

 

2、判断顺序表是否已满，如果满了，需要Arrays.CopyOf（）进行扩容

 

3、将pos后的元素依次后移，即 elem[i+1]=elem[i]

 

4、将目标元素data放入pos下标对应位置，即elem[pos]=data