目录

 线性表

顺序表的实现

顺序表各个方法的实现

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

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

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

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

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

int get(int pos) -- 获取pos位置的元素

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

void remove (int toRemove)——删除第一次出现的关键字

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

void clear ()——清空顺序表

 线性表

线性表是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛应用的数据结构,常见的线性表: 顺序表, 链表, 栈, 队列...

线性表在逻辑上是线性结构,也就是说连续的一条直线.但是在物理结构上并不一定是连续的,线性表在屋里上存储时,通常以数组和链式结构的形式存储.

 

顺序表的实现

1. 创建一个IList接口, 用来放所有相关方法

public interface IList {    boolean isFull(); // 判断数组是否放满    void add(int data); // 在数组末尾新增元素    void add(int pos,int data); // 给指定位置插入数据    boolean contain(int toFind); // 判断是否包含某个元素    int indexOf(int toFind); // 查找某个对应元素的位置    int get(int pos); // 获取pos位置的元素    void set(int pos,int value);// 将pos位置的元素设为value    void remove(int toRemove); // 删除第一次出现的关键字    void removeAll(int roRemove); // 删除所有出现的关键字    void clear(); // 清空顺序表}

2.创建一个MyArrayList 类, 数组成员变量 int[] elem 用来放数据, 整形成员变量usedSize 用来记录数组里面的数据个数

3.在 MyArrayList 类里面实现IList 接口, 并重写里面的方法

顺序表各个方法的实现

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

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

public boolean isFull() {        return size == elem.length;    }

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

1.先用isFull()方法判断数组是否放满,若装满,就调用Arrays的copyOf(elem,2*elem.length)方法对数组进行扩容

2.将第usedSize位的数组元素赋值为data

3.usedSize++

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

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

1.首先判断传入的参数pos是否合法:

                1).创建一个checkPosOfAdd(int pos)方法来进行判断

                2).若(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++

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

void checkAddPos(int pos) -- 检查传入add方法中的pos是否合法 : 

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

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

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

                继承自运行时异常 RuntimeException

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

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

1.遍历数组

2.当elem[i] == toFind 时, return true;

3.找不到,return false

public boolean contain(int toFind) {        for (int i = 0;i < usedSize;i++) {            if(elem[i] == toFind) {                return true;            }        }        return false;    }

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

1.遍历数组

2.当elem[i] == toFind 时, return i;

3.找不到 return -1;

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是否合法

        1)创建 checkPosOfGetAndSet(int pos) 方法来进行判断

        2)若 (pos < 0 || pos >= usedSize) , 则抛出自定义异常 PosNotLegalException

2.合法, return elem[pos]

public int get(int pos) {        try {            checkPosOfGetAndSet(pos);        } catch (PosNotLegalException e) {            e.printStackTrace();        }        return elem[pos];    }    private void checkPosOfGetAndSet(int pos) {        if(pos < 0 || pos >= usedSize) {            throw new PosNotLegalException("pos位置不合法");        }    }

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

1. 判断传入的参数pos是否合法

        1).调用checkPosOfGetAndSet(int pos) 方法来判断

        2).若 (pos < 0 || pos >= usedSize) , 则抛出自定义异常 PosNotLegalException

2.赋值: elem[pos] == value;

@Override    public void set(int pos, int value) {        try {            checkPosOfGetAndSet(pos);        } catch (PosNotLegalException e) {            e.printStackTrace();        }        elem[pos] = value;    }private void checkPosOfGetAndSet(int pos) {        if(pos < 0 || pos >= usedSize) {            throw new PosNotLegalException("pos位置不合法");        }    }

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

void removeAll (int 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;) {            int pos = indexOf(toRemove);            if(pos != -1) {                for(int j = pos;j < usedSize - 1;j++) {                    elem[j] = elem[j+1];                }                usedSize--;            } else {                break;            }        }    }

void clear ()——清空顺序表

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

public void clear() {        usedSize = 0;    }