【数据结构】：顺序表里一些主要功能的实现

框架

线性表

• 是 n 个具有相同特征的数据元素的有限序列
  常见的线性表：顺序表、链表、栈、队列…

---

• 线性表在逻辑上是线性结构，也就是连续的一条直线
  但在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式进行存储
  

顺序表

• 顺序表其实就是一个数组，是用一段物理地址连续的存储单元依次存储数据元素的线性结构
• 其访问速度比较快，给定下标情况下，速度为 O (1)
• 适用于经常进行下标查找或者更新的操作

顺序表实现逻辑

1. 创建一个 IList 接口，用来放所有相关的方法
2. 创建一个 MyArrayList 类，数组成员变量 int[ ] elem 用来放数据，整形成员变量 usedSize 用来记录数组里面的数据个数
3. 在 MyArrayList 类里面实现 IList 接口，并重写里面的方法

各种方法的实现

boolean isFull ()——判断数组是否放满

• 直接返回 usedSize == elem.length 即可，相等为 true，不相等为 false

    @Override
    public boolean isFull() {
        return usedSize == elem.length;
    }

void add (int data)——在数组末尾插入新元素

1. 首先用 isFUll() 方法判断数组是否装满，若装满，就调用 Arrays 的 copyOf(elem, 2*elem.length) 方法对数组进行扩容
2. 将第 usedSize 位的数组元素赋值为 data
3. usedSize++;

    @Override
    public void add(int data) {
        if(isFull()){
            //如果满了，就扩容为原来的两倍
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize] = data;
        usedSize++;
    }

void add (int pos, int data)——在指定位置插入元素

1. 首先判断传入的参数 pos 是否合法
   • 我们创建一个 checkPosOfAdd(int pos) 方法来进行判断，
   • 若 (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++;

    @Override
    public void add(int pos, int data) {
        //判断输入的 pos 是否合法
        try{
            checkAddPos(pos);
        }catch (PosNotLegalException e){
            e.printStackTrace();
        }
        //判断数组是否装满
        if(isFull()){
            elem = Arrays.copyOf(elem,elem.length*2);
        }
        //移动元素
        for (int i = usedSize - 1; i >= pos; i--) {
            elem[i + 1] = elem[i];
        }
        //插入元素
        elem[pos] = data;
        usedSize++;
    }

void checkPosOfAdd (int pos)——检查传入 add 方法中的 pos 是否合法

• 若不合法则抛出一个自定义异常 PosNotLegalException

private void checkPosOfAdd(int pos) throws PosNotLegalException{  
    if(pos < 0 || pos > usedSize){  
        //自定义一个异常类：PosNotLegalException  
        throw new PosNotLegalException("pos位置不合法");    
    }
}

PosNotLegalException——传入参数不合法的自定义异常

• 继承自运行时异常 RuntimeException

public class PosNotLegalException extends RuntimeException{  
    public PosNotLegalException(String msg) {  
        super(msg);  
    }
}

boolean contain (int toFind)——判断是否包含某个元素

1. 遍历数组 usedSize 次
2. 当 elem[i] == toFind 时，return true;
3. 找不到，return false;

public boolean contains(int toFind) {  
    //只需要寻找useSize次  
    for (int i = 0; i < usedSize; i++) {  
        if(elem[i]==toFind){  
            return true;  
        }    
    }   
    return false;  
}

int indexOf (int toFind)——查找某个对应元素的位置

1. 遍历数组 usedSize 次
2. 当 elem[i] == toFind 时，return i;
3. 找不到，return 0;

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 是否合法
   • 创建 checkPosOfGetAndSet(int pos) 方法来进行判断
   • 若 (pos < 0 || pos > usedSize)，则抛出自定义异常 PosNotLegalException
2. 合法，return elem[pos];

public int get(int pos) {  
    try{  
        checkPosOfGet(pos);  
    }catch (PosNotLegalException e){  
        e.printStackTrace();  
    }    return elem[pos];  
}  

void checkPosOfGetAndSet (int pos)——判断输入 get 和 set 方法的值是否合法

• 若不合法则抛出一个自定义异常 PosNotLegalException

private void checkPosOfGet (int pos) throws PosNotLegalException{  
    if(pos < 0 || pos > usedSize){  
        throw new PosNotLegalException("pos位置不合法");  
    }
}

void set (int pos, int value)——将 pos 位置的元素设为 value

1. 判断传入的参数 pos 是否合法
   • 调用 checkPosOfGetAndSet(int pos) 方法来进行判断
   • 若 (pos < 0 || pos > usedSize)，则抛出自定义异常 PosNotLegalException
2. 赋值：elem[pos] == value;

public void set(int pos, int value) {  
    try {  
        checkPosOfGetAndSet(pos);  
    } catch (PosNotLegalException e) {  
        e.printStackTrace();  
    }    
    elem[pos] = value;  
}

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("没有要找的关键字");  
    }    for (int i = pos; i < usedSize - 1; i++) {  
        elem[i] = elem[ i + 1];  
    }    this.usedSize--;  
}

void removeAll (toRemove)——删除所有出现的关键字

1. 使用 for 循环多次调用 indexOf() 方法，若 pos != -1，则继续操作
2. 移动元素，将后面的元素从后往前依次向后移一位 `elem[pos] = elem[pos + 1];
3. usedSize--;

public void removeAll(int toRemove) {  
    for (int i = 0; i < usedSize; i++) {  
        int pos = indexOf(toRemove);  
        if (pos != -1) {  
            for (int j = pos; j < usedSize - 1; j++) {  
                elem[j] = elem[j + 1];  
            }            
            usedSize--;  
        }    
    }
}

void clear ()——清空顺序表

• 因为是基本类型，直接 usedSize = 0 即可
• 若是引用类型，则需将每一个位置的数据都置为 null (防止内存泄露)

public void clear() {  
    usedSize = 0;  
}