图文+实战,轻松学会数据结构【数组】

作者:周棋洛,大二计算机在校生 ‍

内容:数据结构概念,Java模拟一个数组

目标:一篇一种数据结构,今天学习数组


图文+实战,轻松学会数据结构【数组】_第1张图片

目录

前言

思维导图

什么是数据结构?

初识数组数据结构

实战Java模拟数组

数组初始化

length方法,返回数组长度

isLegal方法,判断下标是否正常

add方法,添加数据

remove方法,移除数据

update方法,更新数组元素

search方法,查找数组元素

isEmpty方法,检测数组是否为空

toString方法,打印遍历后的数组

 测试

总结


前言

小伙伴们,你们好,这是一篇数据结构的文章,今天从简单的数组下手,数据结构很重要,大一学习数组结构,真的觉得很难,但是不能因为难就此止步,当你坚持一点一点攻克它,再回首,数据结构也不过如此啊!,加油,成长的路上不会如履平地,绊脚石就是成功的见证,跟博主一起努力,拿下数据结构吧!

思维导图

以后的文章也会从数据结构的优势,劣势,模拟数据结构和总结四个方面来学习,理论加实战,轻松拿下数据结构

图文+实战,轻松学会数据结构【数组】_第2张图片

 

什么是数据结构?

维基百科:在计算机科学中,数据结构(data structure)是计算机中存储、组织数据的方式

早些时候人们记录电话号码会使用电话簿,假如一行记录一个人的电话号,当电话越来越多时,找起来就很费劲了

如果想找的更快,这个时候可以对联系人进行分类,比如分成家人,朋友,同事等三类,然后给每一个分类预留一页,当查找时直接定位到相应的分类,速度就快了很多,但是问题也来了,预留空间到底多少合适?少了不够,多了浪费!

数据结构概念就和电话簿存储电话类似,存储数据时,根据实际情况,选用合适的数据结构,可以提高内存利用率

图文+实战,轻松学会数据结构【数组】_第3张图片

初识数组数据结构

数组可以说是最基本最常见的数据结构,数组一般用来存储相同类型的数据,可通过数组名和下标进行数据的访问和更新,由于数据是存储在连续空间内的,所以每个数据的内存地址(在内存上的位置)都可以通过数组下标算出,我们也就可以借此直接访问目标数据(这叫作“随机访问”),因此数组的访问速度非常可观,而添加和删除数据比较耗工夫

 

假设数组中有 n 个数据,由于访问数据时使用的是随机访问(通过下标可计算出内存地址),所以时间复杂度为恒定的O(1)
但另一方面,想要向数组中添加或删除数据时,必须把目标位置后面的数据一个个移动,如果在数组头部添加数据,就要移动n次,时间复杂度为O(n),删除操作也是同理

实战Java模拟数组

使用Java语言来模拟数组的实现过程,目标是实现一个无限扩容,并且完成增删改查,返回数组长度,判断数组是否为空等方法,这里注意,如果自己想没有思路,可以将这个过程通过纸和笔来画出来,帮助理解,真的很实用

图文+实战,轻松学会数据结构【数组】_第4张图片

 

,目标明确,那就开始写代码了,首先创建一个类表示自己编写的数组类,取名为 MyArray

数组初始化

首先定义一个属性,int类型数组,elements,并使用无参构造进行数组初始化,默认是没有元素的

/**
 * 用于存储数据的数组
 */
private int[] elements;

/**
 * 初始化
 */
public MyArray() {
    elements = new int[0];
}

length方法,返回数组长度

获取数组长度的方法,返回数组长度

/**
 * 获取数据长度的方法
 * @return 返回数组长度
 */
public int length() {
    return this.elements.length;
}

isLegal方法,判断下标是否正常

判断数组下标是否符合要求,即 小于0 或者 大于数组长度-1 都是不合法的,因为数组的下标是从0开始计算的,true表示输入的下标合法,false表示不合法,并提示

/**
 * 判断数组下标是否符合要求,即 小于0 或者 大于数组长度-1 都是不合法的
 * 因为数组的下标是从0开始计算的
 * @param index 数组下标
 * @return 布尔,true表示输入的下标合法,false表示不合法,并提示
 */
public boolean isLegal(int index) {
    if (index < 0 || index > elements.length - 1) {
        System.out.println("数组下标不合法,操作不成功");
        return false;
    }
    return true;
}

add方法,添加数据

