一、深入理解顺序表
顺序表（Sequence List）
- 顺序表的定义：顺序表是在计算机内存中以数组的形式保存的线性表
- 顺序表的特点：表中元素的逻辑顺序与其物理顺序相同
- 顺序表的缺点：
（1） 顺序表中间/头部的插入删除，时间复杂度为O(N)
（2）增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗
（3）若增容按2倍增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间
二、创建框架
- 创建一个可以定义类型、可以实现功能的类，在这个类中，创建一个数组（表示顺序表中的元素），再创建变量 size（ 表示数组中当前拥有的元素个数），接着创建四个函数来实现顺序表的增删查改功能
- 创建一个主函数用来测试
- 记住一个核心的要点：用数组实现顺序表，就要满足顺序表的规则，
① 数组下标要保持有序
② 数组中间元素不可断
- 此外，应该注意一些细小的点：
（1）每个函数接收的是什么，返回的是什么
（2）增加元素前，我们要初始化数组元素为0
（3）增加元素时，我们要考虑从哪个位置增加，要考虑是否有数组越界的情况，要考虑是否需要扩容数组的长度
（4）删除元素时，我们要考虑删除元素对应的数组下标
（5）每次实现函数的时候，考虑此时数组中剩余的元素个数 size
三、代码实现
1. 创建一个 SequenceList 类
import java.util.Arrays; public class SequenceList { int[] element; //创建一个数组（表示顺序表中的元素） int size; //size表示数组中当前拥有的元素 //初始化数组元素和对应的size public void initial(){ this.element = new int[5]; this.size = 0; } //向顺序表中添加元素--------增 ✓ public void addNum(int pos, int data){ expansion(); //判断是否要扩容的问题 //pos为负数时，表示数组越界，不可逆 //pos>size时，不满足顺序表对应的顺序规则 if(pos < 0 || pos > this.size){ System.out.println("无法扩容！"); return; } //表示从数组中间插入元素 if(pos >= 0 && pos <= this.size - 1){ for (int i = this.size-1; i >= pos ; i--) { this.element[i+1] = this.element[i]; } } //除了上述的两个if语句，其他的都正常添加 this.element[pos] = data; this.size++; } //扩容函数 ✓ public void expansion(){ if(this.size == this.element.length){ this.element = Arrays.copyOf(this.element, this.element.length * 2); } } //输出当前顺序表的所有元素 ✓ public void print(){ for (int i = 0; i < this.size; i++) { System.out.print(this.element[i] + " "); } System.out.println(); } //从顺序表中删除元素--------删 ✓ public void deleteNum(int data){ int pos = 0; int flag = 0; //找到要删除的元素对应的数组下标 //然后把下标赋值给pos,并用flag标记一下 for (int i = 0; i < this.size; i++) { if(this.element[i] == data){ pos = i; flag = 1; break; } } //如果没找到，有可能越界，有可能数组中就没有该元素 //不论哪种原因，直接返回就行了 if(flag == 0){ System.out.println("你所要删除的元素不在该顺序表的范围内"); return; } //如果pos位置处于顺序表的中间，那么就挪动元素进行覆盖 //如果处于尾部的元素，将被0覆盖 if(pos >= 0 && pos <= this.element.length - 1){ for (int i = pos; i < this.size - 1; i++) { this.element[i] = this.element[i+1]; } } this.size--; } //从顺序表中查找元素--------查 ✓ public void findNum(int data){ int flag = 0; //遍历数组，找到元素就把flag置成1，反之把flag置成0 for (int i = 0; i < this.element.length; i++) { if(this.element[i] == data){ flag = 1; System.out.print("你所要找的元素"+data+"，它在顺序表中对应的下标是： "); System.out.println(i); break; } } if(flag == 0){ System.out.println("找不到你所要找的元素！"); return; } } //从顺序表中查找元素并修改--------改 ✓ public void modifyNum(int data, int newNum){ for (int i = 0; i < this.element.length; i++) { if(this.element[i] == data){ this.element[i] = newNum; } } } //清空顺序表 public void emptyList(){ this.size = 0; } }
2. 创建主函数用来测试
public class Test { public static void main(String[] args) { SequenceList test = new SequenceList(); test.initial(); } }
四、分析增、删两个方法
我们主要来看一下增加元素和删除元素的这两个方法，其他的方法只需要遍历数组即可，较为简单，不再赘述。
1. addNum 方法
我们要理解如何操作，使得中间任一位置插入元素，画图实现！
例如，我们插入一个元素 data = 6，数组下标 pos = 2，那么数组下标为 2 之后的元素都要往后挪，挪动的时候不能覆盖，可以参考下图的挪动顺序自我理解。先挪 4，再挪 2， 9 ，7，5。此外我们更应该注意 for 循环的区间问题
2. deleteNum 方法
我们要理解如何操作，使得中间某一位置元素被删除，画图实现！
例如，我们删除一个元素 data = 5，数组下标 pos = 2，那么数组下标为 2 之后的元素都要往前挪，挪动的时候不能覆盖，可以参考下图的挪动顺序自我理解。先挪 7，再挪 9， 2 ，4。此外我们更应该注意 for 循环的区间问题
五、测试
（1）增加功能
public class Test { public static void main(String[] args) { SequenceList test = new SequenceList(); test.initial(); test.addNum(0,1); test.addNum(1,3); test.addNum(2,5); test.addNum(3,7); test.addNum(4,9); test.print(); test.addNum(3,8); test.print(); test.addNum(0,2); test.print(); test.addNum(7,4); test.print(); } }
输出结果：
（2）删除功能
public class Test { public static void main(String[] args) { SequenceList test = new SequenceList(); test.initial(); test.addNum(0,1); test.addNum(1,3); test.addNum(2,5); test.addNum(3,7); test.addNum(4,9); test.print(); test.deleteNum(9); test.print(); test.deleteNum(1); test.print(); test.deleteNum(5); test.print(); } }
输出结果：
（3）查找功能
public class Test { public static void main(String[] args) { SequenceList test = new SequenceList(); test.initial(); test.addNum(0,1); test.addNum(1,3); test.addNum(2,5); test.addNum(3,7); test.addNum(4,9); test.print(); test.findNum(1); test.findNum(5); test.findNum(9); test.findNum(100); } }
输出结果：
（4）修改功能
public class Test { public static void main(String[] args) { SequenceList test = new SequenceList(); test.initial(); test.addNum(0,1); test.addNum(1,3); test.addNum(2,5); test.addNum(3,7); test.addNum(4,9); test.print(); test.modifyNum(1,2); test.modifyNum(5,8); test.modifyNum(9,10); test.print(); } }
输出结果：
总结
- 本人之前用 C 代码写了通讯录的一个小项目，里面创建了一个结构体，很多功能都是通过指针实现的。结构体与 Java 的类很相似，但是 Java 的类可强太多了！它可以创建成员函数对成员变量直接操作，之后通过实例化对象，这就使实现功能十分方便了！省略了很多繁杂过程。
- 本篇博客在于深入理解顺序表的逻辑，因为这融合了很多基础知识，比如数组、类、对象等等…此外，本人这些天也顺利适应了 Java 风格。
Over. 谢谢观看哟~
