顺序表
文章目录
- 基本结构
- 打印顺序表
- 元素的增加
- 判断数组是否已满，以及扩容
- 获取顺序表的长度
- 在pos位置添加元素
- 判定是否包含某个元素以及获取某个元素的位置
- 获取pos位置的元素以及更新pos位置的元素
- 删除第一次出现的关键字key
- 清空顺序表
- 所有完整代码
1.线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储
2.顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构,一般情况下使用数组来存储。在数组上进行数据的增删查改。
模拟实现
基本结构
public class MyArrayList { public int[] elem; public int useSize; //默认容量 private static final int DEFAULT_SIZE = 10; public MyArraylist(){ this.elem=new int[DEFAULT_SIZE]; } }
首先创建一个顺序表的类，类中有三个属性，一个elem数组(顺序表可看作数组)，一个int类型usesize(用来表示表中有效元素的个数)，一个私有的静态final变量DEFAULT_SIZE(表示数组的默认容量)
打印顺序表
public void display() { //1、数组为空打印[]; if (usedSize == 0) { System.out.println("[]"); return; } //数组不为空[1,2,3,4] StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < usedSize; i++) { sb.append(this.elem[i]); if (i < usedSize - 1) { sb.append(","); } } sb.append("]"); System.out.println(sb.toString()); }
元素的增加
public void add(int data) { //1、先判断数组是否需要扩容 if (isFull()) { grow(); } //2、增加元素 this.elem[usedSize] = data; usedSize++; }
在数组中增加元素时，首先要判断数组是否已满，否则无法添加新元素。需进行数组的扩容。
判断数组是否已满，以及扩容
//判断是否已满 public boolean isFull() { return usedSize == this.elem.length; } //扩容 public void grow() { this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length); }
扩容以数组长度的2倍进行扩容。
获取顺序表的长度
public int size() { return usedSize; }
这里我们直接获取数组中有效元素个数即可。
在pos位置添加元素
public void add(int pos, int data) { //1、判断下标是否合法 if (!checkPosInAdd(pos)) { throw new IndexOutOfBoundsException("传入的下标非法，pos=" + pos); } //整体往后移一位 //判断是否需要扩容 if (isFull()) { grow(); } for (int i = usedSize; i > pos; i--) { this.elem[i] = this.elem[i - 1]; } this.elem[pos] = data; usedSize++; }
首先我们需要判断添加的元素是否合法(pos不能为负,pos不能大于数组的长度)，然后判断数组是否需要扩容，其次将最后一个元素依次往后移动一个位置，直到指针到达pos位置，最后进行赋值，usedSize++
这里通过画图能更好的理解
开始向后移动
如果是在useSize位置添加直接elem[pos]=val。
判定是否包含某个元素以及获取某个元素的位置
// 判定是否包含某个元素 public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { if (this.elem[i] == toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if (this.elem[i] == toFind) { return i; } } return -1; }
这里很好理解，通过遍历数组找到相应的位置或者元素。
获取pos位置的元素以及更新pos位置的元素
// 获取 pos 位置的元素 public int get(int pos) { if (!checkPosInAdd(pos)) { throw new IndexOutOfBoundsException("传入的下标非法，pos=" + pos); } return this.elem[pos]; } // 给 pos 位置的元素设为 value public void set(int pos, int value) { if (!checkPosInAdd(pos)) { throw new IndexOutOfBoundsException("传入的下标非法，pos=" + pos); } this.elem[pos] = value; }
思路很简单，先判断pos的合法性，然后进行相应的操作
删除第一次出现的关键字key
public void remove(int key) { //查找元素的位置 int index = indexOf(key); //没找到 if (index == -1) { return; } //找到了，后面元素向前移 for (int i = index; i < usedSize; i++) { this.elem[i] = this.elem[i + 1]; } usedSize--; }
这里首先我们需要找到key的所在位置(没找到返回-1)，如果所在位置index==useSize,直接删除即可，否则从index位置开始每个元素依次向前移动一个位置。
清空顺序表
public void clear() { //如果数据类型为引用类型，将每个元素置为null /*for (int i = 0; i < usedSize; i++) { this.elem[i]=null; }*/ usedSize = 0; }
如果数据类型为引用类型，将每个元素置为null
所有完整代码
public class MyArraylist { public int[] elem; public int usedSize;//0 //默认容量 private static final int DEFAULT_SIZE = 10; public MyArraylist() { this.elem = new int[DEFAULT_SIZE]; } /** * 打印顺序表: * 根据usedSize判断即可 */ public void display() { //1、数组为空打印[]; if (usedSize == 0) { System.out.println("[]"); return; } //数组不为空[1,2,3,4] StringBuilder sb = new StringBuilder(); sb.append("["); for (int i = 0; i < usedSize; i++) { sb.append(this.elem[i]); if (i < usedSize - 1) { sb.append(","); } } sb.append("]"); System.out.println(sb.toString()); } //扩容 public void grow() { this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length); } // 新增元素,默认在数组最后新增 public void add(int data) { //1、先判断数组是否需要扩容 if (isFull()) { grow(); } //2、增加元素 this.elem[usedSize] = data; usedSize++; } /** * 判断当前的顺序表是不是满的！ * * @return true:满 false代表空 */ public boolean isFull() { return usedSize == this.elem.length; } //检查数据合法性 private boolean checkPosInAdd(int pos) { //throw new IndexOutOfBoundsException("传入的下标非法，pos="+pos); return pos >= 0 && pos < usedSize;//合法 } // 在 pos 位置新增元素 public void add(int pos, int data) { //1、判断下标是否合法 if (!checkPosInAdd(pos)) { throw new IndexOutOfBoundsException("传入的下标非法，pos=" + pos); } //整体往后移一位 //判断是否需要扩容 if (isFull()) { grow(); } for (int i = usedSize; i > pos; i--) { this.elem[i] = this.elem[i - 1]; } this.elem[pos] = data; usedSize++; } // 判定是否包含某个元素 public boolean contains(int toFind) { for (int i = 0; i < usedSize; i++) { if (this.elem[i] == toFind) { return true; } } return false; } // 查找某个元素对应的位置 public int indexOf(int toFind) { for (int i = 0; i < usedSize; i++) { if (this.elem[i] == toFind) { return i; } } return -1; } // 获取 pos 位置的元素 public int get(int pos) { if (!checkPosInAdd(pos)) { throw new IndexOutOfBoundsException("传入的下标非法，pos=" + pos); } return this.elem[pos]; } private boolean isEmpty() { return this.usedSize == 0; } // 给 pos 位置的元素设为【更新为】 value public void set(int pos, int value) { if (!checkPosInAdd(pos)) { throw new IndexOutOfBoundsException("传入的下标非法，pos=" + pos); } this.elem[pos] = value; } /** * 删除第一次出现的关键字key * * @param key */ public void remove(int key) { //查找元素的位置 int index = indexOf(key); //没找到 if (index == -1) { return; } //找到了，后面元素向前移 for (int i = index; i < usedSize; i++) { this.elem[i] = this.elem[i + 1]; } usedSize--; } // 获取顺序表长度 public int size() { return usedSize; } // 清空顺序表 public void clear() { //如果数据类型为引用类型，将每个元素置为null /*for (int i = 0; i < usedSize; i++) { this.elem[i]=null; }*/ usedSize = 0; } }
3.缺陷
- 时间上：当我们进行数据增加和删除时，需要移动位置，大大增加了时间复杂度
- 空间上：当我们进行数组扩容时，每次都以数组长度的2倍进行扩容，当数组长度特别大时，2倍扩容会消耗大量的空间
那这种缺陷可以消除吗?答案是可以的，利用链表可以有效的消除上述的缺陷。至于链表，期待我的下篇文章吧。如果有什么问题以及建议，欢迎大家评论和私信，谢谢支持！！！