这里难的就是理解数组这种数据结构是不可变长的,一旦确定大小,就没办法修改了,那如果数组装满了,怎么办,数组扩容,说是扩容,本质是创建一个更大的新的数组,把原数组循环赋值给新数组,最后重点,把新数组的引用赋值给原数组这就完成了数组的扩容

 图文+实战,轻松学会数据结构【数组】_第5张图片

/**
 * 完成数组的增
 * @param element 需要加入数组的元素
 */
public void add(int element) {
    // 数组扩容,当添加时就在已有基础上加1
    int newLength = this.elements.length + 1;
    // 创建一个新的大小的数组
    int[] newArr = new int[newLength];
    // 循环将原数组的值赋给新长度的数组
    for (int i = 0; i < elements.length; i++) {
        newArr[i] = elements[i];
    }
    // 把添加元素放在数组中
    newArr[newLength - 1] = element;
    // 把新数组的引用赋值给真的数组,newArr此时就没人引用了,就会被JVM机进行销毁
    elements = newArr;
}

remove方法,移除数据

在进行删除操作时,首先要判断要删除的下标是否合理,如果合理再进行后续操作,否则直接返回,当下标合理,重点来了,这里遍历数组元素,通过判断当前元素是否小于要删除元素的下标,如果时就直接赋值,如果等于,直接 continue 跳过,就相当于删了,否则就是原数组下标值赋给新的数组下标 -1位置的元素

 

/**
* 数组删除方法
* @param index 待删除数组元素的下标值
*/
public void remove(int index) {
if (!isLegal(index)) {
    return;
}
int[] newArr = new int[elements.length - 1];
for (int i = 0; i < elements.length; i++) {
    if (i < index) {
        newArr[i] = elements[i];
    } else if (i == index) {
        continue;
    } else {
        newArr[i - 1] = elements[i];
    }
}
elements = newArr;
}

update方法,更新数组元素

更新就时指定要改下标为多少的元素,改为多少,但也要注意下标合法判断哦,很简单

/**
 * 更新数组下标元素的值
 * @param index    待更新数组元素的下标
 * @param newValue 待更新下标的值
 */
public void update(int index, int newValue) {
    if (!isLegal(index)) {
        return;
    }
    this.elements[index] = newValue;
}

search方法,查找数组元素

简单的遍历查找数组元素,有则直接返回元素的下标,没有返回-1

/**
 * 查找元素
 * @param targetVal 待查找的目标值
 * @return 数组下标,找到了直接返回,没找到返回-1
 */
public int search(int targetVal) {
    for (int i = 0; i < elements.length; i++) {
        if (elements[i] == targetVal) {
            return i;
        }
    }
    System.out.println("芜湖,没找到");
    return -1;
}

isEmpty方法,检测数组是否为空

只要数组的length不等于0,数组就不为空,就返回false,反之为空,返回true

/**
 * 判断数组是否为空
 * @return 如果为空返回true,不为空返回false
 */
public boolean isEmpty() {
    if (elements.length != 0) {
        return false;
    }
    return true;
}

toString方法,打印遍历后的数组

这里使用toString方法,借助Arrays工具类打印数组

/**
 * 重写 toString,调用Arrays工具类打印数组
 * @return
 */
@Override
public String toString() {
    return Arrays.toString(elements);
}

 

 测试

public static void main(String[] args) {
    // 实例化自己写的数组类
    MyArray myArray = new MyArray();
    // 添加数据
    myArray.add(100);
    myArray.add(-150);
    myArray.add(50);
    myArray.add(4);
    System.out.println(myArray);
    // 移除数据
    myArray.remove(3);
    System.out.println(myArray);
    // 修改数据
    myArray.update(2, 100100);
    System.out.println(myArray);
    myArray.update(10, 100);
    // 查询数组
    int i = myArray.search(100);
    System.out.println(i);
}
[100, -150, 50, 4]
[100, -150, 50]
[100, -150, 100100]
数组下标不合法,操作不成功
0

总结

  • 数组是最基本最常见的数据结构,一般用来存储相同类型的数据
  • 数组可通过数组名和下标进行数据的访问和更新
  • 数组在内存上是连续的,这种连续使得我们可以高效的进行元素“访问”
  • 优点访问快,复杂度为O(1);
  • 缺点插入和删除是时的元素移动导致速度慢,并且其“内存”大小固定。
  • 对于大小固定的数据,选用数组进行存储简直不要太棒

图文+实战,轻松学会数据结构【数组】_第6张图片

 

你可能感兴趣的