手记

数据结构和算法(三)数组

一、数组的定义:

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

 线性表(Linear List):数据排成像线一样的数据结构,每个线性表的数据只有两个反向。

特性:随机访问。优秀的访问速度,低效的新增和删除。

如数组、链表、栈、队列

非线性表:数据不是简单的前后关系。如:二叉树、图、堆等

数组寻址公式

    a[i]_address = base_address+[i]*data_type_size

base_address 为数组分配的内存块的首地址, data_type_size表示数组为每个元素的大小。

数组下标最确切的的说法应该叫偏移(offset)

为什么数组的下标是从0开始

因为从1开始,地址的计算公式就变成

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

每次随机访问数组元素,cpu就多一次减法指令,而数组是非常基础的数据结构,通过下标随机访问数组元素是非常基础的编程基础,效率的优化需要做到极致,所以数组的下标从0开始,而不是以1开始。


 VM 标记清除垃圾回收算法

大多数主流虚拟机采用可达性分析算法来判断对象是否存活,在标记阶段,会遍历所有 GC ROOTS,将所有 GC ROOTS 可达的对象标记为存活。只有当标记工作完成后,清理工作才会开始。

不足:1.效率问题。标记和清理效率都不高,但是当知道只有少量垃圾产生时会很高效。2.空间问题。会产生不连续的内存空间碎片。

二维数组的内存寻址

对于 m * n 的数组,a [ i ][ j ] (i < m,j < n)的地址为:

address = base_address + ( i * n + j) * type_size













0人推荐
随时随地看视频
慕课网APP