一、顺序表的构造函数
1.1接口
public interface IList { // 新增元素,默认在数组最后新增 void add(int data); // 在 pos 位置新增元素 void add(int pos, int data); // 判定是否包含某个元素 boolean contains(int toFind); // 查找某个元素对应的位置 int indexOf(int toFind); // 获取 pos 位置的元素 int get(int pos); // 给 pos 位置的元素设为 value void set(int pos, int value); //删除第一次出现的关键字key,更新 void remove(int toRemove); // 获取顺序表长度 int size(); // 清空顺序表 void clear(); // 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的 void display(); //顺序表判满 boolean isFull(); //顺序表判空 boolean isEmpty(); }
1.2 类定义
class MyArrayList implements IList { private int[] elem; private int usedSize; public static final int DEFAULT_SIZE=2; public MyArrayList(){ this.elem=new int[DEFAULT_SIZE]; this.usedSize=0; } public MyArrayList(int capacity){ this.elem=new int[capacity]; } }
二、实现的功能
2.1检查容量
如果当前容量不足，则扩大2倍。
private void checkCapacity(){//检查容量 if(isFull()){ //扩容 elem=Arrays.copyOf(elem,elem.length*2); } }
2.2表尾插入元素
在插入前，首先检查容量，容量不足就先扩容，之后继续插入。
public void add(int data) { checkCapacity(); elem[this.usedSize]=data; this.usedSize++; }
2.3判满
public boolean isFull() { /* if(usedSize==elem.length){ return true; } return false;*/ return usedSize==elem.length; }
2.4指定位置增加元素
首先要检查指定位置是否合法：
private void checkPosOnAdd(int pos) throws PosIllegality{ if(pos<0 || pos>usedSize){ System.out.println("插入不合法!"); throw new PosIllegality("插入元素下标异常:>"+pos); } }
public void add(int pos, int data) { try{ checkPosOnAdd(pos);//检查pos位置合法性 }catch (PosIllegality e){ e.printStackTrace();//捕获异常并打印插入元素下标异常 return; } checkCapacity(); //1.从最后一个有效的数据开始往后移动，当i小于pos就结束 for (int i = usedSize-1; i >=pos ; i--) { elem[i+1]=elem[i]; } //2.存放元素到pos位置 elem[pos]=data; //3.顺序表长度加一 usedSize++; }
2.5判空
public boolean isEmpty() { return usedSize==0; }
2.6检查数据是否在表中
public boolean contains(int toFind) { if(isEmpty()){ return false; } for (int i = 0; i < usedSize; i++) { //如果是查找引用类型，一定要用equals方法!!! if(elem[i]==toFind){ return true; } } return false; }
2.7查找指定元素的下标
public int indexOf(int toFind) { if(isEmpty()){ return -1; } for (int i = 0; i < usedSize; i++) { //如果是查找引用类型，一定要用equals方法!!! if(elem[i]==toFind){ return i; } } return -1; }
2.8获取指定位置的元素
同样需要检查指定位置是否合法：
private void checkPosOnGetAndSet(int pos) throws PosIllegality{ if(pos<0 || pos>=usedSize){ System.out.println("获取元素下标不合法!"); throw new PosIllegality("获取元素下标异常:>"+pos); } }
public int get(int pos)throws MyArrayListEmpty { if(isEmpty()){ throw new MyArrayListEmpty("顺序表为空!!"); } checkPosOnGetAndSet(pos); return elem[pos]; }
2.9设置表中指定位置的元素
public void set(int pos, int value) { checkPosOnGetAndSet(pos); elem[pos]=value; }
2.10删除元素
删除元素，首先要找到要删除元素的下标，可以调用上面写过的函数。
public void remove(int toRemove) { /** * 1.找到删除的数字下标 * 2.挪动数据 * 3.usedSize-- */ int index=indexOf(toRemove); if(index==-1){ System.out.println("无此元素:>"+toRemove); return; } for (int i = index; i < usedSize-1; i++) { elem[i]=elem[i+1]; } usedSize--; }
2.11获取元素个数
public int size() { return this.usedSize; }
2.12清空顺序表
public void clear() { this.usedSize=0; //如果是引用数据类型的清空，通过for循环把元素置空即可 }
2.13显示顺序表
public void display() { for (int i = 0; i < this.usedSize; i++) { System.out.println(elem[i]+" "); } System.out.println(); }
