乐趣区

关于数据结构:数据结构与算法系列之数组

jiezi

什么是数组？

忘了在哪本书看见过一句话“了解了概念性的货色，你就学会了 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 开始

参考：
《数据结构与算法之美》
《零根底学数据结构》

退出移动版