【数据结构】顺序表

线性表

我们要讲顺序表，就不得不先讲线性表，因为顺序表是线性表的一种。

线性表的定义

线性表顾名思义就是将数据像线一样组织起来的表。
可以联想现实中排队来理解。

线性表的特征：

• 线性表的数据元素之间有顺序。
• 除了首元素和尾元素，每个元素都有一个前驱和后继。

顺序表

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

顺序表接口的实现

自己实现一个顺序表（存储int类型数据），将顺序表作为一个类，我们实现一些接口即一些成员方法来实现数据的增删查改。

public class SeqList {private int[] elem;private int usedSize;// 默认构造方法SeqList(){   }// 将顺序表的底层容量设置为initcapacitySeqList(int initcapacity){   }// 新增元素,默认在数组最后新增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 位置的元素设为 valuepublic void set(int pos, int value) {   }//删除第一次出现的关键字keypublic void remove(int toRemove) {   }// 获取顺序表长度public int size() { return 0; }// 清空顺序表public void clear() {   }}

默认构造方法

我们默认最开始开辟10个空间的数据。

private static final int DEFAULT_SIZE = 10;public SeqList() {this.elem= new int[DEFAULT_SIZE];}

将顺序表的底层容量设置为initcapacity

传入数组长度，以数组长度来开辟空间。

private static final int DEFAULT_SIZE = 10;public SeqList(int initcapacity) {this.elem= new int[initcapacity];}

尾插

新增元素,默认在数组最后新增。
考虑要点：

• 当前顺序表是否已经满了，满了就增加空间。
• 增加了一个元素usedSize加1。

 public void add(int data) {if(isFull()){elem = Arrays.copyOf(elem,elem.length * 2);}elem[usedSize++] = data;}/*** 判断当前的顺序表是不是满的！** @return true:满   false代表空*/private boolean isFull() {return usedSize == elem.length;}

在 pos 位置新增元素

在pos下标插入元素。
注意事项：

• 当前顺序表是否已经满了，满了就增加空间。
• 给的pos位置是否合法，不合法就抛异常。
• 使用从后向前循环遍历将pos位置后的元素后移。
• 增加了一个元素usedSize加1。

private boolean checkPosInAdd(int pos) throws PosIllegalException{if(pos < 0 || pos > usedSize){throw new PosIllegalException("位置不合法");}return true;}// 在 pos 位置新增元素public void add(int pos, int data) {try{if(checkPosInAdd(pos)){if(isFull()){elem = Arrays.copyOf(elem,elem.length * 2);}for (int i = usedSize; i > pos ; i--) {elem[i] = elem[i-1];}elem[pos] = data;usedSize++;}}catch(PosIllegalException e){e.printStackTrace();}}

判定是否包含某个元素

看给定的数据是否包含在该顺序表中。
直接循环遍历即可，找到返回true，没有返回false。

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

查找某个元素对应的位置

看给定的数据在该顺序表中下标。
直接循环遍历即可，找到返回下标，没有返回-1。

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

获取 pos 位置的元素

将pos位置的元素输出。
注意事项：

• 检查pos是否合法

public int get(int pos) {try{if(checkPosInAdd(pos)){return elem[pos];}}catch(PosIllegalException e){e.printStackTrace();}return 0;}

给 pos 位置的元素设为 value

将pos位置元素修改。
注意事项：

• 检查pos是否合法。

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

删除第一次出现的关键字key

将第一次出现的key删除。
注意事项：

• 循环遍历查找。
• 用找到的key后面的元素一一向前面覆盖。
• usedSize减1。

public void remove(int key) {for (int i = 0; i < usedSize; i++) {if(elem[i] == key){for (int j = i; j < usedSize - 1; j++) {elem[j] = elem[j + 1];}usedSize--;}}}

获取顺序表长度

获取顺序表的长度在这就是指有用数据的个数，即usedSize。

public int size() {return usedSize;}

清空顺序表

将顺序表中的内容置为空。
注意事项：

• 因为真正顺序表存储泛型，一一遍历将元素置为空，下面用置为0代替。
• UsedSize也置为0。

public void clear() {for (int i = 0; i < usedSize; i++) {elem[i] = 0;}usedSize = 0;}

Java中的ArrayList

在Java中提供了ArrayList类来表示顺序表。

实现的接口

接口说明：

1. RandomAccess接口表示支持随机访问。
2. Cloneable接口表示支持克隆。
3. Serializable接口表示支持序列化。

构造方法

Java提供了3个构造方法如表：

方法	方法用途介绍
ArrayList()	无参构造
ArrayList(Collection<? extends E> c)	利用其他 Collection 构建 ArrayList
ArrayList(int initialCapacity)	指定顺序表初始容量

常用方法

提供的常用方法和我们上面自己实现的差不多。

顺序表的优劣

优点

顺序表的优点有如下几个方面：

1. 支持随机访问。
2. 给定下标查询快。

缺点

1. 空间不够需要扩容，会有内存的浪费。
2. 头部和中间的插入删除要摞动数据。

练习

练习的链接如下：
杨辉三角