沧州网站优化公司,网站国外推广,什么网站做企业邮箱服务,搜索引擎排名优化是什么意思目录 1. 顺序表的相关概念1.1 线性表1.2 顺序表2. 功能实现2.1 整体框架2.2 乱七八糟的功能(bushi)2.2.1 判断容量是否满2.2.2 返回顺序表当前长度2.2.3 扩容2.2.4 清空整个顺序表 2.3 插入数据2.3.1 头插数据2.3.2 尾插数据2.3.3 指定位置插入 2.4 删除数据2.4.1 删除第一次出… 目录 1. 顺序表的相关概念1.1 线性表1.2 顺序表2. 功能实现2.1 整体框架2.2 乱七八糟的功能(bushi)2.2.1 判断容量是否满2.2.2 返回顺序表当前长度2.2.3 扩容2.2.4 清空整个顺序表 2.3 插入数据2.3.1 头插数据2.3.2 尾插数据2.3.3 指定位置插入 2.4 删除数据2.4.1 删除第一次出现的key2.4.2 删除所有的的key 2.5 查找数据2.5.1 判定是否包含某个元素2.5.2 查找某个元素对应的位置2.5.3 pos位置不合法异常2.5.4 获取pos位置的元素 2.6 修改数据 3. 全部代码 1. 顺序表的相关概念
1.1 线性表
线性表是一种常见的数据结构它的特点是逻辑上是连续的线性结构物理上不一定连续常见的线性表有顺序表、链表、栈、队列……
1.2 顺序表
顺序表是线性表的一种顺序表一般使用一段连续的地址来存储数据比如数组。在数组中进行增删查改等操作。
2. 功能实现
顺序表分为静态顺序表(容量有限)和动态顺序表(可扩容)今天我们实现的是动态顺序表并且能存储任意类型的数据所以使用到了泛型的知识点如果不了解泛型的小伙伴可以参考博主之前出的预备知识 泛型初识
2.1 整体框架
一个顺序表中需要有:数组(用于存放有效数据)、容量、当前数据个数所以我们定义一个类成员变量分别是存放数据的数组array、记录当前数据个数的curSize、当前顺序表的容量Capacity默认是10可以按需修改。在构造方法中初始化数组的内容这样当我们实例化一个顺序表对象后就能初始化顺序表了。
public class SeqListT {public Object[] array;//存放数据的数组public int curSize;//当前数据个数private int Capacity 10;//容量public SeqList() {this.array new Object[this.Capacity];}
}2.2 乱七八糟的功能(bushi)
2.2.1 判断容量是否满
逻辑很简单只要判断当前数据个数的curSize是否与顺序表的容量Capacity相等即可如果满了返回true没满返回false public boolean isFull() {return this.curSize this.Capacity;}2.2.2 返回顺序表当前长度
顺序表当前长度指的是当前数据的个数直接将curSize返回即可 //返回当前长度public int size() {return curSize;}2.2.3 扩容
Arrays.copyOf方法能够实现数组的扩容并且将原有的数据拷贝。这里我们将容量扩大两倍扩容之后别忘了将数组的容量Capacity也变为两倍 //扩容private void dilatation() {this.array Arrays.copyOf(this.array, 2 * this.Capacity);this.Capacity * 2;}2.2.4 清空整个顺序表
循环遍历顺序表将每个元素依次置为null然后将curSize和Capacity置为0 //清空public void clear() {for (int i 0; i curSize; i) {array[i] null;}this.curSize 0;this.Capacity 0;}2.3 插入数据
插入数据的方式有头插、尾插、在指定位置插入。一般情况下插入数据是尾插所以我们把尾插和在指定位置插入这两个方法重载头插方法另外实现一个。
2.3.1 头插数据 注意几个细节 1.插入前判断容量够不够如果不够需要扩容 2.如果顺序表中没有元素直接添加将数据赋值给0下标位置的元素 3.添加之后将当前数据个数curSize加1 如果顺序表中有数据且容量足够插入前需将数据整体往后挪动给第一个空出位置如图假设顺序表中有12、23、34、45这四个数据头插法插入数据99 //头插public void addFront(T data) {//如果满了,扩容if (isFull()) {dilatation();}//如果没有元素,直接添加if (this.curSize 0) {this.array[0] data;this.curSize;return;}//开始添加int cur curSize;while (cur 0) {array[cur] array[cur - 1];cur--;}array[0] data;this.curSize;}
2.3.2 尾插数据
插入数据前先判断容量够不够如果不够扩容。插入时直接将curSize下标赋值为插入的数据即可 //尾插public void add(T data) {if (isFull()) {//如果满了,扩容dilatation();}this.array[curSize] data;this.curSize;}2.3.3 指定位置插入
指定位置插入指的是pos位置插入数据 注意几个细节 1.需要判断pos位置的合法性pos不能小于0pos不能大于curSize因为顺序表中的数据是连续的 2.需要判断容量是否足够如果不够需要扩容 //在pos位置添加数据public void add(int pos, T data) throws PosNotLegalException {//判断pos位置合不合法try {if (pos 0 || pos this.curSize) {throw new PosNotLegalException(pos位置不合法);}} catch (PosNotLegalException e) {e.printStackTrace();}//如果满了,扩容if (isFull()) {dilatation();}//开始添加int cur curSize;while (cur pos) {array[cur] array[cur - 1];cur--;}array[pos] data;this.curSize;}2.4 删除数据
删除顺序表中的某个值key分为两种第一种是只删除第一次出现的key第二种是删除所有的key
2.4.1 删除第一次出现的key
如果遇到了key将key后面的元素整体往前挪动即可让后一个位置的值覆盖前一个位置的值 //移除第一次出现的keypublic void remove(T key) {int cur -1;for (int i 0; i curSize; i) {if (key.equals(array[i])) {cur i;//记录该位置}}if (cur -1) {System.out.println(找不到该元素);} else {//挪数据while (cur curSize - 1) {array[cur] array[cur 1];cur;}this.curSize--;}}2.4.2 删除所有的的key
利用双指针算法移除所有的key,例如在原数组012 2 3 0 4 2中移除所有的2。定义一个fast变量和slow变量如果fast下标的值不等于要删除的值则将fast下标的值赋值给fast下标如果fast下标的值等于要删除的值说明这个值不是我们需要的这时让fast一个人往前走即可 核心代码
if(arr[fast]!key) {arr[slow]arr[fast];fast;slow;
} else {fast;
}//移除所有的keypublic void removeAll(T key) {//将所有的key都删除int fast 0;int slow 0;while (fast this.curSize) {if (this.array[fast] ! key) {array[slow] array[fast];fast;slow;} else {fast;}}this.curSize slow;}2.5 查找数据
2.5.1 判定是否包含某个元素
循环遍历顺序表所有元素如果找到了该元素返回true没找到返回false。需要注意的是我们实现的是泛型类顺序表传递的是引用类型引用类型比较不能使用而是使用equals方法 // 判定是否包含某个元素public boolean contains(T toFind) {for (int i 0; i curSize; i) {if (toFind.equals(array[i])) {return true;}}return false;}2.5.2 查找某个元素对应的位置
循环遍历顺序表所有元素找到了这个元素就返回下标没找到则返回-1该方法只返回第一次出现该元素的位置 // 查找某个元素第一次出现位置public int indexOf(T toFind) {int index -1;for (int i 0; i curSize; i) {if (toFind.equals(array[i])) {index i;}}return index;}2.5.3 pos位置不合法异常
获取元素前需要判断传的参数pos的合法性pos不能小于0pos也不能大于等于当前顺序表个数curSize如果pos合法返回pos位置的元素即可。 判断pos位置是否合法可以通过自定义异常来实现如果pos不合法抛出自定义的异常通过try-catch捕获 定义一个pos位置不合法异常
public class PosNotLegalException extends RuntimeException {public PosNotLegalException(String s) {super(s);}public PosNotLegalException() {super();}
}2.5.4 获取pos位置的元素
判断pos的合法性如果不合法抛出异常如果合法返回该下标元素即可 //获取pos位置的元素public T get(int pos) {try {if (pos 0 || pos curSize) {throw new PosNotLegalException(pos位置不合法);}} catch (PosNotLegalException e) {e.printStackTrace();}return (T) array[pos];}2.6 修改数据
修改数据将pos下标位置修改为指定的值同样需要判断pos的合法性如果合法直接将pos下标的值修改即可 //将pos位置设置为valuepublic void set(int pos, T value) {if (pos 0 || pos curSize) {throw new PosNotLegalException(pos位置不合法);}array[pos] value;}3. 全部代码
自定义的异常类(pos位置不合法异常)
public class PosNotLegalException extends RuntimeException {public PosNotLegalException(String s) {super(s);}public PosNotLegalException() {super();}
}SeqList.java文件
public class SeqListT {public Object[] array;//存放数据的数组public int curSize;//当前数据个数private int Capacity 10;//容量//初始化public SeqList() {this.array new Object[this.Capacity];}//扩容private void dilatation() {this.array Arrays.copyOf(this.array, 2 * this.Capacity);this.Capacity * 2;}//尾插public void add(T data) {if (isFull()) {//如果满了,扩容dilatation();}this.array[curSize] data;this.curSize;}//在pos位置添加数据public void add(int pos, T data) throws PosNotLegalException {//判断pos位置合不合法try {if (pos 0 || pos this.curSize) {throw new PosNotLegalException(pos位置不合法);}} catch (PosNotLegalException e) {e.printStackTrace();}//如果满了,扩容if (isFull()) {dilatation();}//开始添加int cur curSize;while (cur pos) {array[cur] array[cur - 1];cur--;}array[pos] data;this.curSize;}//头插public void addFront(T data) {//如果满了,扩容if (isFull()) {dilatation();}//如果没有元素,直接添加if (this.curSize 0) {this.array[0] data;this.curSize;return;}//开始添加int cur curSize;while (cur 0) {array[cur] array[cur - 1];cur--;}array[0] data;this.curSize;}//判断容量是否满public boolean isFull() {return this.curSize this.Capacity;}// 判定是否包含某个元素public boolean contains(T toFind) {for (int i 0; i curSize; i) {if (toFind.equals(array[i])) {return true;}}return false;}// 查找某个元素对应的位置public int indexOf(T toFind) {int index -1;for (int i 0; i curSize; i) {if (toFind.equals(array[i])) {index i;}}return index;}//获取pos位置的元素public T get(int pos) {try {if (pos 0 || pos curSize) {throw new PosNotLegalException(pos位置不合法);}} catch (PosNotLegalException e) {e.printStackTrace();}return (T) array[pos];}//判断是否为空public boolean isEmpty() {return curSize 0;}//将pos位置设置为valuepublic void set(int pos, T value) {if (pos 0 || pos curSize) {throw new PosNotLegalException(pos位置不合法);}array[pos] value;}//移除第一次出现的keypublic void remove(T key) {int cur -1;for (int i 0; i curSize; i) {if (key.equals(array[i])) {cur i;//记录该位置}}if (cur -1) {System.out.println(找不到该元素);} else {//挪数据while (cur curSize - 1) {array[cur] array[cur 1];cur;}this.curSize--;}}//移除所有的keypublic void removeAll(T key) {//将所有的key都删除int fast 0;int slow 0;while (fast this.curSize) {if (this.array[fast] ! key) {array[slow] array[fast];fast;slow;} else {fast;}}this.curSize slow;}//返回当前长度public int size() {return curSize;}//清空public void clear() {for (int i 0; i curSize; i) {array[i] null;}this.curSize 0;this.Capacity 0;}
}今天的内容就到这里感谢老铁们的点赞、收藏、评论~❤
