🍉线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
🍉顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
🌵顺序表概念及结构
顺序表一般可以分为：
静态顺序表：使用定长数组存储。
动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用
相比之下动态顺序表更灵活, 根据需要动态的分配空间大小.
接下来详细讲解动态顺序表的实现
🍌顺序表接口实现（注释非常详细，我👴👴都能看懂）
先把这个顺序表类的成员属性和构造函数写好
然后就是实现接下来的一个个接口
🍈打印顺序表
这里很简单，就像遍历数组一样，把顺序表遍历一遍即可
// 打印顺序表 public void display() { for (int i = 0; i < this.usedSize; i++) {//将有效元素遍历并且打印 System.out.print(this.elem[i]+" "); } System.out.println(); }
🍈在pos位置新增元素
这里思路分为以下几个步骤：
- ①判断pos是否合法
- ②判断顺序表满没满（这里还>需需要额外写一个判断方法isFull()），满了需要Arrays.copyOf()扩容
- ③pos之后的元素依次向后移动个位置
- ④将目标元素data放入这个pos位置
//判断顺序表是否满了 public boolean isFull() {//判断方法就是将有效元素个数和数组长度比较 if (usedSize==elem.length)//如果两者相等，说明这个数组已经装满了 return true; else return false; } // 在 pos 位置新增元素 public void add(int pos, int data) { if (pos>=0 && pos<=usedSize){ //首先保证pos得是合法的 if (isFull()){//判断容量是否已经满了 this.elem = Arrays.copyOf(this.elem,this.elem.length+1);//满了得扩容 } for (int i = usedSize-1 ; i >= pos ; i--){ //要从后往前移动，不能从前往后移，这样前一个位置的值移到后一个位置的值上， //那后一个位置上的值就会被覆盖，导致后边的所有值都变成与第一个移动的值一样 elem[i+1] = elem[i];//从新增元素位置之后的所有元素整体往后移动 1位 } this.elem[pos] = data;//向pos位置插入数据 this.usedSize++;//有效元素+1 } else System.out.println("位置不合法"); }
🍈获取顺序表长度
这个很简单，获取成员属性的有效长度useSize就可以了
// 获取顺序表的有效数据长度 public int size() { return this.usedSize; }
🍈判断是否包含某个元素
传入需要查找的元素，然后在所有有效元素中依次查找
// 判定是否包含某个元素 public boolean contains(int toFind) { for (int i =0 ; i<usedSize ; i++){//在有效元素里依次查找 if (elem[i]==toFind) return true; } return false; }
🍈查找某个元素对应的位置
这里可以用遍历有效元素就好了和上边一样，我只不过想复习一下二分查找，因为二分查找虽然也是一种遍历，但是可以很好的提高遍历的效率
// 查找某个元素对应的位置（复习一遍二分查找） public int search(int toFind) { int left = 0; //设置一个左下标 int right = elem.length-1;//再设置一个右下标，值为数组长度-1 while (left <= right) {//循环查找，条件就是左下标<=右下标 //=号不要忘，不然会漏掉一种情况（所查值为最后一个元素的情况） int mid=(left+right)/2;//设置中间值，用来减半需要遍历的元素，提高效率 if (elem[mid]<toFind){//如果这个中间值小于目标值，就把这个中间值的下一个元素设为左值 left = mid+1; }//与上边同理 else if (elem[mid]>toFind){ right = mid-1; } else//如果这个中间值既不大于也不小于目标值，那这个中间值就是所要查找目标值，返回其下标就好了 return mid; } System.out.println("没有这个数"); return -1; }
🍈获取pos位置的元素
传入一个位置，先判断这个位置是否合法，合法的话直接返回这个位置上的元素就好了
// 获取 pos 位置的元素 public int getPos(int pos) { if (pos>=0 && pos<=usedSize)//判断位置是否合法 return elem[pos]; else return -1;//如果位置不合法返回-1表示位置不合法 }
🍈给pos位置的元素设为value
依旧先判断位置是否合法，合法的话，直接将value赋值给这个位置覆盖掉原数据
// 给 pos 位置的元素设为 value public void setPos(int pos, int value) {//传入位置和想赋予的值 if (pos>=0 && pos<=usedSize){//判断是否合法 elem[pos]=value; } else System.out.println("pos非法"); }
🍈删除第一次出现的数据
先调用上边已经写好的查找接口判断是否有这个数据，如果有的话，就从此数据开始依次将当前数据的下一个数据覆盖当前数据实现删除功能不要忘了有效元素-1
//删除第一次出现的关键字key public void remove(int toRemove) { if (-1==this.search(toRemove)){ System.out.println("没有这个元素"); } else{ int index = this.search(toRemove);//获得要删除数据的位置（下标） for (int i = index ; i<usedSize-1 ; i++)//从此数据开始依次将当前数据的下一个数据覆盖当前数据实现删除功能 elem[i]=elem[i+1]; usedSize--;//注意删除一个元素之后，整个顺序表的有效元素也要-1嗷 } }
🍈清空顺序表
这里就用最粗暴的办法，直接将有效元素个数清零，其实不用管数组元素是否都变成0，因为下一次使用的时候又会有新的数据覆盖上去
// 清空顺序表 public void clear() { this.usedSize = 0; }
🍌顺序表的缺陷
- 1. 顺序表中间/头部的插入删除，时间复杂度为O(N)
- 2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
链表会不会存在以上的问题呢？请往下看👇👇
