顺序表介绍：
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
🍑顺序表一般可以分为：
- 1.静态顺序表：使用定长数组存储元素。（本篇主要围绕静态顺序表展开）
- 2.动态顺序表：使用动态开辟的数组存储。
顺序表的手动实现
📝本文将创建两个Java文件：MyArraysList.java用于顺序表的实现，Test.java用于顺序表的各个接口的测试
顺序表功能接口概览
import java.util.Arrays; public class MyArraysList { private int[] elem; private int usedSize; // 默认值是0 private static final int DEFAULT_SIZE = 4; // 定义为常量，更加安全 // 初始化顺序表 public MyArraysList() { this.elem = new int[4]; } // 对顺序表进行扩容 public void expand() {} //判断当前顺序表是否为空 public boolean isempty() {} // 判断当前顺序表是不是满了 public boolean isFull() {} // 打印顺序表 public void display() {} // 新增元素,默认在数组最后新增 public void add(int data) {} // 新增元素，在数组最前面新增 public void addHead(int data){} // 在 pos 位置新增元素 public void addPos(int pos, int data) {} // 删除表头元素 public void removeHead() {} // 删除表尾元素 public void removeTail() {} // 指定下标元素的删除 public void removePos(int pos) {} //删除第一次出现的关键字key public void remove(int toRemove) {} // 判定是否包含某个元素 public boolean contains(int toFind) { return true; } // 查找某个元素对应的位置 public int indexOf(int toFind) { return -1; } // 获取 pos 位置的元素 public int getPos(int pos) { return -1; } // 给 pos 位置的元素设为 value public void setPos(int pos, int value) {} // 获取顺序表长度 public int size() { return 0; } // 清空顺序表 public void clear() {} }
基本功能的实现
🌰对顺序表进行扩容
// 对顺序表进行扩容 public void expand() { this.elem = Arrays.copyOf(this.elem, this.usedSize * 2); System.out.println("已经成功扩容至原来的两倍"); // 给用户提醒 }
🌰判断顺序表是否为空
/** * 判断当前顺序表是否为空 * @return true->空的，false->还没空 */ public boolean isempty() { if (this.usedSize == 0) { return true; } else return false; }
🌰判断顺序表是否已满
/** * 判断当前顺序表是不是满了 * @return true->满了，false->还没满 */ public boolean isFull() { if (this.usedSize == this.elem.length) return true; else return false; }
🌰打印顺序表
// 打印顺序表 // 打印的第一种方式 public void display() { for (int i = 0; i < this.elem.length; i++) { System.out.print(this.elem[i] + " "); } System.out.println(); } // 打印的第二种方式,用Arrays.toString直接打印 public void display() { System.out.println(Arrays.toString(this.elem)); }
🌰获取顺序表的有效长度
// 获取顺序表的有效长度 public int size() { return this.usedSize; }
🌰清空顺序表
// 清空顺序表 public void clear() { for (int i = 0; i < this.usedSize; i++) { this.elem[i] = 0; } this.usedSize = 0; // 注意有效数组长度也要清零 }
四大功能
一、增加数据
🌰头插
// 新增元素，在数组最前面新增 public void addHead(int data) { if (isFull()) { System.out.println("数组满了，需要扩容"); expand(); } else { // 从usedSize下标开始，不会数组越界（此时的elem.length > usedSize) for (int i = this.usedSize; i > 0; --i) { this.elem[i] = this.elem[i - 1]; // 从后往前挪动数据，为的是给顺序表的表头腾出来 } this.elem[0] = data; // 在顺序表开头插入 this.usedSize++; // 数组有效长度加一 }
🌰尾插
//在数组最后新增 public void addTail(int data) { if (isFull()) { System.out.println("数组满了需要扩容"); expand(); } else this.elem[this.usedSize++] = data; }
🌰指定下标插入
- 1.判断pos位置是否合法（在顺序表中，数据是连续的，中间不能有空缺）
- 2. 判断顺序表是否满了，如果满了，需要扩容
- 3. 插入数据（可能需要挪动元素）
// 在 pos 位置新增元素 public void addPos(int pos, int data) { if (pos < 0 || pos > usedSize) { System.out.println("pos位置不合法"); return; } if (isFull()) { System.out.println("数组满了需要扩容"); expand(); } else { // 如果插入位置在顺序表的中间，要注意挪动元素，从后向前挪动，这样不会造成元素值的覆盖 for (int i = this.usedSize - 1; i >= pos; --i) { this.elem[i + 1] = this.elem[i]; } this.elem[pos] = data; // 挪动完毕，可以赋值插入 this.usedSize++; // 当前元素数加一 } }
二、删除数据
🌰头删
// 删除表头元素 public void removeHead() { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } // 从第一个元素开始，用后面元素的值覆盖掉前面的值，遍历整个数组就相当于把第一个元素用覆盖的方式抹去了 for (int i = 1; i < this.usedSize; i++) { this.elem[i - 1] = this.elem[i]; } this.elem[this.usedSize - 1] = 0; // 现在的最后一个元素是原来的倒数第二个元素， 所以原来的最后一个有效元素要置0 this.usedSize--; // 不要忘记改变有效数组的长度 }
🌰尾删
// 删除表尾元素 public void removeTail() { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } this.elem[this.usedSize - 1] = 0; // 直接将最后一个元素置0就完成了尾删 this.usedSize--; // 不要忘记改变有效数组的长度 }
🌰指定下标元素的删除
// 指定下标元素的删除 public void removePos(int pos) { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } if (pos < 0 || pos >= this.usedSize) { System.out.println("pos下标不合法"); } else { for (int i = pos; i < this.usedSize - 1; ++i) { this.elem[i] = this.elem[i + 1]; // 从要删除的下标开始，用后边元素的值覆盖掉前面的值，就完成了删除 } this.elem[this.usedSize - 1] = 0; // 要完整的删除,将挪动的最后一个元素的原本位置 置空 this.usedSize--;// 删除后不要忘记更改顺序表的有效长度 } }
🌰删除首次出现的指定元素
//删除第一次出现的关键字key public void removeKey(int toRemove) { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toRemove) { // 注意是this.usedSize - 1，将此时 i 之后的元素统一往前搬移一个位置 for (int j = i; j < this.usedSize - 1; ++j) { this.elem[j] = this.elem[j + 1]; } this.elem[this.usedSize - 1] = 0; // 要完整的删除，将挪动的最后一个元素的原本位置 置空 this.usedSize--; // 删除后不要忘记更改顺序表的有效长度 return; // 只删除第一次出现的 } } }
三、查找数据
🌰获取指定位置的元素
- 1.考虑要获取的位置是否合法
- 2.返回指定位置的元素
// 获取 pos 位置的元素 public int getPos(int pos) { if (pos < 0 || pos >= this.usedSize) { // 注意这里当pos==this.usedSize也是不合法的，因为此时的pos下标所要获取的是顺序表中第usedSize+1个元素 System.out.println("pos的位置不合法"); return -1; } else { return this.elem[pos]; } }
🌰获取指定元素所在的位置
// 查找某个元素所对应顺序表中的位置 public int indexOf(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) { return i; } } System.out.println("在数组中没有找到该元素"); return -1; }
🌰查找表中是否包含某个元素
/** * /判定是否包含某个元素 * @param toFind 要查找的元素 * @return true->包含， false->不包含 */ public boolean contains(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) return true; } return false; }
四、修改数据
🍑首先考虑修改的位置是否合法
🍑考虑特殊情况
// 给 pos 位置的元素设为 value public void setPos(int pos, int value) { if (pos < 0 || pos > this.usedSize) { System.out.println("pos位置不合法"); return; } if (pos == this.usedSize) { // 对这种情况要单独处理，此时相等于增加元素 this.elem[pos] = value; this.usedSize++; } else { this.elem[pos] = value; } }
总代码
📝MyArraysList.java
import java.util.Arrays; public class MyArraysList { private int[] elem; private int usedSize; // 默认值是0 private static final int DEFAULT_SIZE = 4; // 定义为常量，更加安全 // 初始化顺序表 public MyArraysList() { this.elem = new int[4]; } // 对顺序表进行扩容 public void expand() { this.elem = Arrays.copyOf(this.elem, this.usedSize * 2); System.out.println("已经成功扩容至原来的两倍"); // 给用户提醒 } /** * 判断当前顺序表是否为空 * @return true->空的，false->还没空 */ public boolean isempty() { if (this.usedSize == 0) { return true; } else return false; } /** * 判断当前顺序表是不是满了 * @return true->满了，false->还没满 */ public boolean isFull() { if (this.usedSize == this.elem.length) return true; else return false; } // 打印顺序表 public void display() { for (int i = 0; i < this.elem.length; i++) { System.out.print(this.elem[i] + " "); } // System.out.println(Arrays.toString(this.elem));或者用Arrays.toString打印也行 System.out.println(); } // 新增元素,默认在数组最后新增 public void addTail(int data) { if (isFull()) { System.out.println("数组满了需要扩容"); expand(); } else this.elem[this.usedSize++] = data; } // 新增元素，在数组最前面新增 public void addHead(int data) { if (isFull()) { System.out.println("数组满了，需要扩容"); expand(); } else { // 从usedSize下标开始，不会数组越界（此时的elem.length > usedSize) for (int i = this.usedSize; i > 0; --i) { this.elem[i] = this.elem[i - 1]; // 从后往前挪动数据，为的是给顺序表的表头腾出来 } this.elem[0] = data; // 在顺序表开头插入 this.usedSize++; // 数组有效长度加一 } } // 1、判断pos位置是否合法（在顺序表中，数据是连续的，中间不能有空缺） // 2、判断顺序表是否满了，如果满了，需要扩容 // 3、插入数据（可能需要挪作元素） // 在 pos 位置新增元素 public void addPos(int pos, int data) { if (pos < 0 || pos > usedSize) { System.out.println("pos位置不合法"); return; } if (isFull()) { System.out.println("数组满了需要扩容"); expand(); } else { // 如果插入位置在顺序表的中间，要注意挪动元素，从后向前挪动，这样不会造成元素值的覆盖 for (int i = this.usedSize - 1; i >= pos; --i) { this.elem[i + 1] = this.elem[i]; } this.elem[pos] = data; // 挪动完毕，可以赋值插入 this.usedSize++; // 当前元素数加一 } } // 删除表头元素 public void removeHead() { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } // 从第一个元素开始，用后面元素的值覆盖掉前面的值，遍历整个数组就相当于把第一个元素用覆盖的方式抹去了 for (int i = 1; i < this.usedSize; i++) { this.elem[i - 1] = this.elem[i]; } this.elem[this.usedSize - 1] = 0; // 现在的最后一个元素是原来的倒数第二个元素， 所以原来的最后一个有效元素要置0 this.usedSize--; // 不要忘记改变有效数组的长度 } // 删除表尾元素 public void removeTail() { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } this.elem[this.usedSize - 1] = 0; // 直接将最后一个元素置0就完成了尾删 this.usedSize--; // 不要忘记改变有效数组的长度 } // 指定下标元素的删除 public void removePos(int pos) { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } if (pos < 0 || pos >= this.usedSize) { System.out.println("pos下标不合法"); } else { for (int i = pos; i < this.usedSize - 1; ++i) { this.elem[i] = this.elem[i + 1]; // 从要删除的下标开始，用后边元素的值覆盖掉前面的值，就完成了删除 } this.elem[this.usedSize - 1] = 0; // 要完整的删除,将挪动的最后一个元素的原本位置 置空 this.usedSize--;// 删除后不要忘记更改顺序表的有效长度 } } //删除第一次出现的关键字key public void removeKey(int toRemove) { if (isempty()) { System.out.println("顺序表为空，删除不合法"); return; } for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toRemove) { // 注意是this.usedSize - 1，将此时 i 之后的元素统一往前搬移一个位置 for (int j = i; j < this.usedSize - 1; ++j) { this.elem[j] = this.elem[j + 1]; } this.elem[this.usedSize - 1] = 0; // 要完整的删除，将挪动的最后一个元素的原本位置 置空 this.usedSize--; // 删除后不要忘记更改顺序表的有效长度 return; // 只删除第一次出现的 } } } /** * /判定是否包含某个元素 * @param toFind 要查找的元素 * @return true->包含， false->不包含 */ public boolean contains(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) return true; } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i = 0; i < this.usedSize; i++) { if (this.elem[i] == toFind) { return i; } } System.out.println("在数组中没有找到该元素"); return -1; } // 获取 pos 位置的元素 public int getPos(int pos) { if (pos < 0 || pos >= this.usedSize) { System.out.println("pos的位置不合法"); return -1; } else { return this.elem[pos]; } } // 给 pos 位置的元素设为 value public void setPos(int pos, int value) { if (pos < 0 || pos > this.usedSize) { System.out.println("pos位置不合法"); return; } if (pos == this.usedSize) { // 对这种情况要单独处理，此时相等于增加元素 this.elem[pos] = value; this.usedSize++; } else { this.elem[pos] = value; } } // 获取顺序表长度 public int size() { return this.usedSize; } // 清空顺序表 public void clear() { for (int i = 0; i < this.usedSize; i++) { this.elem[i] = 0; } this.usedSize = 0; // 注意有效数组长度也要清零 } }
🏀测试结果
好了，今天的文章就到这里了，感谢大家的支持🥰，下篇见😁
