目录
一、顺序表中的接口
二、顺序表中的方法实现
(1)display方法
(2)add方法
1、不指定下标位置插入
2、指定下标位置插入
(3)contains方法
(4)indexOf方法
(5)get方法
(6)set方法
(7)remove方法
(8)size方法
(9)clear方法
三、最终代码
一、顺序表中的接口
代码如下:
public interface IList {
// 新增元素,默认在数组最后新增
public void add(int data);
// 在 pos 位置新增元素
public void add(int pos, int data);
// 判定是否包含某个元素
public boolean contains(int toFind);
// 查找某个元素对应的位置
public int indexOf(int toFind);
// 获取 pos 位置的元素
public int get(int pos);
// 给 pos 位置的元素设为 value
public void set(int pos, int value);
//删除第一次出现的关键字key
public void remove(int toRemove);
// 获取顺序表长度
public int size();
// 清空顺序表
public void clear();
// 打印顺序表,注意:该方法并不是顺序表中的方法,为了方便看测试结果给出的
public void display();
}
以上的方法就是我们要模拟实现顺序表的方法了。
二、顺序表中的方法实现
创建一个类,这个类实现上面接口,重写类里所有的方法。
我们知道,顺序表其实就是数组,所以要创建一个数组来存放数据,还要用一个整型变量来记录顺序表的大小,还有构造方法,我们可以指定顺序表的容量,也可以使用默认容量为10,代码如下
public class MyArrayList implements IList{
public int[] elem;
private int usedSize = 0;
private int DEFAULT_SIZE = 10;
public MyArrayList() {
elem = new int[DEFAULT_SIZE];
}
public MyArrayList(int size) {
elem = new int[size];
}
}
(1)display方法
这个方法是打印顺序表的方法,并不是顺序表中的方法
@Override
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
(2)add方法
1、不指定下标位置插入
插入元素前要检查顺序表满没满,满了就要扩容,再插入元素,因为没指定下标插入元素,所以插入的是顺序表的末位置,也就是usedSize位置,插入完后usedSize要自增,表示顺序表多了一个元素,代码如下:
@Override
public void add(int data) {
//检查容量
checkCapacity();
//添加元素
elem[usedSize] = data;
usedSize++;
}
private void checkCapacity() {//检查容量
if(ifFull()) {
//扩容
elem = Arrays.copyOf(elem, elem.length * 2);
}
}
private boolean ifFull() {//判断数组满了没
return usedSize == elem.length;
}
2、指定下标位置插入
指定下标位置插入元素就要判断这个下标是否合法,不合法就要抛出异常,下标是合法的就判断顺序表的容量满了没,没满就扩容,当经过上面两个检查后,才能指定位置插入元素,但插入前,还要把指定的下标,及之后的元素都往后移动一位,才能把要放的元素放进去,代码如下:
@Override
public void add(int pos, int data) throws PosIllegality{
//判断pos下标是否合法
try {
checkPosOnAdd(pos);
} catch (PosIllegality e) {
e.printStackTrace();
}
//数组满了就要扩容
checkCapacity();
for (int i = usedSize - 1; i >= pos; i--) {
elem[i + 1] = elem[i];
}
elem[pos] = data;
usedSize++;
}
private void checkPosOnAdd(int pos) throws PosIllegality{
if(pos < 0 || pos > usedSize) {
//不合法,抛异常
System.out.println("不合法");
throw new PosIllegality("数组下标不合法" + pos);
}
}
//异常
public class PosIllegality extends RuntimeException{
public PosIllegality(String msg) {
super(msg);
}
}
(3)contains方法
判定是否包含某个元素,代码如下:
@Override
public boolean contains(int toFind) {
if(usedSize == 0) return false;
for (int i = 0; i < usedSize; i++) {
if(elem[i] == toFind) {
return true;
}
}
return false;
}
(4)indexOf方法
查找某个元素对应的位置,代码如下:
@Override
public int indexOf(int toFind) {
if(usedSize == 0) return -1;
for (int i = 0; i < usedSize; i++) {
if(elem[i] == toFind) {
return i;
}
}
return -1;
}
(5)get方法
获取 pos 位置的元素,这个和add指定位置一样,要判断pos下标是否合法,不合法就要抛异常,当顺序表是空的时候,也要抛异常,当上面两个判断都没有抛异常后,就返回指定下标的元素,代码如下:
@Override
public int get(int pos) {
try {
checkPosOnGetAndSet(pos);
} catch (PosIllegality e) {
e.printStackTrace();
}
if(usedSize == 0) {
//数组为空,拿不了,抛异常
throw new MyArrayListEmpty("顺序表为空");
}
return elem[pos];
}
private void checkPosOnGetAndSet(int pos) throws PosIllegality{
if(pos < 0 || pos >= usedSize) {
//下标不合法
System.out.println("下标不合法");
throw new PosIllegality("查找的下标不合法" + pos);
}
}
//异常
public class MyArrayListEmpty extends RuntimeException{
public MyArrayListEmpty(String msg) {
super(msg);
}
}
(6)set方法
给 pos 位置的元素设为 value,要检查下标是否合法,不合法就要抛异常,合法就给 pos 位置的元素设为 value,代码如下:
@Override
public void set(int pos, int value) throws PosIllegality{
try {
//检查下标合法性
checkPosOnGetAndSet(pos);
} catch (PosIllegality e) {
e.printStackTrace();
}
elem[pos] = value;
}
(7)remove方法
删除第一次出现的关键字key,这个方法可以用上面的indexOf方法,找到key值的下标,有就返回下标数字,没有返回-1,当返回的是-1,就输出“没有这个数字”,有就删除这个下标元素,方法是后面元素往前覆盖,再把usedSize自减,表示顺序表少了一个元素,代码如下:
@Override
public void remove(int toRemove) {
int index = indexOf(toRemove);
if(index == -1) {
System.out.println("没有这个数字");
return;
}
for (int i = index; i < usedSize; i++) {
elem[i] = elem[i + 1];
}
usedSize--;
}
(8)size方法
获取顺序表长度,代码如下:
@Override
public int size() {
return usedSize;
}
(9)clear方法
清空顺序表,代码如下
@Override
public void clear() {
usedSize = 0;
}
三、最终代码
MyArrayList类:文章来源:https://www.toymoban.com/news/detail-760688.html
public class MyArrayList implements IList{
public int[] elem;
private int usedSize = 0;
private int DEFAULT_SIZE = 10;
public MyArrayList() {
elem = new int[DEFAULT_SIZE];
}
public MyArrayList(int size) {
elem = new int[size];
}
@Override
public void add(int data) {
//检查容量
checkCapacity();
//添加元素
elem[usedSize] = data;
usedSize++;
}
private void checkCapacity() {//检查容量
if(ifFull()) {
//扩容
elem = Arrays.copyOf(elem, elem.length * 2);
}
}
private boolean ifFull() {//判断数组满了没
return usedSize == elem.length;
}
@Override
public void add(int pos, int data) throws PosIllegality{
//判断pos下标是否合法
try {
checkPosOnAdd(pos);
} catch (PosIllegality e) {
e.printStackTrace();
}
//数组满了就要扩容
checkCapacity();
for (int i = usedSize - 1; i >= pos; i--) {
elem[i + 1] = elem[i];
}
elem[pos] = data;
usedSize++;
}
private void checkPosOnAdd(int pos) throws PosIllegality{
if(pos < 0 || pos > usedSize) {
//不合法,抛异常
System.out.println("不合法");
throw new PosIllegality("数组下标不合法" + pos);
}
}
@Override
public boolean contains(int toFind) {
if(usedSize == 0) return false;
for (int i = 0; i < usedSize; i++) {
if(elem[i] == toFind) {
return true;
}
}
return false;
}
@Override
public int indexOf(int toFind) {
if(usedSize == 0) return -1;
for (int i = 0; i < usedSize; i++) {
if(elem[i] == toFind) {
return i;
}
}
return -1;
}
@Override
public int get(int pos) {
try {
checkPosOnGetAndSet(pos);
} catch (PosIllegality e) {
e.printStackTrace();
}
if(usedSize == 0) {
//数组为空,拿不了,抛异常
throw new MyArrayListEmpty("顺序表为空");
}
return elem[pos];
}
private void checkPosOnGetAndSet(int pos) throws PosIllegality{
if(pos < 0 || pos >= usedSize) {
//下标不合法
System.out.println("下标不合法");
throw new PosIllegality("查找的下标不合法" + pos);
}
}
@Override
public void set(int pos, int value) throws PosIllegality{
try {
//检查下标合法性
checkPosOnGetAndSet(pos);
} catch (PosIllegality e) {
e.printStackTrace();
}
elem[pos] = value;
}
@Override
public void remove(int toRemove) {
int index = indexOf(toRemove);
if(index == -1) {
System.out.println("没有这个数字");
return;
}
for (int i = index; i < usedSize; i++) {
elem[i] = elem[i + 1];
}
usedSize--;
}
@Override
public int size() {
return usedSize;
}
@Override
public void clear() {
usedSize = 0;
}
@Override
public void display() {
for (int i = 0; i < usedSize; i++) {
System.out.print(elem[i] + " ");
}
System.out.println();
}
}
//异常类文章来源地址https://www.toymoban.com/news/detail-760688.html
public class MyArrayListEmpty extends RuntimeException{
public MyArrayListEmpty(String msg) {
super(msg);
}
}
public class PosIllegality extends RuntimeException{
public PosIllegality(String msg) {
super(msg);
}
}
到了这里,关于数据结构 模拟实现ArrayList顺序表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!