框架
线性表
- 是
n个具有相同特征的数据元素的有限序列
常见的线性表：顺序表、链表、栈、队列…
- 线性表在逻辑上是线性结构，也就是连续的一条直线
但在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式进行存储
顺序表
- 顺序表其实就是一个数组，是用一段物理地址连续的存储单元依次存储数据元素的线性结构
- 其访问速度比较快，给定下标情况下，速度为 O (1)
- 适用于经常进行下标查找或者更新的操作
顺序表实现逻辑
- 创建一个
IList接口，用来放所有相关的方法 - 创建一个
MyArrayList类，数组成员变量int[ ] elem用来放数据，整形成员变量usedSize用来记录数组里面的数据个数 - 在
MyArrayList类里面实现IList接口，并重写里面的方法
各种方法的实现
boolean isFull ()——判断数组是否放满
- 直接返回
usedSize == elem.length即可，相等为true，不相等为false
@Override public boolean isFull() { return usedSize == elem.length; }
void add (int data)——在数组末尾插入新元素
- 首先用
isFUll()方法判断数组是否装满，若装满，就调用Arrays的copyOf(elem, 2*elem.length)方法对数组进行扩容 - 将第
usedSize位的数组元素赋值为data usedSize++;
@Override public void add(int data) { if(isFull()){ //如果满了，就扩容为原来的两倍 elem = Arrays.copyOf(elem,elem.length*2); } elem[usedSize] = data; usedSize++; }
void add (int pos, int data)——在指定位置插入元素
- 首先判断传入的参数 pos 是否合法
- 我们创建一个
checkPosOfAdd(int pos)方法来进行判断， - 若
(pos < 0 || pos >= usedSize)，则抛出一个自定义异常PosNotLegalException
- 再用
isFull()方法判断数组是否装满，若装满，就调用Arrays的copyOf(elem, 2*elem.length)方法对数组进行扩容 - 移动元素，将后面的元素从后往前依次向后移一位
elem[usedSize] = elem[usedSize - 1]; - 插入元素，
elem[pos] = data; usedSize++;
@Override public void add(int pos, int data) { //判断输入的 pos 是否合法 try{ checkAddPos(pos); }catch (PosNotLegalException e){ e.printStackTrace(); } //判断数组是否装满 if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } //移动元素 for (int i = usedSize - 1; i >= pos; i--) { elem[i + 1] = elem[i]; } //插入元素 elem[pos] = data; usedSize++; }
void checkPosOfAdd (int pos)——检查传入 add 方法中的 pos 是否合法
- 若不合法则抛出一个自定义异常
PosNotLegalException
private void checkPosOfAdd(int pos) throws PosNotLegalException{ if(pos < 0 || pos > usedSize){ //自定义一个异常类：PosNotLegalException throw new PosNotLegalException("pos位置不合法"); } }
PosNotLegalException——传入参数不合法的自定义异常
- 继承自运行时异常
RuntimeException
public class PosNotLegalException extends RuntimeException{ public PosNotLegalException(String msg) { super(msg); } }
boolean contain (int toFind)——判断是否包含某个元素
- 遍历数组 usedSize 次
- 当
elem[i] == toFind时，return true; - 找不到，
return false;
public boolean contains(int toFind) { //只需要寻找useSize次 for (int i = 0; i < usedSize; i++) { if(elem[i]==toFind){ return true; } } return false; }
int indexOf (int toFind)——查找某个对应元素的位置
- 遍历数组 usedSize 次
- 当
elem[i] == toFind时，return i; - 找不到，
return 0;
public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind) return i; } return -1; }
int get (int pos)——获取 pos 位置的元素
- 判断传入的参数pos是否合法
- 创建
checkPosOfGetAndSet(int pos)方法来进行判断 - 若
(pos < 0 || pos > usedSize)，则抛出自定义异常PosNotLegalException
- 合法，
return elem[pos];
public int get(int pos) { try{ checkPosOfGet(pos); }catch (PosNotLegalException e){ e.printStackTrace(); } return elem[pos]; }
void checkPosOfGetAndSet (int pos)——判断输入 get 和 set 方法的值是否合法
- 若不合法则抛出一个自定义异常
PosNotLegalException
private void checkPosOfGet (int pos) throws PosNotLegalException{ if(pos < 0 || pos > usedSize){ throw new PosNotLegalException("pos位置不合法"); } }
void set (int pos, int value)——将 pos 位置的元素设为 value
- 判断传入的参数
pos是否合法
- 调用
checkPosOfGetAndSet(int pos)方法来进行判断 - 若
(pos < 0 || pos > usedSize)，则抛出自定义异常PosNotLegalException
- 赋值：
elem[pos] == value;
public void set(int pos, int value) { try { checkPosOfGetAndSet(pos); } catch (PosNotLegalException e) { e.printStackTrace(); } elem[pos] = value; }
void remove (int toRemove)——删除第一次出现的关键字
- 调用
indexOf()方法，获取关键字的下标，并对下标进行判断，若pos == -1，则输出“未找到” - 移动元素，将后面的元素从后往前依次向后移一位
elem[pos] = elem[pos + 1]; usedSize--;
public void remove(int toRemove) { int pos = indexOf(toRemove); if (pos == -1) { System.out.println("没有要找的关键字"); } for (int i = pos; i < usedSize - 1; i++) { elem[i] = elem[ i + 1]; } this.usedSize--; }
void removeAll (toRemove)——删除所有出现的关键字
- 使用 for 循环多次调用
indexOf()方法，若pos != -1，则继续操作 - 移动元素，将后面的元素从后往前依次向后移一位 `elem[pos] = elem[pos + 1];
usedSize--;
public void removeAll(int toRemove) { for (int i = 0; i < usedSize; i++) { int pos = indexOf(toRemove); if (pos != -1) { for (int j = pos; j < usedSize - 1; j++) { elem[j] = elem[j + 1]; } usedSize--; } } }
void clear ()——清空顺序表
- 因为是基本类型，直接
usedSize = 0即可 - 若是引用类型，则需将每一个位置的数据都置为
null(防止内存泄露)
public void clear() { usedSize = 0; }
