数组

146 阅读4分钟

唐诗开篇,与文无关。 

于易水送人 

  • 骆宾王(约619年~约687年),婺(wù)州义乌(浙江义乌)人。与王勃、杨炯、卢照邻并称“初唐四杰”,世称“王杨卢骆”。他的写作风格在当时享誉一时,其诗内容广泛,格调高远,多感叹个人遭遇,抨击社会现实之作。 

此地别燕丹,壮士发冲冠。 

昔时人已没,今日水犹寒。


什么是数组?

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

线性表(Linear List)。线性表就是数据排成像一条线一样的数据结构。数组、链表、队列、栈等都是线性表结构。线性表上的数据最多只有前和后两个方向。 

非线性表。二叉树、堆、图等都是非线性结构,之所以叫非线性,是因为在非线表中数据之间并不是简单的前后关系。

连续的内存空间和相同的数据类型。正式因为有这两个限制,才有了随机访问的特性。但是正因为内存空间要保持连续性,造成数组在插入、删除操作时候需要做大量的数据搬移工作。 

数组可以根据下标随机访问数组元素。 

数组连续内存寻址公式:a[i]_address = base_address + i * data_type_size

其中base_address为内存块首地址。data_type_size为数组中每个元素的大小。

容器能否完全替代数组?

针对数组类型,很多语言都提供了容器类,比如java中的ArrayList。在项目开发中又该如何选择?

以Java为例,ArrayList的最大优势就是可以将很多数组的操作细节封装起来,并且支持动态扩容(其自动扩容为原来的1.5倍)。但是由于扩容的操作涉及内存的申请和数据搬移,是比较耗时的。所以,如果实现知道要存储的数据大小,最好在创建ArrayList的时候事先是定大小

数组空间不够时,我们就要重新申请一块更大的内存空间,将原来的数据复制过来,然后在进行新数据的插入操作

有的时候数组获取更适合应用场景。

  1. 如果数据大小事先已知,并且对数据的操作非常简单,用不到ArrayList提供的大部分方法,可以直接使用数组。
  2. Java ArrayList无法存储基本类型,比如int、long,需要封装为integer、Long类,而Autoboxing、Unboxing则有一定的性能消耗,所以如果特别关注性能,或者希望使用基本数据类型,就可以选择数组。
  3. 当要表示多维数组时,用数组更加直观。比如Object[][] array;如果使用容器类则需要这样定义:ArrayList<ArrayList> array。

在平时业务开发中,可直接使用编程语言提供的容器类,但是,如果底层开发,直接使用数组可能会更合适。

问题?

为什么在大多数语言中,数组都是以0开始编号,而不是用1开始编号?

从数组内存模型来看,“下标”最确切的定义应该是“偏移(oddset)”。如果用a来表示数组的首地址,a[0]就是偏移为0的元素的地址,也就是首地址,a[k]表示偏移k个type_size的位置,

a[k]_address = base_address + k * type_size

但是如果从1开始编号,那么a[k]的内存放地址就是:


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

对比发现,从1开始编号,每次随机访问就多了一次减法运算,对于CPU来说,就是多一次减法指令。

另外C语言设计者就是用0开始记录数组下标。之后的Java、JavaScript等都效仿了C语言,因此继续沿用从0开始的计数习惯。

小结 

数组使用一块连续内存空间,来存储相同类型的一组数据,最大的特点就是支持随机访问。但是插入、删除操作的效率比较低,平均情况时间复杂度为O(n)。

 


课后作业: 

  • 实现一个支持动态扩容的数组 
  • 实现一个大小固定的有序数组,支持动态增删改操作 
  • 实现两个有序数组合并为一个有序数组


本文是 算法与数据结构之美_05学习笔记。