目录
- 1. 顺序表的相关概念
- 1.1 线性表
- 1.2 顺序表
- 2. 功能实现
- 2.1 整体框架
- 2.2 乱七八糟的功能(bushi)
- 2.2.1 判断容量是否满
- 2.2.2 返回顺序表当前长度
- 2.2.3 扩容
- 2.2.4 清空整个顺序表
- 2.3 插入数据
- 2.3.1 头插数据
- 2.3.2 尾插数据
- 2.3.3 指定位置插入
- 2.4 删除数据
- 2.4.1 删除第一次出现的key
- 2.4.2 删除所有的的key
- 2.5 查找数据
- 2.5.1 判定是否包含某个元素
- 2.5.2 查找某个元素对应的位置
- 2.5.3 pos位置不合法异常
- 2.5.4 获取pos位置的元素：
- 2.6 修改数据
- 3. 全部代码
1. 顺序表的相关概念
1.1 线性表
线性表是一种常见的数据结构，它的特点是逻辑上是连续的线性结构，物理上不一定连续，常见的线性表有顺序表、链表、栈、队列……
1.2 顺序表
顺序表是线性表的一种，顺序表一般使用一段连续的地址来存储数据，比如数组。在数组中进行增删查改等操作。
2. 功能实现
顺序表分为静态顺序表(容量有限)和动态顺序表(可扩容)，今天我们实现的是动态顺序表，并且能存储任意类型的数据，所以使用到了泛型的知识点，如果不了解泛型的小伙伴可以参考博主之前出的预备知识：
泛型初识
2.1 整体框架
一个顺序表中需要有:数组(用于存放有效数据)、容量、当前数据个数，所以我们定义一个类，成员变量分别是存放数据的数组array、记录当前数据个数的curSize、当前顺序表的容量Capacity（默认是10，可以按需修改）。在构造方法中初始化数组的内容，这样当我们实例化一个顺序表对象后，就能初始化顺序表了。
public class SeqList<T> {
public Object[] array;//存放数据的数组
public int curSize;//当前数据个数
private int Capacity = 10;//容量
public SeqList() {
this.array = new Object[this.Capacity];
}
}
2.2 乱七八糟的功能(bushi)
2.2.1 判断容量是否满
逻辑很简单，只要判断当前数据个数的curSize是否与顺序表的容量Capacity相等即可，如果满了返回true，没满返回false
public boolean isFull() {
return this.curSize == this.Capacity;
}
2.2.2 返回顺序表当前长度
顺序表当前长度指的是当前数据的个数，直接将curSize返回即可
//返回当前长度
public int size() {
return curSize;
}
2.2.3 扩容
Arrays.copyOf方法能够实现数组的扩容并且将原有的数据拷贝。这里我们将容量扩大两倍，扩容之后别忘了将数组的容量Capacity也变为两倍
//扩容
private void dilatation() {
this.array = Arrays.copyOf(this.array, 2 * this.Capacity);
this.Capacity *= 2;
}
2.2.4 清空整个顺序表
循环遍历顺序表，将每个元素依次置为null，然后将curSize和Capacity置为0
//清空
public void clear() {
for (int i = 0; i < curSize; i++) {
array[i] = null;
}
this.curSize = 0;
this.Capacity = 0;
}
2.3 插入数据
插入数据的方式有头插、尾插、在指定位置插入。一般情况下插入数据是尾插，所以我们把尾插和在指定位置插入这两个方法重载，头插方法另外实现一个。
2.3.1 头插数据
注意几个细节：
1.插入前判断容量够不够，如果不够需要扩容
2.如果顺序表中没有元素，直接添加，将数据赋值给0下标位置的元素
3.添加之后将当前数据个数curSize加1
如果顺序表中有数据且容量足够，插入前需将数据整体往后挪动，给第一个空出位置，如图：假设顺序表中有12、23、34、45这四个数据，头插法插入数据99
//头插
public void addFront(T data) {
//如果满了,扩容
if (isFull()) {
dilatation();
}
//如果没有元素,直接添加
if (this.curSize == 0) {
this.array[0] = data;
this.curSize++;
return;
}
//开始添加
int cur = curSize;
while (cur > 0) {
array[cur] = array[cur - 1];
cur--;
}
array[0] = data;
this.curSize++;
}
2.3.2 尾插数据
插入数据前先判断容量够不够，如果不够，扩容。插入时，直接将curSize下标赋值为插入的数据即可
//尾插
public void add(T data) {
if (isFull()) {
//如果满了,扩容
dilatation();
}
this.array[curSize] = data;
this.curSize++;
}
2.3.3 指定位置插入
指定位置插入，指的是pos位置插入数据
注意几个细节：
1.需要判断pos位置的合法性pos不能小于0，pos不能大于curSize（因为顺序表中的数据是连续的）
2.需要判断容量是否足够，如果不够需要扩容
//在pos位置添加数据
public void add(int pos, T data) throws PosNotLegalException {
//判断pos位置合不合法
try {
if (pos < 0 || pos > this.curSize) {
throw new PosNotLegalException("pos位置不合法");
}
} catch (PosNotLegalException e) {
e.printStackTrace();
}
//如果满了,扩容
if (isFull()) {
dilatation();
}
//开始添加
int cur = curSize;
while (cur > pos) {
array[cur] = array[cur - 1];
cur--;
}
array[pos] = data;
this.curSize++;
}
2.4 删除数据
删除顺序表中的某个值key，分为两种，第一种是只删除第一次出现的key，第二种是删除所有的key
2.4.1 删除第一次出现的key
如果遇到了key，将key后面的元素整体往前挪动即可，让后一个位置的值覆盖前一个位置的值
//移除第一次出现的key
public void remove(T key) {
int cur = -1;
for (int i = 0; i < curSize; i++) {
if (key.equals(array[i])) {
cur = i;
//记录该位置
}
}
if (cur == -1) {
System.out.println("找不到该元素");
} else {
//挪数据
while (cur < curSize - 1) {
array[cur] = array[cur + 1];
cur++;
}
this.curSize--;
}
}
2.4.2 删除所有的的key
利用双指针算法移除所有的key,例如：在原数组（0，1，2 ，2 ，3， 0， 4 ， 2）中移除所有的2。定义一个fast变量和slow变量，如果fast下标的值不等于要删除的值，则将fast下标的值赋值给fast下标；如果fast下标的值等于要删除的值，说明这个值不是我们需要的，这时让fast一个人往前走即可
核心代码：
if(arr[fast]!=key) {
arr[slow]=arr[fast];
fast++;
slow++;
} else {
fast++;
}
//移除所有的key
public void removeAll(T key) {
//将所有的key都删除
int fast = 0;
int slow = 0;
while (fast < this.curSize) {
if (this.array[fast] != key) {
array[slow] = array[fast];
fast++;
slow++;
} else {
fast++;
}
}
this.curSize = slow;
}
2.5 查找数据
2.5.1 判定是否包含某个元素
循环遍历顺序表所有元素，如果找到了该元素，返回true，没找到返回false。需要注意的是：我们实现的是泛型类顺序表，传递的是引用类型，引用类型比较不能使用==，而是使用equals方法
// 判定是否包含某个元素
public boolean contains(T toFind) {
for (int i = 0; i < curSize; i++) {
if (toFind.equals(array[i])) {
return true;
}
}
return false;
}
2.5.2 查找某个元素对应的位置
循环遍历顺序表所有元素，找到了这个元素就返回下标，没找到则返回-1，该方法只返回第一次出现该元素的位置
// 查找某个元素第一次出现位置
public int indexOf(T toFind) {
int index = -1;
for (int i = 0; i < curSize; i++) {
if (toFind.equals(array[i])) {
index = i;
}
}
return index;
}
2.5.3 pos位置不合法异常
获取元素前需要判断传的参数pos的合法性，pos不能小于0，pos也不能大于等于当前顺序表个数curSize，如果pos合法，返回pos位置的元素即可。
判断pos位置是否合法，可以通过自定义异常来实现，如果pos不合法，抛出自定义的异常，通过try-catch捕获
定义一个pos位置不合法异常：
public class PosNotLegalException extends RuntimeException {
public PosNotLegalException(String s) {
super(s);
}
public PosNotLegalException() {
super();
}
}
2.5.4 获取pos位置的元素：
判断pos的合法性，如果不合法，抛出异常；如果合法，返回该下标元素即可
//获取pos位置的元素
public T get(int pos) {
try {
if (pos < 0 || pos >= curSize) {
throw new PosNotLegalException("pos位置不合法");
}
} catch (PosNotLegalException e) {
e.printStackTrace();
}
return (T) array[pos];
}
2.6 修改数据
修改数据：将pos下标位置修改为指定的值，同样需要判断pos的合法性，如果合法直接将pos下标的值修改即可
//将pos位置设置为value
public void set(int pos, T value) {
if (pos < 0 || pos >= curSize) {
throw new PosNotLegalException("pos位置不合法");
}
array[pos] = value;
}
3. 全部代码
自定义的异常类(pos位置不合法异常)
public class PosNotLegalException extends RuntimeException {
public PosNotLegalException(String s) {
super(s);
}
public PosNotLegalException() {
super();
}
}
SeqList.java文件
public class SeqList<T> {
public Object[] array;//存放数据的数组
public int curSize;//当前数据个数
private int Capacity = 10;//容量
//初始化
public SeqList() {
this.array = new Object[this.Capacity];
}
//扩容
private void dilatation() {
this.array = Arrays.copyOf(this.array, 2 * this.Capacity);
this.Capacity *= 2;
}
//尾插
public void add(T data) {
if (isFull()) {
//如果满了,扩容
dilatation();
}
this.array[curSize] = data;
this.curSize++;
}
//在pos位置添加数据
public void add(int pos, T data) throws PosNotLegalException {
//判断pos位置合不合法
try {
if (pos < 0 || pos > this.curSize) {
throw new PosNotLegalException("pos位置不合法");
}
} catch (PosNotLegalException e) {
e.printStackTrace();
}
//如果满了,扩容
if (isFull()) {
dilatation();
}
//开始添加
int cur = curSize;
while (cur > pos) {
array[cur] = array[cur - 1];
cur--;
}
array[pos] = data;
this.curSize++;
}
//头插
public void addFront(T data) {
//如果满了,扩容
if (isFull()) {
dilatation();
}
//如果没有元素,直接添加
if (this.curSize == 0) {
this.array[0] = data;
this.curSize++;
return;
}
//开始添加
int cur = curSize;
while (cur > 0) {
array[cur] = array[cur - 1];
cur--;
}
array[0] = data;
this.curSize++;
}
//判断容量是否满
public boolean isFull() {
return this.curSize == this.Capacity;
}
// 判定是否包含某个元素
public boolean contains(T toFind) {
for (int i = 0; i < curSize; i++) {
if (toFind.equals(array[i])) {
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int indexOf(T toFind) {
int index = -1;
for (int i = 0; i < curSize; i++) {
if (toFind.equals(array[i])) {
index = i;
}
}
return index;
}
//获取pos位置的元素
public T get(int pos) {
try {
if (pos < 0 || pos >= curSize) {
throw new PosNotLegalException("pos位置不合法");
}
} catch (PosNotLegalException e) {
e.printStackTrace();
}
return (T) array[pos];
}
//判断是否为空
public boolean isEmpty() {
return curSize == 0;
}
//将pos位置设置为value
public void set(int pos, T value) {
if (pos < 0 || pos >= curSize) {
throw new PosNotLegalException("pos位置不合法");
}
array[pos] = value;
}
//移除第一次出现的key
public void remove(T key) {
int cur = -1;
for (int i = 0; i < curSize; i++) {
if (key.equals(array[i])) {
cur = i;
//记录该位置
}
}
if (cur == -1) {
System.out.println("找不到该元素");
} else {
//挪数据
while (cur < curSize - 1) {
array[cur] = array[cur + 1];
cur++;
}
this.curSize--;
}
}
//移除所有的key
public void removeAll(T key) {
//将所有的key都删除
int fast = 0;
int slow = 0;
while (fast < this.curSize) {
if (this.array[fast] != key) {
array[slow] = array[fast];
fast++;
slow++;
} else {
fast++;
}
}
this.curSize = slow;
}
//返回当前长度
public int size() {
return curSize;
}
//清空
public void clear() {
for (int i = 0; i < curSize; i++) {
array[i] = null;
}
this.curSize = 0;
this.Capacity = 0;
}
}
今天的内容就到这里，感谢老铁们的点赞、收藏、评论~❤
