## 一、基本概念顺序表--用顺序存储的方式实现线性表。顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。 ![顺序存储](https://www.88-bit.com/images/blog/e82ed14fa9bb4117bdb4a99bfcf2500f.png) 第一个元素的地址假设它是 LOC(A) ，计算第二个元素的地址就可以用第一个元素的地址加上第一个数据元素 a1 所消耗的存储空间，用 sizeof 表示该数据元素所消耗的存储空间大小。这里需要注意的一点是，n 与 MaxSize 是有含义上的不同的，其中 an 代表的是顺序表中最后一个数据元素，而 MaxSize 代表的是数组的最后一个存储单元。 ## 二、顺序表的定义 ```java public class InitList { private final int LEN = 8; // 数组的默认大小 private int size; // 线性表中元素的个数 private Object[] elements; // 数组元素数组 public InitList(){ this.size = 0; elements = new Object[LEN]; } } ``` ## 三、顺序表的特点 1. 随机访问，即可以在O(1)时间内找到第i个元素。data[i] 2. 存储密度高，每个节点只存储数据元素 3. 插入、删除操作不方便，需要移动大量元素 ## 四、顺序表的插入和删除 ### 4.1 插入操作 ListInsert(&L,i,e)：插入操作。在表L中的第i个位置（位序）上插入指定元素e。 ```java /** * @desc 插入操作 * @author yxs * @update yxs * @date 2020/12/15 21:40 * @param i 表示位序 * @return 是否成功 */ public boolean insert(int i,Object e){ // 指定的插入位序越界 if(i<1 || i>size+1) return false; // 当前存储空间已满，实现扩容 if(size >= elements.length) expandSpace(); for (int j=size;j>=i;j--){ elements[j] = elements[j-1]; } elements[i-1] = e; size++; return true; } // 扩容 private void expandSpace(){ Object[] a = new Object[elements.length*2]; for(int i=0;isize) return null; Object e = elements[i - 1]; for(int j=i;jsize) return null; return elements[i-1]; } ``` 时间复杂度 = O(1) ### 4.4 按值查找 ```java /** * @desc 按值查找 * @author yxs * @update yxs * @date 2020/12/15 23:07 * @param e 元素值 * @return 元素的位置（位序） */ public int getElemByValue(Object e){ for(int i=0;i

他的文章