Fork me on GitHub
0%

服务端校招知识点一 数据结构之数组

鸡汤

人生没有连续的一帆风顺,总是要靠自己的坚持来维护这一份延续
一段连续的快乐总是那么不容易被插入或打断

1、前言

在复习数据之前,我们先回忆一个概念,什么是线性表,线性表和数组的关系是什么?接下来让我们一起来回顾一下

2、线性表

定义:零个或多个数据元素组成的有限序列。
解释:我们注意定义中有两个点,一个是数据元素,一个是有限序列。首先线性表是一个序列,强调这个序列是有限长度n,其中n≥0, n=0的序列我们成为空表;数据元素则是一个抽象的概念,数据元素可能是数字1、2、3,可能是猴、狗等动物,也可能是本子、笔等文具。

3、数组与线性表的关系

数据是线性表的顺序存储结构,即用一段连续的存储单元一次存储线性表的数据元素。有两个概念我们要区分一下,“数组的长度”和“线性表的长度”是有区别的,一般来说,数组的长度要大于等于线性表的长度,简单可以理解为我们在一些高级语言中看到的长度(len)和容量(cap),数组是存储线性表的存储空间,已经分配的存储空间一般是不会变的。当然一些高级语言中会通过某些编程的手段使数组实现动态分配,但这是很消耗的,所以在我们日常的开发中,都会尽量避免数组的重新分配。

1
2
// 假如已知arr1数组长度,需要申请一个和arr1相同长度的数据
arr2 := make([]int64, len(arr1)) // 作为伪代码理解

4、数组的地址计算

由于数组是顺序存储的,所以数组的地址也就是连续的一段空间,我们在编程语言中的往往定义起始地址是0,这有悖于我们从小接受的从1开始数数的教育。于是线性表的第i个元素在顺序存储结构中的位置应该是i - 1,即数据元素的序列号与存储的位置如下图

5、数组的插入与删除

5.1 数据元素检索

对于顺序存储结构来说,获取某一个位置的元素是很容易的,譬如,我们要获取第i个元素,我们只需要将第i-1位置的元素去除即可,这里的时间复杂度为O(1)

5.2 数据元素插入

上面我们说到了,从数组中取一个位置的数据是很容易的,那么插入呢?我们可以想象一下,在课堂的一排座位是一个数组,那么现在新来一位同学,他要选择这一排的某个位置上,我们都要怎么做呢,首先这位新同学要选的位置是符合老师的期望的,然后要看这一排的座位是否足够容纳这位新同学,如果不够,我们就要搬来一个座位来满足需求,假如新同学选的是第i个位置,那么为了保持这一排的其他同学顺序不变,只能从最后一位同学开始到第i个同学,依次向后移动一个位置,空出来的新第i位置留给新同学。由此我们知道,将一个数据元素插入数组,我们需要做这些事:

  • 判断要插入的位置是否合理,不合理抛出异常
  • 如果插入后的数据元素个数大于数组长度,那么就需要返回异常或者动态申请新的存储空间
  • 从最后一个数据元素开始,到第i位置的元素,依次向后移动一个存储单元
  • 第i位置赋值为要插入的元素
    // 代码过于简单,忽略

5.3 数据元素删除

同插入的场景中提到的,那么删除的过程自然就是插入的逆序,还用刚才的例子,假如这个新来的同学在第i位置坐的很不爽,前后的同学总是合谋欺负他,那么他要离开这个位置换到其他排,那么从第i+1位置开始,都需要依次向前移动一个位置,并将最后一个位置元素清除(线性表长度减1)

  • 判断要删除的位置是否合理,不合理抛出异常
  • 从第i+1个数据元素到最后一个数据元素,依次向前移动一个存储单元
  • 线性表长度减1

6、数组的优劣势

优势:

  • 快速获取线性表中的任意位置数据元素
  • 数据元素顺序存储,不需要维护数据元素之间的关联关系(利用物理内存位置维护,地址依次递增)

劣势:

  • 插入和删除操作需要移动线性表中的大多数数据元素
  • 线性表长度大于分配的存储空间时,需要重新申请存储空间,性能有比较大的消耗
  • 存储空间连续,当线性表的长度很大是,内存分配是个问题
一分也是爱❤️