- 1.线性表
- 2.顺序表
- 2.1 概念及结构
- 2.2 常见接口
- 2.3接口具体实现
- 2.3.1打印顺序表
- 2.3.2在 pos 位置新增元素
- 2.3.3 判定是否包含某个元素
- 2.3.4 查找某个元素对应的位置
- 2.3.5获取 pos 位置的元素
- 2.3.6给 pos 位置的元素设为 value
- 2.3.7删除第一次出现的关键字key
- 2.3.8 获取顺序表的有效数据长度
- 2.3.9 清空顺序表
- 3完整代码
**线性表（linear list）**是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
2.顺序表 2.1 概念及结构顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：
- 静态顺序表：使用定长数组存储。
- 动态顺序表：使用动态开辟的数组存储。
静态顺序表适用于确定知道需要存多少数据的场景.
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用
public class MyArrayList {
// 打印顺序表
public void display() { }
// 在 pos 位置新增元素
public void add(int pos, int data) { }
// 判定是否包含某个元素
public boolean contains(int toFind) { return true; }
// 查找某个元素对应的位置
public int search(int toFind) { return -1; }
// 获取 pos 位置的元素
public int getPos(int pos) { return -1; }
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) { }
//删除第一次出现的关键字key
public void remove(int toRemove) { }
// 获取顺序表长度
public int size() { return 0; }
// 清空顺序表
public void clear() { }
}
2.3接口具体实现
首先定义顺序表elem，并用构造函数初始化顺序表，顺序表有效数据个数usedSize
public int[] elem;
public int usedSize;//0有效数据个数
public MyArrayList() {
this.elem = new int[10];
}
2.3.1打印顺序表
将顺序表中有效个数据打印出来：
//打印顺序表
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
2.3.2在 pos 位置新增元素
增加元素首先要看元素插入的位置是否合法，其次判断顺序表是否满了，满了要对顺序表进行扩容
将pos位置及后面的元素后移，然后将data插入elem[pos]位置
//在 pos 位置新增元素
public void add(int pos, int data) {
if (pos < 0 || pos > usedSize) {
System.out.println("位置不合法！");
return;
}
if (isFull()) {
Arrays.copyOf(this.elem, 2 * this.elem.length);
}
//3
for (int i = this.usedSize - 1; i >= pos; i--) {
this.elem[i + 1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
//判断是否满
public boolean isFull() {
return this.usedSize == this.elem.length;
}
2.3.3 判定是否包含某个元素
将元素与顺序表有效数据范围的元素依次进行比较，如果有返回true，否则返回false。
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == toFind) {
return true;
}
}
return false;
}
2.3.4 查找某个元素对应的位置
将元素与顺序表有效数据范围的元素依次进行比较，如果有返回下标i，否则返回-1。
// 查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;
}
2.3.5获取 pos 位置的元素
首先判断pos位置是否合法，其次判断顺序表是否为空
获取pos位置元素，返回
// 获取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >= usedSize) {
System.out.println("pos位置不合法");
return -1;//说明，业务上的处理，不考考虑
}
if (isEmpty()) {
System.out.println("顺序表为空!");
return -1;
}
return this.elem[pos];
}
//判空
public boolean isEmpty() {
return this.usedSize == 0;
}
2.3.6给 pos 位置的元素设为 value
首先判断pos位置是否合法，其次判断顺序表是否为空
pos位置元素设置为value
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= usedSize) {
System.out.println("pos位置不合法");
return;//说明，业务上的处理，不考考虑
}
if (isEmpty()) {
System.out.println("顺序表为空!");
return;
}
this.elem[pos] = value;
}
2.3.7删除第一次出现的关键字key
将下标为i的元素删除，将elem[i]值设置为elem[i+1],
//删除第一次出现的关键字key
//1.判断顺序表是否为空
//2.查找要删除的数字elem[i]==toRemove
//3.i
2.3.8 获取顺序表的有效数据长度
//获取顺序表的有效数据长度
public int size() {
return this.usedSize;
}
2.3.9 清空顺序表
// 清空顺序表
public void clear() {
this.usedSize=0;
}
3完整代码
import java.util.Arrays;
public class MyArrayList {
public int[] elem;
public int usedSize;//0有效数据个数
public MyArrayList() {
this.elem = new int[10];
}
//打印顺序表
public void display() {
for (int i = 0; i < this.usedSize; i++) {
System.out.print(this.elem[i] + " ");
}
System.out.println();
}
//获取顺序表的有效数据长度
public int size() {
return this.usedSize;
}
//在 pos 位置新增元素
public void add(int pos, int data) {
if (pos < 0 || pos > usedSize) {
System.out.println("位置不合法！");
return;
}
if (isFull()) {
Arrays.copyOf(this.elem, 2 * this.elem.length);
}
//3
for (int i = this.usedSize - 1; i >= pos; i--) {
this.elem[i + 1] = this.elem[i];
}
this.elem[pos] = data;
this.usedSize++;
}
public boolean isFull() {
return this.usedSize == this.elem.length;
}
// 判定是否包含某个元素
public boolean contains(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == toFind) {
return true;
}
}
return false;
}
// 查找某个元素对应的位置
public int search(int toFind) {
for (int i = 0; i < this.usedSize; i++) {
if (this.elem[i] == toFind) {
return i;
}
}
return -1;
}
// 获取 pos 位置的元素
public int getPos(int pos) {
if (pos < 0 || pos >= usedSize) {
System.out.println("pos位置不合法");
return -1;//说明，业务上的处理，不考考虑
}
if (isEmpty()) {
System.out.println("顺序表为空!");
return -1;
}
return this.elem[pos];
}
public boolean isEmpty() {
return this.usedSize == 0;
}
// 给 pos 位置的元素设为 value
public void setPos(int pos, int value) {
if (pos < 0 || pos >= usedSize) {
System.out.println("pos位置不合法");
return;//说明，业务上的处理，不考考虑
}
if (isEmpty()) {
System.out.println("顺序表为空!");
return;
}
this.elem[pos] = value;
}
//删除第一次出现的关键字key
//1.判断顺序表是否为空
//2.查找要删除的数字elem[i]==toRemove
//3.i
public class Test {
public static void main(String[] args) {
MyArrayList myArrayList = new MyArrayList();
myArrayList.add(0,1);
myArrayList.add(1,2);
myArrayList.add(2,3);
myArrayList.add(3,4);
myArrayList.add(4,5);
myArrayList.display();
System.out.println(myArrayList.contains(3));
System.out.println(myArrayList.search(1));
System.out.println(myArrayList.getPos(4));
myArrayList.setPos(4,78);
myArrayList.display();
myArrayList.clear();
myArrayList.display();
}
}
