1.线性表
定义：线性表是 n 个具有相同特性的数据元素的有序序列。线性表是一种在实际中广泛使用的数据结构，常用的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上并不定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2. 顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
2.1 顺序表结构
代码实现：
public class MyArrayList implements IList{ public int[] elem; public int usedSize; // 记录数组元素个数 public static final int DEFAULT_CAACITY = 5; // 默认容量 public MyArrayList() { elem = new int[DEFAULT_CAACITY]; } }
2.2 实现顺序表接口
代码实现：
public interface IList { // 新增元素,默认在数组最后新增 public void add(int data); // 在 pos 位置新增元素 public void add(int pos, int data); // 判定是否包含某个元素 public boolean contains(int toFind); // 查找某个元素对应的位置 public int indexOf(int toFind); // 获取 pos 位置的元素 public int get(int pos); // 给 pos 位置的元素设为 value public void set(int pos, int value); //删除第一次出现的关键字key public void remove(int toRemove); // 获取顺序表长度 public int size(); // 清空顺序表 public void clear(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的 public void display(); // 判断数组是否存满元素 public boolean isFull(); // 判断数组是否为空 public boolean isEmpty(); }
2.3 打印顺序表
代码实现：
/** * 打印顺序表的所有的元素 */ @Override public void display() { for (int i = 0; i < usedSize; i++) { System.out.print(elem[i] + " "); } System.out.println(); }
2.2 实现新增元素
新增元素思想：
- 判断数组是否存满元素，如果存满则增加容量，否则存储在
elem[usedSize]位置 - 判断
pos位置是否合法，则抛出异常 - 从最后一个元素开始先前遍历到
pos位置，分别将它们都向后移动一个位置，再将元素存放到pos位置
代码实现：
/*** * 添加元素，默认添加到数组的最后位置 * @param data */ @Override public void add(int data) { // 1.判断是否满了 满了就要扩容 if (isFull()) { expansion(); } elem[usedSize] = data; usedSize++; } /*** * 给pos位置添加元素data * 从后往前移动元素 再将元素放进数组 * @param pos * @param data */ @Override public void add(int pos, int data) { checkPosOfAdd(pos); if (isFull()) { expansion(); } for (int i = usedSize - 1; i >= pos; i--) { elem[i + 1] = elem[i]; } elem[pos] = data; usedSize++; } /*** * 判断数组是否存满 * @return */ @Override public boolean isFull() { return usedSize == elem.length; } /** * 扩容数组 */ public void expansion() { elem = Arrays.copyOf(elem, 2 * elem.length); } /** * 判断pos位置是否合法 * @param pos */ private void checkPosOfAdd(int pos) { if (pos < 0 || pos > usedSize) { throw new PosException("pos位置：" + pos); } }
异常类：
public class PosException extends RuntimeException { public PosException() { } public PosException(String msg) { super(msg); } }
2.3 实现查找元素
代码实现：
/*** * 查找当前元素，是否存在 * @param toFind * @return */ @Override public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { if (toFind == elem[i]) { return true; } } return false; } /*** * 查找当前元素，并返回下标 * @param toFind * @return */ @Override public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if (toFind == elem[i]) { return i; } } return -1; }
2.3 获取指定位置的值
思路：
- 判断
pos位置是否合法，则抛出异常 - 判断数组是否为空，否则抛出异常
- 返回
elem[pos]的值
代码实现：
/*** * 获取pos位置的值 * @param pos * @return */ @Override public int get(int pos) { // 1.判断pos是否合法 checkPosOfGet(pos); // 2.判断数组是否为空 if (isEmpty()) { throw new EmptyException("顺序表为空"); } return elem[pos]; } /** * 判断pos是否合法 * @param pos */ private void checkPosOfGet(int pos) { if (pos < 0 || pos >= usedSize) { throw new PosException("pos位置：" + pos); } } /*** * 判断数组是否为空 * @return */ @Override public boolean isEmpty() { return usedSize == 0; }
异常类：
public class EmptyException extends RuntimeException { public EmptyException() { } public EmptyException(String msg) { super(msg); } }
2.4 删除元素
思路：
- 判断顺序表是否为空，如果为空抛出异常
- 查找要删除的元素
- 从删除元素的下标遍历到
usedSize - 1位置，分别将后一个元素移动到前几个位置。
代码实现：
/*** * 删除toRemove这个数字 * @param toRemove */ @Override public void remove(int toRemove) { // 1.判断数组是否为空 if (isEmpty()) { throw new EmptyException("顺序表为空，不能删除"); } int index = indexOf(toRemove); for (int i = index; i < usedSize - 1; i++) { elem[i] = elem[i + 1]; } usedSize--; }
2.5 获取顺序表的长度
思路：顺序表的长度就等于usedSize的值
/*** * 获取顺序表的长度 * @return */ @Override public int size() { return this.usedSize; }
2.6 清空顺序表
思路：将usedSize的值置为空
/*** * 清空顺序表 防止内存泄漏 */ @Override public void clear() { usedSize = 0; }
3.代码
4. OJ题
