顺序表详解(Java)

目录

（）

顺序表

初始化

（）

方法实现

1> display 遍历(简单)

2> isFull 是否为满

3> size 顺序表的大小

 4> add 增加在最后位置(考虑是否满了) (难)

5> add 增加到指定位置(是否为满)

6> isEmpty 是否为空

7> contain  是否包含某个元素 (简单)

8> indexOf 查找某个位置的元素 

 9> get 获取 pos 位置的元素

10> set 给 pos 位置的元素设为 value 

11> remove 移除某个数据

12> clear 清空顺序表

如何使用

小结

---

线性表定义: 

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

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

顺序表

顺序表是一个动态扩容的数组.

我们来实现一个顺序表, 需要通过这个数组写一些方法实现各种功能.

初始化

先来给顺序表创建一个数组.

    public static final int DEFAULT_SIZE = 10;    public int[] elem;    public int usedSize = 0;    public MyArrayList() {        this.elem = new int[DEFAULT_SIZE];    }

 分配一个数组, usedSize 表示这个数组初始时里面0个数据, DEFAULT_SIZE 表示数组默认大小为10.我们也可以自己创建顺序表时来指定数组的默认大小, 通过构造函数传参来实现.

    public MyArrayList(int size) {        this.elem = new int[size];    }

方法实现

如何实现各种功能, 先来实现一个接口, 通过这个接口来说明我们想要实现的功能:

package myList;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();    // 判断是否为满    public boolean isFull();    // 判断是否为空    public boolean isEmpty();}

然后写一个类来实现其中的代码:

package myList;public class MyArrayList implements IList{    public static final int DEFAULT_SIZE = 10;    public int[] elem;    public int usedSize = 0;    public MyArrayList() {        this.elem = new int[DEFAULT_SIZE];    }    public MyArrayList(int size) {        this.elem = new int[size];    }    @Override    public void add(int data) {    }    @Override    public void add(int pos, int data) {    }    @Override    public boolean contains(int toFind) {        return false;    }    @Override    public int indexOf(int toFind) {        return 0;    }    @Override    public int get(int pos) {        return 0;    }    @Override    public void set(int pos, int value) {    }    @Override    public void remove(int toRemove) {    }    @Override    public int size() {        return 0;    }    @Override    public void clear() {    }    @Override    public void display() {    }    @Override    public boolean isFull() {        return false;    }    @Override    public boolean isEmpty() {        return false;    }}

1> display 遍历(简单)

    @Override    public void display() {        for(int i = 0; i  
2> isFull 是否为满
 
    @Override    public boolean isFull() {        return this.usedSize == elem.length;    }
 
3> size 顺序表的大小
 
    @Override    public int size() {        return this.usedSize;    }
 
 4> add 增加在最后位置(考虑是否满了) (难)
 
注意: 满了就扩容: 怎么扩容? 使用 copyOf 方法.
 
    @Override    public void add(int data) {        if(isFull()) {            elem = Arrays.copyOf(elem, 2*elem.length);        }        this.elem[this.usedSize] = data;        usedSize++;    }
 
5> add 增加到指定位置(是否为满)
 
注意: 看放的位置是否合法, 不能是负数或者太靠后不连贯了.
 
解决方法: 写一个方法来检查位置是否合法, 不合法的话抛出异常
 
此处的异常是自定义异常
 
package myList;public class PosIllegality extends Exception {    public PosIllegality(String msg) {        super(msg);    }}
 
    private void checkPosOnAdd(int pos) throws PosIllegality {        if(pos  usedSize) {            System.out.println("位置不合法");            throw new PosIllegality("插入元素下标异常: " + pos);        }    }
 
代码实现:  
 
    @Override    public void add(int pos, int data) {        try {            checkPosOnAdd(pos);        }catch (PosIllegality e) {            e.printStackTrace();            return;        }        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++;    }
   
步骤:
  
1> 检查位置合法性
  
2> 检查是否数组满了
  
3> 开始进行位移: 从最后一个有效的数据开始往后移动, 当i  
6> isEmpty 是否为空
 
    @Override    public boolean isEmpty() {        return this.usedSize == 0;    }
 
7> contain  是否包含某个元素 (简单)
 
注意: 看是否为空
 
    @Override    public boolean contains(int toFind) {        if(isEmpty()) {            return false;        }        for(int i = 0; i  
8> indexOf 查找某个位置的元素 
 
注意: 看是否为空
 
    @Override    public int indexOf(int toFind) {        if(isEmpty()) {            return -1;        }        for(int i = 0; i  
9> get 获取 pos 位置的元素
 
注意: 判断位置是否合法, 其中的异常是自定义异常
 
package myList;public class MyArrayListEmpty extends Exception {    public MyArrayListEmpty(String msg) {        super(msg);    }}
 
package myList;public class PosIllegality extends Exception {    public PosIllegality(String msg) {        super(msg);    }}
  
    @Override    public int get(int pos) throws MyArrayListEmpty {        try {            checkPosOnGet(pos);        }catch (PosIllegality e) {            e.printStackTrace();            return -1;        }        if(isEmpty()) {            throw new MyArrayListEmpty("获取指定下标元素时, 顺序表为空!");        }        return elem[pos];    }    private void checkPosOnGet(int pos) throws PosIllegality {        if(pos  usedSize) {            System.out.println("不合法");            throw new PosIllegality("获取指定下标的元素异常: " + pos);        }    }
 
10> set 给 pos 位置的元素设为 value 
 
注意:  pos 位置是否合法
 
package myList;public class PosIllegality extends Exception {    public PosIllegality(String msg) {        super(msg);    }}
 
    @Override    public void set(int pos, int value) {        try {            checkPosOnSet(pos);        } catch (PosIllegality e) {            throw new RuntimeException(e);        }        elem[pos] = value;    }    private void checkPosOnSet(int pos) throws PosIllegality {        if(pos  usedSize) {            System.out.println("不合法");            throw new PosIllegality("获取指定下标的元素异常: " + pos);        }    }
 
11> remove 移除某个数据
 
注意: 看是否有这个数据.没有的话可以抛出异常.有的话就依次覆盖前一个数据
 
    @Override    public void remove(int toRemove) {        int index = indexOf(toRemove);        if(index == -1) {            System.out.println("没有找到这个数字!");            return ;        }        for(int i = index; i  
12> clear 清空顺序表
 
最简单的一种方式
 
    @Override    public void clear() {        this.usedSize = 0;    }
 
当里面的数据时引用数据类型时需要释放内存
 
    @Override    public void clear() {        for (int i = 0; i  
如何使用
 
可以通过 main 函数调用这个类中方法
 
package myList;/** * 类的使用者 */public class Test {    public static void main(String[] args) {        MyArrayList myArrayList = new MyArrayList();        myArrayList.display();    }}
  
小结
 
当添加元素或者删除元素时 注意: usedSize++ 或者 usedSize--
 
加入和删除 注意实现的过程.
 
注意下标不合法等异常