本篇博客围绕如何构建顺序表，以及如何使用顺序表实现增删查改等功能展开
❓ 首先我们需要先理解一个概念：线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
本篇博客主题：顺序表
一. 顺序表的概念及其结构：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
1️⃣ 静态顺序表：使用定长数组存储。
2️⃣ 动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用
相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.
二. 动态实现顺序表
①.创建链表（由于链表地址是连续的这里采用数组存储）
public class MyArrayList {
public int[] elem;
public int usedSize;//有效的数据个数
public MyArrayList() {
this.elem = new int[10];
}
}
定义一个 elem 数组和一个记录数组元素个数的 numSize，并给数组开辟内存空间
②.打印顺序表
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
循环打印出数组元素即是顺序表
③.获取链表长度
public int size() {
return this.usedSize;
}
返回数组现有元素的个数即是顺序表的长度
④.在 pos 位置新增元素 （pos数值由用户输入）
public void add(int pos, int data) {
if(pos < 0 || pos > usedSize) {
System.out.println("pos 位置不合法！");
return;
}
if(isFull()) {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3、
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
进入方法先行判断用户输入的坐标合不合法，数组坐标从 0 开始，不会小于 0 ，坐标也不可以大于现有数组元素的个数
再判断顺序表是不是满了（数组现有元素等于数组长度），满了就利用 copyOf 动态开辟空间，数组 elem 指向新开辟的空间
从 pos 位置开始向后赋值，直到最后一个元素的位置停止循环，pos 位置的元素被赋值为新的数据data，最后现有数组元素个数增 1 ，就完成了元素的插入
⑤.判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return true;
}
}
return false;
}
循环遍历数组查询输入的数值，如果有返回 true 没有返回 false
⑥.查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return i;
}
}
return -1;
}
循环遍历数组查询输入的数值，如果有返回对应数值的下标就返回，否则返回 -1（即没有该元素）
⑦.获取 pos 位置的元素
public int getPos(int pos) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos 位置不合法");
return -1;//所以 这里说明一下，业务上的处理，这里不考虑 后期可以抛异常
}
if(isEmpty()) {
System.out.println("顺序表为空！");
return -1;
}
return this.elem[pos];
}
public boolean isEmpty() {
return this.usedSize==0;
}
和上面的代码一样先行判断 pos 的合法性，再判断一下顺序表是不是为空，如果为空无法得到对应顺序表数值，最后返回 pos 下标的数组元素
⑧.给 pos 位置的元素设为 value（更新 pos 下标的数值）
public void setPos(int pos, int value) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos位置不合法");
return;
}
if(isEmpty()) {
System.out.println("顺序表为空！");
return;
}
this.elem[pos] = value;
}
也是进来先行判断，最后对应的下标元素赋值为更新的数值
⑨.删除第一次出现的关键字key
public void remove(int toRemove) {
if(isEmpty()) {
System.out.println("顺序表为空！");
return;
}
int index = search(toRemove);
if(index == -1) {
System.out.println("没有你要删除的数字！");
return;
}
for (int i = index; i < this.usedSize-1; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize] = null; 如果数组当中是引用数据类型。
}
进入方法先行判断顺序表是不是为空，如果空程序结束（顺序表为空无法完成删除操作）
查找需要删除的元素的下标位置，从后向前赋值覆盖掉需要删除的元素，最后现有元素个数 -1 即可
⑩.清空顺序表
public void clear() {
this.usedSize = 0;
//如果数组中存储的是引用类型还需要循环把数组元素指向空对象
}
把现有元素个数置 0 ，不再满足上述功能的条件，即可以完成顺序表的清除
整体代码：创建顺序表
public class MyArrayList {
public int[] elem;
public int usedSize;//有效的数据个数
public MyArrayList() {
this.elem = new int[10];
}
// 打印顺序表
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i]+" ");
}
System.out.println();
}
// 获取顺序表的有效数据长度
public int size() {
return this.usedSize;
}
// 在 pos 位置新增元素
public void add(int pos, int data) {
if(pos < 0 || pos > usedSize) {
System.out.println("pos 位置不合法！");
return;
}
if(isFull()) {
this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
}
//3、
for (int i = this.usedSize-1; i >= pos ; i--) {
this.elem[i+1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return true;
}
}
return false;
}
// 查找某个元素对应的位置,找不到返回-1
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if(this.elem[i] == toFind) {
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int getPos(int pos) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos 位置不合法");
return -1;//所以 这里说明一下，业务上的处理，这里不考虑 后期可以抛异常
}
if(isEmpty()) {
System.out.println("顺序表为空！");
return -1;
}
return this.elem[pos];
}
public boolean isEmpty() {
return this.usedSize==0;
}
// 给 pos 位置的元素设为/更新 value
public void setPos(int pos, int value) {
if(pos < 0 || pos >= this.usedSize) {
System.out.println("pos位置不合法");
return;
}
if(isEmpty()) {
System.out.println("顺序表为空！");
return;
}
this.elem[pos] = value;
}
//删除第一次出现的关键字key
public void remove(int toRemove) {
if(isEmpty()) {
System.out.println("顺序表为空！");
return;
}
int index = search(toRemove);
if(index == -1) {
System.out.println("没有你要删除的数字！");
return;
}
for (int i = index; i < this.usedSize-1; i++) {
this.elem[i] = this.elem[i+1];
}
this.usedSize--;
//this.elem[usedSize] = null; 如果数组当中是引用数据类型。
}
// 清空顺序表
public void clear() {
this.usedSize = 0;
}
}
使用顺序表：
public class Test {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0,1);
myArrayList.add(1,2);
myArrayList.add(2,3);
myArrayList.add(3,4);
myArrayList.display();
//myArrayList.remove(29);
System.out.println("==============");
myArrayList.clear();
myArrayList.display();
}
}
以上就是顺序表的建立和使用，如果对大家有所帮助还请一键三连，谢谢大家的支持！！！！
