数据结构与算法系列之数组

用户头像
书旅
关注
发布于: 2020 年 09 月 14 日
数据结构与算法系列之数组

什么是数组?



忘了在哪本书看见过一句话“理解了概念性的东西,你就学会了70%”



回到主题,什么是数组?数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据



概念中有两个关键的地方:



  1. 数组是一种线性数据结构

  2. 数组中存储的是连续的内存空间和相同类型的数据



什么是线性数据结构

有数据结构基础的小伙伴都应该知道,线性结构就是数据排成一条线一样的数据结构,也就意味着它仅有前后两个方向,比如队列、单链表、栈等,也是线性结构



与它相对的就是非线性表,最典型的就是树和图。他们的特点就是并不是只有前后这种关系



连续的内存空间和相同类型的数据

正因为有了这个特性,使得数组可以进行“随机访问”。虽然访问数组中某个元素变得很快,但缺点就是在修改(删除、插入)数组的时候,操作会变得很麻烦,因为要保证数组内存空间的连续性,所以不得不进行繁琐的数据移动



假设有一个长度为5的int类型的数组var a [5]int,假设给这个数组分配的内存空间首地址是1000,则这个数组分配的内存空间为1000~1019,看下图



操作系统会为每一个内存单眼分配一个地址,通过这个地址来访问内存中的数据。当操作系统需要随机访问数组中的某一个元素时,它会通过下边这个寻址公式来计算出某个元素的存储地址

a[i]_address = base_address + i * data_type_size
data_type_size:表示数组中每个元素的大小。比如int类型,它占用的是4个字节,所以这里data_type_size就是4



数组和链表的区别是什么

通过上边对数组的介绍,可以看出来,数组适合查找操作。但是查找的时间复杂度并不为O(1)。即便是排好序的数组,你用二分查找,时间复杂度也是O(logn)。所以,数组支持随机访问,根据下标随机访问的时间复杂度为O(1)



数组相关操作



插入元素



数组头部插入元素



在数组的头部插入元素,为了保证空间的连续性,需要将数组中所有的元素向后移一位,然后将待插入元素放入到首部位置



代码实现

function insertIntoHead($elem, $arr)
{
echo "原始数组:".PHP_EOL;
print_r($arr);
$i = 0;
$len = count($arr);
while ($i < $len) {
$arr[$len-$i] = $arr[$len-$i-1];
$i++;
}
$arr[0] = $elem;
echo "头部插入元素之后结果:".PHP_EOL;
print_r($arr);
}



数组中间插入元素



在数组的中间某个位置插入元素,需要将待插入位置以后的元素均向后移动一位



代码实现

function insertIntoMid($elem, $position, $arr)
{
echo "原始数组:".PHP_EOL;
print_r($arr);
$len = count($arr);
$i = $position-1;
$value = $arr[$i];
$arr[$i] = $elem;
$head = $i+1;
$offset = $position-1;
while ($i < $len) {
$arr[$len-$i+$offset] = $arr[$len-$i-1+$offset];
$i++;
}
$arr[$head] = $value;
echo "头部插入元素之后结果:".PHP_EOL;
print_r($arr);
}



数组尾部插入元素



在尾部插入元素,不需要移动元素,直接放在当前的末尾元素后边即可



删除元素

数组头部删除元素



删除数组头部元素,将所有的元素向前移动一位即可



代码实现:

function delHead($arr)
{
echo "删除前:".PHP_EOL;
print_r($arr);
for ($i=0; $i<count($arr)-1; $i++) {
$arr[$i] = $arr[$i+1];
}
unset($arr[count($arr)-1]);
echo "删除后".PHP_EOL;
print_r($arr);
}



数组中间删除元素



将待删除元素后边的所有元素向前一定一位



代码实现:

function delMid($position, $arr)
{
echo "删除前:".PHP_EOL;
print_r($arr);
$len = count($arr);
for ($i=$position-1; $i<$len-1; $i++) {
$arr[$i] = $arr[$i+1];
}
unset($arr[$len-1]);
echo "删除后".PHP_EOL;
print_r($arr);
}



数组尾部删除元素



直接删除即可,无需移动数组中的元素



如果在数组的末尾插入元素,那就不需要移动数据了,这时的时间复杂度为O(1)。但如果在数组的开头插入元素,那所有的数据都需要依次往后移动一位,所以最坏时间复杂度是O(n)。 因为我们在每个位置插入元素的概率是一样的,所以平均情况时间复杂度为(1+2+…n)/n=O(n)。删除元素也是同理



为什么大多数编程语言中,数组要从0开始编号,而不是从1开始呢?

从数组存储的内存模型上来看,“下标”最确切的定义应该是“偏移(offset)”。前面也说到,如果用a来表示数组的首地址,a[0]就是偏移为0的位置,也就是首地址。a[k]就表示偏移k个 type_size 的位置,所以计算a[k]的内存地址只需要用这个公式

a[k]_address = base_address + k * type_size



但是,如果数组从1开始计数,那我们计算数组元素a[k]的内存地址就会变为

a[k]_address = base_address + (k-1)*type_size

对比两个公式,我们不难发现,从1开始编号,每次随机访问数组元素都多了一次减法运算,对于CPU来说,就是多了一次减法指令



数组作为非常基础的数据结构,通过下标随机访问数组元素又是其非常基础的编程操作,效率的优化就要尽可能做到极致。所以为了减少一次减法操作,数组选择了从0开始编号,而不是从1开始



参考:

《数据结构与算法之美》

《零基础学数据结构》





发布于: 2020 年 09 月 14 日 阅读数: 288
用户头像

书旅

关注

公众号:IT猿圈 2019.04.11 加入

还未添加个人简介

评论 (2 条评论)

发布
用户头像
如果我没记错的话,这个就是 极客时间那个 课程
2020 年 09 月 14 日 12:15
回复
有参考,文末有说明
2020 年 09 月 14 日 13:44
回复
没有更多了
数据结构与算法系列之数组