顺序表
顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序储存是指用一组地址连续的存储单元，一次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数组元素存储在相邻的物理存储单元中，即通过数组元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
api设计
| 方法 | 解释 |
|---|---|
| SequenceList(int capacity) | 创建容量为capacity的SequenceList对象 |
| public vlid clear() | 清空线性表 |
| public bollean isEmpty() | 判断线性表是否为空，是返回true，否返回false |
| public int length | 获取当前线性表又多少个元素 |
| public T get(int i) | 读取并返回线性表中的第i个元素的值 |
| public void insert(int i,T t) | 再线性表的第i个索引前插入一个值为t的数据元素 |
| public void insert(T t) | 向线性表中添加一个元素t |
| public T remove(int i) | 删除并返回线性表中第i个数组元素 |
| public int indexOf(T t) | 返回线性表中首次出现指定的数组元素的位序号，若不存在，则返回-1. |
| 成员变量 | private T[ ] eles ：存储元素的数组 private int N ：当前线性表的长度 |
代码示例
public class SequenceList<T> implements Iterable<T>{
//存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
//初始化数组
this.eles =(T[])new Object[capacity];
//初始化元素的个数为0
this.N = 0;
}
//将一个线性表置为空表，重置
public void clear(){
this.N=0;
}
//判断当前线性表是否为空表
public boolean isEnpty(){
return N==0;
}
//获取线性表的长度
public int length(){
return N ;
}
//获取指定位置的元素
public T get(int i){
return this.eles[i];
}
//向线性表中添加元素t
public void insert(T t){
eles[N++] = t;
}
//在i位置中插入元素
public void insert(int i,T t){
//先将所有从i元素开始所有元素都往后移动一位
int n=N;
while(true){
if(n<=i){
eles[i]= t;
N++;
break;
}
eles[n+1] = eles[n];
n--;
}
}
//删除指定位置索引i处的元素，并返回该元素
public T remove(int i){
//记录索引i处的值
T init = eles[i];
//让索引i后面元素一次向前移动一位即可
for(int index=i;index<N-1;index++){
eles[index]=eles[index+1];
}
//元素个数减一
this.N--;
return init;
}
//查找元素第一次出现的位置
public int indexOf(T t){
for(int i=0;i<N;i++){
if(eles[i].equals(t)){
return i;
}
}
return -1;
}
public Iterator<T> iterator(){
return new SIterator();
}
private class SIterator implements Iterator{
private int cusor;
public SIterator(){
this.cusor=0;
}
public boolean hasNext(){
return cusor<N;
}
public Object next(){
return eles[cusor++];
}
}
顺序表的容量可变
在前面实现了储存表的基本代码后，我发现，新建了一个顺序表后，容量是固定的，也就是说你每次创建表前，就要指定好又多少个元素，超过就会报错，因此，在日常的业务中就显得不便，于是这个时候我们就需要将顺序表的容量变成可变的，这样即便我们一开始初始化的顺序表的大小比较小，将来即便超出了范围也没有问题。
扩容方式：
当我们添加元素的时候发现，数组的储存已经超过了最大限制，这个时候我们就需要用到数组扩容，扩容的方式是新建一个长度是原数组两倍的新数组，然后将原来的数组的元素复制到新的数组当中。这样我们就相当于将之前的数组的元素容量扩大到两倍。
缩小容量方式：
当我们删除元素的时候，发现数组当前存在的元素是当前数组容量的1/4的时候，我们就需要将数组进行缩小容量，缩小到数组容量的1/2以此来减小对服务器的消耗。最后将原数组的元素复制到新数组中即可。
和上面示例代码主要的变化是多了一个扩/缩 容的方法，然后需要在每次增加元素进数组的时候或者减少元素的时候对数组进行判断，看看是否超额/少额度，超额或者少额，如果超出/少于就调用扩容方法。
扩容方法代码示例：
//根据参数newSize，重置size的大小
public void resize(int newSize){
//定义一个临时数组，指向原数组
T[] temp=eles;
//创建新数组
eles=(T[])new Object[newSize];
//把原数组的元素复制到新数组
for(int i=0;i<N;i++){
eles[i]=temp[i];
}
}最后附上完整的示例代码
public class SequenceList<T> implements Iterable<T>{
//存储元素的数组
private T[] eles;
//记录当前顺序表中的元素个数
private int N;
//构造方法
public SequenceList(int capacity){
//初始化数组
this.eles =(T[])new Object[capacity];
//初始化元素的个数为0
this.N = 0;
}
//将一个线性表置为空表，重置
public void clear(){
this.N=0;
}
//判断当前线性表是否为空表
public boolean isEnpty(){
return N==0;
}
//获取线性表的长度
public int length(){
return N ;
}
//获取指定位置的元素
public T get(int i){
return this.eles[i];
}
//向线性表中添加元素t
public void insert(T t){
if(N==eles.length){
resize(2*eles.length);
}
eles[N++] = t;
}
//在i位置中插入元素
public void insert(int i,T t){
if(N==eles.length){
resize(2*eles.length);
}
//先将所有从i元素开始所有元素都往后移动一位
int n=N;
while(true){
if(n<=i){
eles[i]= t;
N++;
break;
}
eles[n+1] = eles[n];
n--;
}
}
//删除指定位置索引i处的元素，并返回该元素
public T remove(int i){
if(N< eles.length/4){
resize(eles.length/2);
}
//记录索引i处的值
T init = eles[i];
//让索引i后面元素一次向前移动一位即可
for(int index=i;index<N-1;index++){
eles[index]=eles[index+1];
}
//元素个数减一
this.N--;
return init;
}
//查找元素第一次出现的位置
public int indexOf(T t){
for(int i=0;i<N;i++){
if(eles[i].equals(t)){
return i;
}
}
return -1;
}
//根据参数newSize，重置size的大小
public void resize(int newSize){
//定义一个临时数组，指向原数组
T[] temp=eles;
//创建新数组
eles=(T[])new Object[newSize];
//把原数组的元素复制到新数组
for(int i=0;i<N;i++){
eles[i]=temp[i];
}
}
public Iterator<T> iterator(){
return new SIterator();
}
private class SIterator implements Iterator{
private int cusor;
public SIterator(){
this.cusor=0;
}
public boolean hasNext(){
return cusor<N;
}
public Object next(){
return eles[cusor++];
}
}
} 
评论 (0)