前言
笔者开始学习数据结构了,虽然笔者已经会用了,不管是C++ 中的stl亦或是Java 中的集合,为了算法比赛多少都突击过,但只知其然而不知其所以然,还是会限制发展的,因此,笔者写下这篇博客.内容是手搓一个顺序表.顺带加一点异常的使用,大伙看个乐子就好了.有错误直接私信喷我就好了,不用和我客气!
前置知识-什么是数据结构
说的简短一些,数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
前置知识-什么是顺序表?
答:说白了就是一个动态数组
官方概念如下:
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表如何实现?
如图
一个接口,一个类负责实现方法,一个Main类来调用,一个我们自定义的异常来处理各种问题!!!
顺序表的接口
package LIST;
public interface list
{
// 新增元素,默认在数组最后新增
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();
public boolean isfull();
// 负责检查顺序表是否满了
public boolean isEmpty();
//负责检查顺序表是否是空的
}
每个结构具体需要实现什么功能,笔者已经写在注释里了,作为一个"动态数组",也就是"CURD"而已.
没什么难的,但是不借助外力的手搓还是有点难的.
自定义异常
比起使用现有的异常,我们还是自己定义一个方便一些
package LIST;
public class POSIllegal extends RuntimeException
{
public POSIllegal(String message)
{
super(message);
}
}
顺序表的功能实现
前置功能
@Override
public boolean isfull()
// 检测顺序表是否以及满了
{
if(usedsize==myarray.length)
return true;
else
return false;
}
@Override
public boolean isEmpty()
{
return this.usedsize==0?true:false;
}
设置这两个功能说实话有的没必要,但是一定要考虑到严谨,这必须加上来,以防止越界,也可以引出如果使用自定义异常!
通过这两个重写方法,也可以衍生出一个被封装的方法
private void checkcap()
{
if(isfull())
// 检测一下
{
myarray = Arrays.copyOf(myarray,myarray.length*2);
// 扩容(两倍)
}
}为什么我们这里用private?因为你作为使用者,你压根用不着.这也是一种没什么必要的严谨性吧.早点养成习惯也不是什么坏事.
部分核心功能
接下来来到我们的核心功能了,我们一个个来看
增加
@Override
public void add(int data)
{
checkcap();
this.myarray[this.usedsize] =data;
this.usedsize++;
}在指定位置增加
private void checkPos (int pos) throws POSIllegal
{
if(pos<0||pos>this.usedsize)
{
throw new POSIllegal("pos不合法,你的pos是 :"+pos);
}
}
@Override
public void add(int pos, int data)
{
checkcap();
try {
checkPos(pos);
}
catch (POSIllegal e)
{
e.printStackTrace();
System.out.println("下标不符合规定");
return ;
}
for(int i=this.usedsize-1;i>=pos;i--)
{
this.myarray[i+1]=this.myarray[i];
}
this.myarray[pos]=data;
this.usedsize++;
}我们首先,看看,需不需要扩容,不需要,好的,再看看有没有异常,有的话,抛出异常,让catch接收,然后return,没有异常,那就更好了,直接就可以扩容了,注意下标的边界就好了,没有难度.
得到指定位置的数据
@Override
public int get(int pos)
{
try {
return this.myarray[pos];
} catch (ArrayIndexOutOfBoundsException e)
{
e.printStackTrace();
System.out.println("越界了,数组只有"+myarray.length+"这么大");
System.out.println("请你看看自己是不是选择了负数或者大于数组大小的数");
return pos;
}
}这里我们用了官方的异常,有个对比参考.
在指定位置替换元素
private void checkPosSet (int pos) throws POSIllegal
{
if(pos<0||pos>=this.usedsize)
{
throw new POSIllegal("pos不合法,你的pos是 :"+pos);
}
}
@Override
public void set(int pos, int value)
{
try {
checkPosSet(pos);
}
catch (POSIllegal e)
{
e.printStackTrace();
return ;
}
this.myarray[pos]=value;
}注意注意,这里和增加不同了,增加是可以在顺序表增加的,但是替换是不能在结尾替换的,因为你没有元素,你怎么替换?你告诉我.
获取指定位置元素
@Override
public int indexOf(int toFind)
{
if(isEmpty())
{
return -1;
}
else
{
for(int i=0;i<this.usedsize;i++)
{
if(this.myarray[i]==toFind)
return i;
}
}
return -1;
}这里我就没用try catch 写法了
移除第一次出现的某元素
@Override
public void remove(int toRemove)
{
int idx=indexOf(toRemove);
if(idx==-1)
{
System.out.println("没有这个数字哦");
}
else
{
for(int i=idx;i<usedsize-1;i++)
{
this.myarray[i]=this.myarray[i+1];
}
usedsize--;
}
}其他功能
还有两个其他功能
清空,还有获得usedsize
@Override
public int size()
{
return this.usedsize;
}
@Override
public void clear()
{
if(isEmpty())
{
System.out.println("没法清理,顺序表是空的");
return ;
}
for(int i=0;i<this.usedsize;i++)
{
this.myarray[i]=0;
}
display();
System.out.println("清空完成");
}主函数
package LIST;
public class Main
{
public static void main(String[] args) {
Mylist mylist=new Mylist();
mylist.add(0,2);
mylist.add(1,2);
mylist.add(2,2);
mylist.add(3,2);
mylist.add(1,23);
mylist.add(3,2);
mylist.add(3,2);
mylist.add(3,2);
mylist.display();
mylist.set(5,2324);
mylist.set(7,232);
mylist.add(543,242);
System.out.println(mylist.size());
mylist.display();
mylist. clear();
}
}可以进行各种调用
也会显示异常出来
效果如图!!!!!!!
完整代码
完整代码如下
package LIST;
public interface list
{
// 新增元素,默认在数组最后新增
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();
public boolean isfull();
// 负责检查顺序表是否满了
public boolean isEmpty();
//负责检查顺序表是否是空的
}
package LIST;
import java.util.Arrays;
public class Mylist implements list
{
int [] myarray;
public static final int number= 5;
int usedsize=0;
public Mylist()
{
this.myarray = new int[number];
}
private void checkcap()
{
if(isfull())
// 检测一下
{
myarray = Arrays.copyOf(myarray,myarray.length*2);
// 扩容(两倍)
}
}
@Override
public boolean isfull()
// 检测顺序表是否以及满了
{
if(usedsize==myarray.length)
return true;
else
return false;
}
@Override
public boolean isEmpty()
{
return this.usedsize==0?true:false;
}
private void checkPos (int pos) throws POSIllegal
{
if(pos<0||pos>this.usedsize)
{
throw new POSIllegal("pos不合法,你的pos是 :"+pos);
}
}
private void checkPosSet (int pos) throws POSIllegal
{
if(pos<0||pos>=this.usedsize)
{
throw new POSIllegal("pos不合法,你的pos是 :"+pos);
}
}
@Override
public void display()
{
// 打印顺序表
for(int i=0;i<this.usedsize;i++)
{
System.out.print(myarray[i]);
System.out.print(" ");
}
System.out.println();
}
@Override
public void add(int data)
{
checkcap();
this.myarray[this.usedsize] =data;
this.usedsize++;
}
@Override
public void add(int pos, int data)
{
checkcap();
try {
checkPos(pos);
}
catch (POSIllegal e)
{
e.printStackTrace();
return ;
}
for(int i=this.usedsize-1;i>=pos;i--)
{
this.myarray[i+1]=this.myarray[i];
}
this.myarray[pos]=data;
this.usedsize++;
}
@Override
public boolean contains(int toFind)
{
if(isEmpty())
{
System.out.println("找不到,因为顺序表是空的");
return false;
}
for(int i=0;i<usedsize;i++)
{
if(this.myarray[i]==toFind)
{
System.out.println("找到了,它的下标是 :"+i);
return true;
}
}
System.out.println("顺序表里没有这么元素");
return false;
}
@Override
public int indexOf(int toFind)
{
if(isEmpty())
{
return -1;
}
else
{
for(int i=0;i<this.usedsize;i++)
{
if(this.myarray[i]==toFind)
return i;
}
}
return -1;
}
@Override
public int get(int pos)
{
try {
return this.myarray[pos];
} catch (ArrayIndexOutOfBoundsException e)
{
e.printStackTrace();
System.out.println("越界了,数组只有"+myarray.length+"这么大");
System.out.println("请你看看自己是不是选择了负数或者大于数组大小的数");
return pos;
}
}
@Override
public void set(int pos, int value)
{
try {
checkPosSet(pos);
}
catch (POSIllegal e)
{
e.printStackTrace();
return ;
}
this.myarray[pos]=value;
}
@Override
public void remove(int toRemove)
{
int idx=indexOf(toRemove);
if(idx==-1)
{
System.out.println("没有这个数字哦");
}
else
{
for(int i=idx;i<usedsize-1;i++)
{
this.myarray[i]=this.myarray[i+1];
}
usedsize--;
}
}
@Override
public int size()
{
return this.usedsize;
}
@Override
public void clear()
{
if(isEmpty())
{
System.out.println("没法清理,顺序表是空的");
return ;
}
for(int i=0;i<this.usedsize;i++)
{
this.myarray[i]=0;
}
display();
System.out.println("清空完成");
}
}
package LIST;
public class POSIllegal extends RuntimeException
{
public POSIllegal(String message)
{
super(message);
}
}
结尾
可以看到,对于核心功能,我写的很草率,压根没有写完整,只是随便写了几个增删查改的功能,如果要细化还是能出很多的,交给能看到这里的读者了.
我写学过用C语言手搓顺序表,只能说,Java还是更简单一点.
需要我的完整代码,可以访问我的GitHub,链接点进去,这部分代码在JavaDS List当中
需要就点个星呗,我的GitHub有的乱,后续我会整理的.
calljsh/Call-JJ-java (github.com)