目录
线性表
我们要讲顺序表，就不得不先讲线性表，因为顺序表是线性表的一种。
线性表的定义
线性表顾名思义就是将数据像线一样组织起来的表。
可以联想现实中排队来理解。
线性表的特征：
- 线性表的数据元素之间有顺序。
- 除了首元素和尾元素，每个元素都有一个前驱和后继。
顺序表
顺序表是用一段物理地址连续的存储单元就像人挨人排队一样，
依次存储数据元素的线性结构，一般情况下采用数组存储。
在数组上完成数据的增删查改。
顺序表接口的实现
自己实现一个顺序表（存储int类型数据），将顺序表作为一个类，我们实现一些接口即一些成员方法来实现数据的增删查改。
public class SeqList {
private int[] elem;
private int usedSize;
// 默认构造方法
SeqList(){ }
// 将顺序表的底层容量设置为initcapacity
SeqList(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 位置的元素设为 value
public void set(int pos, int value) { }
//删除第一次出现的关键字key
public 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类来表示顺序表。
实现的接口
接口说明：
- RandomAccess接口表示支持随机访问。
- Cloneable接口表示支持克隆。
- Serializable接口表示支持序列化。
构造方法
Java提供了3个构造方法如表：
常用方法
提供的常用方法和我们上面自己实现的差不多。
顺序表的优劣
优点
顺序表的优点有如下几个方面：
- 支持随机访问。
- 给定下标查询快。
缺点
- 空间不够需要扩容，会有内存的浪费。
- 头部和中间的插入删除要摞动数据。
练习
练习的链接如下：
杨辉三角