1.了解什么是顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
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(); //判断是否已满 boolean isFull(); //判断是否为空 public boolean isEmpty(); }
3.初始化ArrayList
usedSize为使用的长度
DEFAULT_SIZE = 10为默认顺序表的容量
两个构造方法
无参构造：顺序表默认大小为10；
有参构造：自定义顺序表大小；
public class MyList implements IList{ public int[] elem ; public int usedSize;//0 //顺序表的 默认大小 public static final int DEFAULT_SIZE = 10; public MyList(){ this.elem = new int[DEFAULT_SIZE]; } public MyList(int capacity){ this.elem = new int[capacity]; } }
4.实现功能接口
遍历顺序表
public void display(){ for (int i = 0; i < usedSize; i++) { System.out.print(elem[i]+" "); } System.out.println(); }
判断顺序表是否已满
public boolean isFull(){ return usedSize == elem.length; }
添加元素
checkCapacity()判断顺序表是否已满，如果已经满了则进行扩容
扩容为原来顺序表的两倍
private void checkCapacity(){ if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } } public void add(int data){ checkCapacity(); elem[this.usedSize] = data; this.usedSize++; }
指定下标添加元素
checkPosOnAdd()判断下标是否合法，如果不合法抛出异常
public 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); } catch (PosIllegality e){ e.printStackTrace(); return; } checkCapacity(); for (int i = usedSize-1; i >= pos; i--) { elem[i+1] = elem[i]; } elem[pos] = data; usedSize++; }
自定义下标不合法异常
package mylist; public class PosIllegality extends RuntimeException{ public PosIllegality(String msg){ super(msg); } }
判断顺序表是否为空
public boolean isEmpty(){ return usedSize == 0; }
查找指定元素是否存在
public boolean contains(int toFind){ if(isEmpty()){ return false; } for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind){ return true; } } return false; }
查找指定元素返回下标
public int indexOf(int toFind){ if(isEmpty()){ return -1; } for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind){ return i; } } return -1; }
获取指定下标的元素
public 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{ checkPosOnGetAndSet(pos); if(isEmpty()){ throw new MyArrayListEmpty("获取指定下标元素时" + "顺序表为空！"); } return elem[pos]; }
顺序表为空异常
package mylist; public class MyArrayListEmpty extends RuntimeException{ public MyArrayListEmpty(String msg){ super(msg); } }
修改指定下标元素的值
public void set(int pos, int value){ checkPosOnGetAndSet(pos); elem[pos] = value; }
删除指定元素
public void remove(int toRemove){ int index = indexOf(toRemove); if(index == -1){ System.out.println("没有找到"); return; } for (int i = index; i < usedSize - 1; i++) { elem[i] =elem[i+1]; } usedSize--; }
顺序表长度
public int size(){ return this.usedSize; }
回收顺序表
public void clear() { usedSize = 0; }
完整代码
package mylist; import java.util.Arrays; public class MyList implements IList{ public int[] elem ; public int usedSize;//0 //顺序表的 默认大小 public static final int DEFAULT_SIZE = 10; public MyList(){ this.elem = new int[DEFAULT_SIZE]; } public MyList(int capacity){ this.elem = new int[capacity]; } public void display(){ for (int i = 0; i < usedSize; i++) { System.out.print(elem[i]+" "); } System.out.println(); } public boolean isFull(){ return usedSize == elem.length; } private void checkCapacity(){ if(isFull()){ elem = Arrays.copyOf(elem,elem.length*2); } } public void add(int data){ checkCapacity(); elem[this.usedSize] = data; this.usedSize++; } public 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); } catch (PosIllegality e){ e.printStackTrace(); return; } checkCapacity(); for (int i = usedSize-1; i >= pos; i--) { elem[i+1] = elem[i]; } elem[pos] = data; usedSize++; } public boolean isEmpty(){ return usedSize == 0; } public boolean contains(int toFind){ if(isEmpty()){ return false; } for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind){ return true; } } return false; } public int indexOf(int toFind){ if(isEmpty()){ return -1; } for (int i = 0; i < usedSize; i++) { if(elem[i] == toFind){ return i; } } return -1; } public 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{ checkPosOnGetAndSet(pos); if(isEmpty()){ throw new MyArrayListEmpty("获取指定下标元素时" + "顺序表为空！"); } return elem[pos]; } public void set(int pos, int value){ checkPosOnGetAndSet(pos); elem[pos] = value; } public void remove(int toRemove){ int index = indexOf(toRemove); if(index == -1){ System.out.println("没有找到"); return; } for (int i = index; i < usedSize - 1; i++) { elem[i] =elem[i+1]; } usedSize--; } public int size(){ return this.usedSize; } public void clear() { usedSize = 0; } }
