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