数据结构(1):使用面向对象模拟数组
数组是一种常用的数据结构,数组具有不可变性,创建后的数组的长度固定,通过索引访问数组中的元素,访问速度快,删除添加效率低。
通过面向对象模拟数组,模拟的数组具有以下功能:
- 添加新元素
- 展示
- 查找元素所在位置
- 根据索引获取元素
- 根据索引删除元素
- 修改指定位置的元素
同时使用两个算法对数组进行操作:
- 有序添加元素
- 二分查找法
1.创建数组类 MyArray.java
数据如何存储呢?在类中添加一个数组类型的私有属性用来保存数据,同时添加一个变量存储有效数据的长度(也就是元素的个数)
创建数组的时候需要指定数组的长度,所以要添加两个构造方法:
1.无参构造方法设置数组默认长度
2.有参构造方法指定数组长度
public class MyArray { //存储元素 private long[] arr; //表示有效数据的长度 private int elements; //无参构造默认50个长度 public MyArray() { arr=new long[50]; } public MyArray(int maxsize) { arr=new long[maxsize]; } }
2.编写添加数据的方法
elements 属性的默认值是 0,第一次向对象中添加元素也是添加到索引为0 的元素中,添加后将 elements 的长度加1,就能一直向数组中添加元素了,添加元素的个数取决于 arr 的长度。
public void insert(long value) { arr[elements]=value; elements++; }
3.编写展示数据的方法
简单的展示数组中的元素即可,使用 for 循环遍历
public void display() { System.out.print("["); for (int i = 0; i < elements; i++) { System.out.print(arr[i]+" "); } System.out.println("]"); }
4.编写查找数据的方法
思路:使用循环遍历数组 arr ,将要查找的数据和 arr 中每个元素进行比较。如果相等,则跳出循环。循环结束后,如果循环次数等于元素个数说明没有找到数据,返回-1。否则返回循环次数(即找到的索引)。
public int search(long value) { int i ; for (i = 0; i < elements; i++) { if(value==arr[i]) { break; } } //遍历到末尾说明没有找到 if (i==elements) { return -1; }else { return i; } }
5.根据索引获取元素
思路:这相对比较简单了,直接给 arr 索引就能获取到元素。但是要注意传入的索引必须可用,不能用的索引可以抛出异常。
public long get(int index) { //如果索引大于可用,或索引小于0 都是无效的索引 if (index>=elements||index<0) { //抛出数组越界异常 throw new ArrayIndexOutOfBoundsException(); }else { return arr[index]; } }
6.根据索引删除元素
思路:和获取元素时一样,先检查索引是否可用。如果可用,就从要删除元素的位置开始向后遍历,每次都将下一个元素的值赋值给当前元素。也就相当于要删除的元素被下一个元素覆盖,下一个元素被下下一个元素覆盖,以此类推。元素移动完成后,将可用元素长度 elements 减1。
public void delete(int index) { //如果索引大于可用,或索引小于0 都是无效的索引 if (index>=elements||index<0) { throw new ArrayIndexOutOfBoundsException(); }else { for(int i=index;i<elements;i++) { arr[index]=arr[i+1]; } elements--; } }
7.修改指定位置的元素
思路:和获取差不多,就是把获取改为修改
public void change(int index,int newValue) { //如果索引大于可用,或索引小于0 都是无效的索引 if (index>=elements||index<0) { throw new ArrayIndexOutOfBoundsException(); }else { arr[index]=newValue; } }
8.完整代码
public class MyArray { private long[] arr; //表示有效数据的长度 private int elements; public MyArray() { arr=new long[50]; } public MyArray(int maxsize) { arr=new long[maxsize]; } /** * 添加数据 * @param value */ public void insert(long value) { arr[elements]=value; elements++; } /** * 显示数据 */ public void display() { System.out.print("["); for (int i = 0; i < elements; i++) { System.out.print(arr[i]+" "); } System.out.println("]"); } /** * 查找数据 */ public int search(long value) { int i ; for (i = 0; i < elements; i++) { if(value==arr[i]) { break; } } //遍历到末尾说明没有找到 if (i==elements) { return -1; }else { return i; } } /** * 查找数据,根据索引来查 */ public long get(int index) { //如果索引大于可用,或索引小于0 都是无效的索引 if (index>=elements||index<0) { throw new ArrayIndexOutOfBoundsException(); }else { return arr[index]; } } /** * 删除数据 */ public void delete(int index) { //如果索引大于可用,或索引小于0 都是无效的索引 if (index>=elements||index<0) { throw new ArrayIndexOutOfBoundsException(); }else { for(int i=index;i<elements;i++) { arr[index]=arr[i+1]; } elements--; } } /** * 更新数据 */ public void change(int index,int newValue) { //如果索引大于可用,或索引小于0 都是无效的索引 if (index>=elements||index<0) { throw new ArrayIndexOutOfBoundsException(); }else { arr[index]=newValue; } } }
9.有序添加元素
思路:修改 insert 方法,遍历 arr 数组,如果当前元素大于添加的数据,当前的位置就要存入的位置。从最后一个元素开始,逐个将元素向后位移,空出要存入的位置。存入要添加的元素后,将有效数据长度加1。
public void insert(long value) { int i; for(i=0;i<elements;i++) { if(arr[i]>value) { break; } } for (int j = elements; j > i; j--) { arr[j]=arr[j-1]; } arr[i]=value; elements++; }
10.二分查找法
思路:数据必须是有序的,才能使用二分查找法!可以结合有序添加元素一块使用,这里的序列是升序(从小到大)。二分查找是每次和一组数中间的数进行比较,如果大于就再和右边的数最中间的数比较,如果小于就和左边的数最中间的数比较。直到中间的数和要查找的数相等,否则就是没有这个数。
public int binarySearch(long value) { int mid=0;//中间值 int low=0; int high = elements; while(true) { mid=(high+low)/2; if(arr[mid]==value) { return mid; }else if(low>high) { return -1; }else { if (value>arr[mid]) { high=mid+1; }else { high=mid-1; } } } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
SpringBoot 返回参数为null,不返回的处理
SpringBoot 整合 fastjson Springboot处理返回的参数为null、或者不返回 一、通过继承WebMvcConfigurerAdapter,重写configureMessageConverters方法实现 @Configuration public class fastJsonConfig extends WebMvcConfigurerAdapter { @Autowired private LogCostInterceptor logCostInterceptor; /** * 使用阿里 fastjson 作为JSON MessageConverter * @param converters */ @Override public void configureMessageConverters(List<HttpMessageConverter<?>> converters) { FastJsonHttpMessageConverter converter = new FastJsonHttpMessageConverter(); F...
- 下一篇
MessagePack Java 0.6.X 可选字段
你可添加一个新的字段来保持可用性。在新字段中使用@Optional注解。 @MessagepublicstaticclassMyMessage {publicString name;publicdoubleversion;// new field@Optionalpublicintflag =0;} 如果你尝试反序列化老版本数据的话,可选字段将会被忽略。 https://www.cwiki.us/display/Serialization/QuickStart+For+MessagePack+Java+0.6.X
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,7,8上安装Nginx,支持https2.0的开启
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果