- 一、深入理解顺序表
- 二、创建框架
- 三、代码实现
- 1. 创建一个类Seqlist
- 2. 创建主函数用来测试
- 四、分析代码的部分逻辑
- 五、总结
顺序表（Sequence List）
- 顺序表的定义：顺序表是在计算机内存中以数组的形式保存的线性表
- 顺序表的特点：表中元素的逻辑顺序与其物理顺序相同
- 顺序表的缺点：
（1） 顺序表中间/头部的插入删除，时间复杂度为O(N)
（2）增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗
（3）若增容按2倍增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间
- 创建一个可以定义类型、可以实现功能的类，创建一个数组（表示顺序表中的元素），再创建变量 size（ 表示数组中当前拥有的元素），接着创建四个接口（函数）来实现顺序表的增删查改功能
- 创建一个主函数用来测试
- 记住一个核心的要点：用数组实现顺序表，就要满足顺序表的规则，
第一，数组下标要保持有序
第二，数组中间元素不可断 - 此外，应该注意一些细小的点：
（1）每个接口接收的是什么，返回的是什么
（2）增加元素前，我们要初始化数组元素为0
（3）增加元素时，我们要考虑从哪个位置增加，要考虑是否有数组越界的情况，要考虑是否需要扩容数组的长度
（4）删除元素时，我们要考虑删除元素对应的数组下标
（5）每次实现函数的时候，考虑此时数组中存在的元素个数 size
public class Seqlist {
//创建一个数组（表示顺序表中的元素）
int[] element;
//size表示数组中当前拥有的元素
int 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;
}
//pos>=0 && pos<=this.size-1 表示从数组中间插入元素
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;
}
}
//从顺序表中查找下标对应的元素--------查 ✓
//与findNum函数的逻辑相同，可以再添加一个findPos函数，但是没有必要
//从顺序表中查找元素并修改--------改 ✓
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) {
Seqlist test = new Seqlist();
test.initial();
test.print();
System.out.println("-----------------");
test.addNum(0,1);
test.addNum(1,3);
test.addNum(2,5);
test.addNum(3,7);
test.addNum(4,9);
test.addNum(5,2);
test.addNum(6,4);
test.print();
System.out.println("-----------------");
test.addNum(2,0);
test.print();
System.out.println("-----------------");
test.deleteNum(1);
test.print();
System.out.println("-----------------");
test.deleteNum(7);
test.print();
System.out.println("-----------------");
test.findNum(5);
System.out.println("-----------------");
test.modifyNum(3,99);
test.print();
test.emptyList();
test.print();
System.out.println("-----------------");
}
}
四、分析代码的部分逻辑
- 在上面的 addNum 接口中
我们要理解如何操作，使得中间任一位置插入元素，画图实现！
例如，我们插入一个元素 data = 6，数组下标 pos = 2，那么数组下标为 2 之后的元素都要往后挪，挪动的时候不能覆盖，可以参考下图的挪动顺序自我理解。先挪 4，再挪 2， 9 ，7，5.
此外我们更应该注意 for 循环的区间问题
- 在上面的 deleteNum 接口中
我们要理解如何操作，使得中间某一位置元素被删除，画图实现！
例如，我们删除一个元素 data = 5，数组下标 pos = 2，那么数组下标为 2 之后的元素都要往前挪，挪动的时候不能覆盖，可以参考下图的挪动顺序自我理解。先挪 7，再挪 9， 2 ，4.
此外我们更应该注意 for 循环的区间问题
- 小白之前用 C 代码写了通讯录的一个小项目，里面创建了一个结构体，很多功能都是通过指针实现的。结构体与 Java 的类很相似，但是 Java 的类可强太多了！它可以创建成员函数对成员变量直接操作，之后通过实例化对象，这就使实现功能十分方便了！也就是完全面对对象，省略了很多繁杂过程，一点也不花里胡哨的，真的十分银杏了！
- 本篇博客在于深入理解顺序表的逻辑，因为这融合了很多基础知识，比如数组、类、对象等等…此外，十七这些天也顺利适应了 Java 风格。
