数据结构：顺序表的实现

顺序表是用一段物理地址连续的存储单元依次储存数据的线性结构，一般情况下采用数组储存，在数组上完成数据的增删减改。

这里我们定义一个MyArrayList类，用来实现顺序表的功能：

public class MyArrayList{int[] array;int usedsize;
public static final int DEFAULT_CAPACITY=10;
//构造方法public MyArrayList(){array=new int[DEFAULT_CAPACITY];}
}

创建一个数组，使用数组对数据进行增删查改，以及组织和描述。

有一个长度为6，有效长度是4的数组：（有效长度就是存储的有效的数据的个数）

提问：如何知道这个数组的有效长度：1.有人会说用遍历，遍历到0结束，有效长度就是就是0之前的长度。但如果用这种方法那下面这个数组有效长度就会有问题：

如果遍历到0结束，则这个数组有效长度是2，但实际这个数组有效长度是4。

所以为了更好的得到有效长度，我们定义一个新的整形变量usedsize，当数组增加一个新的元素，usedsize就加1。删减一个元素，usedsize就减1

 实现size方法：

size方法是用来求取数组有效长度的，而数字有效长度为usedsize。

public int size(){return usedsize;
}

顺序表要实现的功能：

public class MyArrayList {
private int[] array;
private int usedsize;
// 默认构造方法
public MyArrayList(){ 
}
// 新增元素,默认在数组最后新增
public void add(int data) { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int indexOf(int toFind) { return -1; }
// 获取 pos 位置的元素
public int get(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的
public void display() { }
}

 实现display方法：

display方法是用来打印数组中的数据。

（不是顺序表的方法，为了方便看测试结果给出的）

我们要将数组的有效元素打印出来，就要遍历数组。  

public void display() {for(int i=0;i<usedsize;i++){System.out.print(array[i]+" ");}
}

实现add方法：

add方法就是对数组进增加元素。

add一共有两个方法：

public void add (int data);

public void add(int pos,int data);

实现第一个add方法： 在实现增加元素的代码时，我们要判断该数组是否满了，满了就不能继续增加元素了，所以这里定义一个isFull方法来判断数组是否满了。

如果满了就需要扩容，我们又要定义一个扩容的grow的方法。

public boolean isFull(){return array.length==usedsize;
}
public void grow(){array= Arrays.copyOf(array,2*array.length);
}
public void add(int data){if(isFUll()){grow();}array[usedsize]=data;
}

实现第二个add方法时：1.不仅要判断数组是否满了，而且还要判断所提供的pos下标是否合法，即满足pos<usedsize且pos>=0，这里就可以给一个异常。

//定义一个插入下标异常类
public class PosIlleagl extends RuntimeException{public PosIlleagl(){}public PosIlleagl(String msg){System.out.println(msg);}
}
//顺序表的实现类
public class MyArrayList{
public boolean isFull(){return array.length==usedsize;
}
public void grow(){array= Arrays.copyOf(array,2*array.length);
}
public void add(int data){if(isFUll()){grow();}array[usedsize]=data;usedsize++;
}
//定义一个下表异常
private void checkpos(int pos) throws PosIlleagl{if(pos<0||pos>usesized){throw new PosIlleagl("插入位置不合法");}
}
public void add(int pos,int data){try{checkpos(pos);    if(isFUll()){grow();}
int i=0;
for(i=usedsize-1;i>=pos;i++){array[i+1]=array[i];}}
array[pos]=data;
usedsize++;
}catch(PosIlleagl e){e.printStackTrace();
}
}

 在两个add方法中的末尾都要将usesize++；

实现contains方法：

public boolean contains(int tofind)；

contains方法是用来判定数组中是否包含tofind这个元素。

第一想到的方法就是依次遍历数组进行检查。找到了返回true，没找到返回false

public boolean contains(int tofind){int i=0;
for(i=0;i<usedsize;i++){if(array[i]==tofind){return true;}}
return false;
}

实现indexOf方法：

public int indexOf(int toFind)；

indexOf方法用来查找toFind元素的所对应的下标。

也是用遍历数组的方式进行查找，找到了就返回下标，没找到就返回-1。

public int indexOf(int toFind){int i=0;for(i=0;i<usesized;i++){if(array[i]==toFind){return i;}}
return -1;
}

实现get方法：

public int get(int pos);

get方法是用来查找pos下标的值。

1.如果数组是空数组，也不能进行查找，可以给一个异常来判断。

2.这里pos的值不能小于0，也不能大于等于usedsize，之所以不能等于usedsize，因为这里usedsize的下标是没有值的。

 比如：

这里的usedsize的值已经越界了。

所以在写代码前也要进行判断下标是否合理。可以给一个异常进行判断

//定义一个插入下标异常类
public class PosIlleagl extends RuntimeException{public PosIlleagl(){}public PosIlleagl(String msg){System.out.println(msg);}
}
//给一个判断空异常的类
public EmptyException(){public EmptyException(){}public EmptyException(String msg){System.out.println(msg);}
}
//实现顺序表的类
private void isEmpty() throws EmptyException{if(usedsize==0){throw new EmptyException("顺序表为空");}
}
private void checkpos2(int pos) throws PosIlleagl{if(pos<0||pos>=usedsize){throw new PosIlleagl("pos位置不合法");}
}
public class MyArrayList{public int get(int pos){try{isEmpty();checkpos2(pos);return array[pos];}catch(EmptyException e){e.printStackTrace();}catch(PosIlleagl e){e.printStackTrace();
}
return -1;}
}

实现set方法：

public void set(int pos, int value);

set方法就是将pos下标的元素改成value。

其实看到传参中有下标pos，我们都会想到pos下标是否为异常，并判断pos下标合法性

其次是判断数组是否为空。

//定义一个插入下标异常类
public class PosIlleagl extends RuntimeException{public PosIlleagl(){}public PosIlleagl(String msg){System.out.println(msg);}
}
//给一个判断空异常的类
public EmptyException(){public EmptyException(){}public EmptyException(String msg){System.out.println(msg);}
}
//实现顺序表的类
private void isEmpty() throws EmptyException{if(usedsize==0){throw new EmptyException("顺序表为空");}
}
private void checkpos2(int pos) throws PosIlleagl{if(pos<0||pos>=usedsize){throw new PosIlleagl("pos位置不合法");}
}
public class MyArrayList{public int set(int pos,int value){try{isEmpty();checkpos2(pos);array[pos]=value;}catch(EmptyException e){e.printStackTrace();}catch(PosIlleagl e){e.printStackTrace();
}}
}

实现remove方法：

public void remove(int toRemove)；

 remove方法就是将第一次出现的toRemove元素删除

如果要删除23这个元素，,就要先找到23这个元素的下标（通过之前的indexOf方法），就要把34这个元素往前移，44也往前移。

因为这里是找元素删除，没有传入下标，所以不用判断下标是否异常。只需要判断数组是否为空（用异常来判断）

//给一个判断空异常的类
public EmptyException(){public EmptyException(){}public EmptyException(String msg){System.out.println(msg);}
}
//实现顺序表的类
private void isEmpty() throws EmptyException{if(usedsize==0){throw new EmptyException("顺序表为空");}
}
public class MyArrayList{public void remove(int toRemove){try{isEmpty();int val=indexOf(toRemove);if(val==-1){return ;}
for(int i=pos;i<usedsize-1;i++){array[i]=array[i+1];}
usedsize--;}catch(EmptyException e){e.printStackTrace();  }}
}

实现clear方法:

public void clear();

 clear方法是将数组元素清空。

因为这里我们的顺序表是基本数据类型，所以可以很简单的将usedsize=0；即可

如果是引用类型，就要将数组依次遍历，将引用类型数据置为null

public void clear(){usedsize=0;
}

代码如下：

建立一个下标不合理异常类：

public class PosIlleagl extends RuntimeException{public PosIlleagl(){}public PosIlleagl(String msg){System.out.println(msg);}
}

 建立一个空异常类：

public class EmptyException extends RuntimeException{public EmptyException(){}public EmptyException(String msg){System.out.println(msg);}
}

MyArrayList类:

public class MyArrayList{int[] array;int usedsize;public static final int DEFAULT_CAPACITY=10;//构造方法public MyArrayList(){array=new int[DEFAULT_CAPACITY];}// 新增元素,默认在数组最后新增public void add(int data) {if(isfull()){grow();}array[usedsize]=data;usedsize++;}//检查节点是否合法private void checkpos(int pos) throws PosIlleagl{if(pos<0||pos>usedsize){throw new PosIlleagl("pos位置不合法");}}private void checkpos2(int pos) throws PosIlleagl{if(pos<0||pos>=usedsize){throw new PosIlleagl("pos位置不合法");}}private void isEmpty() throws EmptyException{if(usedsize==0){throw new EmptyException("顺序表为空");}}//数组扩容private void grow(){array= Arrays.copyOf(array,2*array.length);}//判断数组是否满了private boolean isfull(){return usedsize==array.length;}// 在 pos 位置新增元素public void add(int pos, int data) {try{checkpos(pos);if(isfull()){grow();}int i=0;for(i=usedsize-1;i>=pos;i--){array[i+1]=array[i];}array[pos]=data;usedsize++;}catch(PosIlleagl e){System.out.println("插入位置不合法");e.printStackTrace();}}// 判定是否包含某个元素public boolean contains(int toFind) {int i=0;for(i=0;i<usedsize;i++){if(array[i]==toFind){return true;}}return false;}// 查找某个元素对应的位置public int indexOf(int toFind) {int i=0;for(i=0;i<usedsize;i++){if(array[i]==toFind){return i;}}return -1;}// 获取 pos 位置的元素public int get(int pos) {try{isEmpty();checkpos2(pos);return array[pos];}catch(EmptyException e){e.printStackTrace();}catch(PosIlleagl e){e.printStackTrace();}return -1;}// 给 pos 位置的元素设为 valuepublic void set(int pos, int value) {try{isEmpty();checkpos2(pos);array[pos]=value;}catch(EmptyException e){e.printStackTrace();}catch(PosIlleagl e){e.printStackTrace();}}//删除第一次出现的关键字keypublic void remove(int toRemove) {try{isEmpty();int val=indexOf(toRemove);if(val==-1){return ;}for(int i=val;i<usedsize-1;i++){array[i]=array[i+1];}usedsize--;}catch(EmptyException e){e.printStackTrace();}}// 获取顺序表长度public int size() {return usedsize;}// 清空顺序表public void clear() {usedsize=0;}// 打印顺序表，注意：该方法并不是顺序表中的方法，为了方便看测试结果给出的public void display() {for(int i=0;i<usedsize;i++){System.out.print(array[i]+" ");}}
}

顺序表的也有优缺点：

优点：因为顺序表的底层是一个数组，所以我们在查找目的下标的值的时候，时间复杂度可以到达O(1)

缺点：

（1）因为顺序表的底层是一个数组，把数据储存到连续的空间，所以在插入或者删除元素时，会将该位置后面的元素整体整体向后移或者向前移。

（2）在增容时，需要申请新的空间，然后拷贝数据，最后再释放旧的空间，造成的消耗也不小

（3）顺序表的增容一般是呈2倍增加，如果在下面这个场景下：我已经有了100个数据，数组也已经满了，但是我现在要增加5个数据，那如果我2倍增容，就会导致我多了100个内存，但只用了5个内存，内存利用率也很低。

所以为了解决上面的问题：我们引入一个新的数据结构——链表