首页 / JAVA / Java实现基于数组实现的线性表
Java实现基于数组实现的线性表
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Java实现基于数组实现的线性表,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3075字,纯文字阅读大概需要5分钟。
内容图文
![Java实现基于数组实现的线性表](/upload/InfoBanner/zyjiaocheng/791/5792b000f5a849559b38a88744b4c629.jpg)
线性表
数组
记录一下用数组实现的线性结构,并实现增删改查。
为了能让自己实现的基于数组的线性结构具有普遍性,我们使用的是泛型程序设计
public class MyString<E> {
private E[] arry;
private int size;
E[] arry是一个泛型数组,现在还没有初始化,此时相当于c++中的没有指向任何内存的空指针.和数组是一样的,如果只是定义了数组,没有对数组进行初始化,那么我们在使用数组时机会出现空指针异常。我们在构造方法中进行初始化。
/**
* 构建一个指定容量大小的数组
* @param capacity 指定的容量大小
*/
public MyString(int capacity) {
arry = (E[]) new Object[capacity];
size = 0;
}
在进行初始化时使用
arry = (E[]) new Object[capacity];
而不是
arry = new E[capacity];
应为java不支持直接对泛型数组初始化为泛型数组,所有我们先初始化为Object类型,在进行强制类型转化为E类型
接下俩就是CURD
添加操作
/**
* 在index位置插入一个新的元素e
* @param e 添加的元素
* @param index 插入的位置
* @throws IllegalAccessException 对应位置不在检索范围异常
*/
public void add(E e, int index) throws IllegalAccessException {
if (index < 0 || index > size) {
throw new IllegalAccessException("Add failed. Require index >= 0 and index <= size.");
}
if (index == arry.length) {
resize(2 * arry.length);
}
for (int i=size-1;i>=index;i--) {
arry[i + 1] = arry[i];
}
arry[index] = e;
size++;
}
在添加之前先判断数组长度是否大于等于添加的位置,如果大于数组长度则需要对数组进行扩容
if (index == arry.length) {
resize(2 * arry.length);
}
扩容代码,扩容长度为原始长度的2倍
private void resize(int newCapacity) {
arry = Arrays.copyOf(arry, newCapacity);
}
判断完数组长度后在进行元素的添加操作,元素添加位置原来的元素和之后的元素都要向后移动一个位置
for (int i=size-1;i>=index;i--) {
arry[i + 1] = arry[i];
}
删除操作
删除操作和添加操作差不多,这里类比直接给代码
/**
* 删除数组中index处的元素
* @param index 需要删除位置的元素
* @return 返回删除的元素
* @throws IllegalAccessException 对应位置不在检索范围异常
*/
public E remove(int index) throws IllegalAccessException {
if (index < 0 || index > size) {
throw new IllegalAccessException("Add failed. Require index >= 0 and index <= size.");
}
E ret = arry[index];
for (int i = index + 1; i < size; i++) {
arry[i - 1] = arry[i];
}
size--;
if (size == arry.length / 4 && 0 != arry.length / 2) {
resize(arry.length / 2);
}
return ret;
}
查询和修改操作
/**
* 把指定位置的元素修改为新的元素
* @param e 新的元素
* @param index 修改的位置
* @return 被修改的元素
* @throws IllegalAccessException
*/
public E set(E e,int index) throws IllegalAccessException {
if (index < 0 || index > size) {
throw new IllegalAccessException("Add failed. Require index >= 0 and index <= size.");
}
arry[index] = e;
return arry[index];
}
/**
* 判断数组中是否纯在元素e,如果纯在返回true否则返回false
* @param e 查找的目标元素
* @return
*/
public boolean contains(E e){
for (int i=0;i<size;i++){
if (arry[i].equals(e)){
return true;
}
}
return false;
}
/**
* 在数组中返回检索目元素,如果纯在返回元素索引,否则返回-1
* @param e 检索的目标元素
* @return
*/
public int fount(E e){
for (int i=0;i<size;i++){
if (arry[i].equals(e)){
return i;
}
}
return -1;
}
基于数组实现的线性结构在查询和修改的时间复杂化度都在O(1)级别的,这里实现的线性结构对应java的ArrayList,所以如果对数组的查询和修改的操作比较多的话,使用ArrayList
内容总结
以上是互联网集市为您收集整理的Java实现基于数组实现的线性表全部内容,希望文章能够帮你解决Java实现基于数组实现的线性表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。