数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

05 | 数组:为什么很多编程语言中数组都从0开始编号?

王争 2018-10-01
提到数组,我想你肯定不陌生,甚至还会自信地说,它很简单啊。
是的,在每一种编程语言中,基本都会有数组这种数据类型。不过,它不仅仅是一种编程语言中的数据类型,还是一种最基础的数据结构。尽管数组看起来非常基础、简单,但是我估计很多人都并没有理解这个基础数据结构的精髓。
在大部分编程语言中,数组都是从 0 开始编号的,但你是否下意识地想过,为什么数组要从 0 开始编号,而不是从 1 开始呢? 从 1 开始不是更符合人类的思维习惯吗?
你可以带着这个问题来学习接下来的内容。

如何实现随机访问?

什么是数组?我估计你心中已经有了答案。不过,我还是想用专业的话来给你做下解释。数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。
这个定义里有几个关键词,理解了这几个关键词,我想你就能彻底掌握数组的概念了。下面就从我的角度分别给你“点拨”一下。
第一是线性表(Linear List)。顾名思义,线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组,链表、队列、栈等也是线性表结构。
而与它相对立的概念是非线性表,比如二叉树、堆、图等。之所以叫非线性,是因为,在非线性表中,数据之间并不是简单的前后关系。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(615)

  • 杰杰 置顶
    JVM标记清除算法:

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

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

    二维数组内存寻址:

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

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

    另外,对于数组访问越界造成无限循环,我理解是编译器的问题,对于不同的编译器,在内存分配时,会按照内存地址递增或递减的方式进行分配。老师的程序,如果是内存地址递减的方式,就会造成无限循环。

    不知我的解答和理解是否正确,望老师解答?

    作者回复: 完全正确✅

    2018-10-01
    18
    744
  • slvher
    对文中示例的无限循环有疑问的同学,建议去查函数调用的栈桢结构细节(操作系统或计算机体系结构的教材应该会讲到)。

    函数体内的局部变量存在栈上,且是连续压栈。在Linux进程的内存布局中,栈区在高地址空间,从高向低增长。变量i和arr在相邻地址,且i比arr的地址大,所以arr越界正好访问到i。当然,前提是i和arr元素同类型,否则那段代码仍是未决行为。

    作者回复: 👍 高手!

    2018-10-01
    12
    1088
  • 夜下凝月
    突然想到了垃圾桶。
    生活中,我们扔进屋里垃圾桶的垃圾,
    并没有消失,只是被 ''标记'' 成了垃圾,
    只有垃圾桶塞满时,才会清理垃圾桶。
    再次存放垃圾
    2018-10-07
    13
    448
  • 不诉离殇
    例子中死循环的问题跟编译器分配内存和字节对齐有关 数组3个元素 加上一个变量a 。4个整数刚好能满足8字节对齐 所以i的地址恰好跟着a2后面 导致死循环。。如果数组本身有4个元素 则这里不会出现死循环。。因为编译器64位操作系统下 默认会进行8字节对齐 变量i的地址就不紧跟着数组后面了。

    作者回复: 高手!

    2018-10-01
    7
    428
  • zyzheng
    关于数组越界访问导致死循环的问题,我也动手实践了一下,发现结果和编译器的实现有关,gcc有一个编译选项(-fno-stack-protector)用于关闭堆栈保护功能。默认情况下启动了堆栈保护,不管i声明在前还是在后,i都会在数组之后压栈,只会循环4次;如果关闭堆栈保护功能,则会出现死循环。请参考:https://www.ibm.com/developerworks/cn/linux/l-cn-gccstack/index.html

    作者回复: 就喜欢你这种自己动手研究的同学

    2018-10-03
    7
    233
  • Nirvanaliu
    文章结构:
    数组看起来简单基础,但是很多人没有理解这个数据结构的精髓。带着为什么数组要从0开始编号,而不是从1开始的问题,进入主题。
    1. 数组如何实现随机访问
    1) 数组是一种线性数据结构,用连续的存储空间存储相同类型数据
    I) 线性表:数组、链表、队列、栈 非线性表:树 图
    II) 连续的内存空间、相同的数据,所以数组可以随机访问,但对数组进行删除插入,为了保证数组的连续性,就要做大量的数据搬移工作
    a) 数组如何实现下标随机访问。
    引入数组再内存种的分配图,得出寻址公式
    b) 纠正数组和链表的错误认识。数组的查找操作时间复杂度并不是O(1)。即便是排好的数组,用二分查找,时间复杂度也是O(logn)。
    正确表述:数组支持随机访问,根据下标随机访问的时间复杂度为O(1)
    2. 低效的插入和删除
    1) 插入:从最好O(1) 最坏O(n) 平均O(n)
    2) 插入:数组若无序,插入新的元素时,可以将第K个位置元素移动到数组末尾,把心的元素,插入到第k个位置,此处复杂度为O(1)。作者举例说明
    3) 删除:从最好O(1) 最坏O(n) 平均O(n)
    4) 多次删除集中在一起,提高删除效率
    记录下已经被删除的数据,每次的删除操作并不是搬移数据,只是记录数据已经被删除,当数组没有更多的存储空间时,再触发一次真正的删除操作。即JVM标记清除垃圾回收算法。
    3. 警惕数组的访问越界问题
    用C语言循环越界访问的例子说明访问越界的bug。此例在《C陷阱与缺陷》出现过,很惭愧,看过但是现在也只有一丢丢印象。翻了下书,替作者加上一句话:如果用来编译这段程序的编译器按照内存地址递减的方式给变量分配内存,那么内存中的i将会被置为0,则为死循环永远出不去。
    4. 容器能否完全替代数组
    相比于数字,java中的ArrayList封装了数组的很多操作,并支持动态扩容。一旦超过村塾容量,扩容时比较耗内存,因为涉及到内存申请和数据搬移。
    数组适合的场景:
    1) Java ArrayList 的使用涉及装箱拆箱,有一定的性能损耗,如果特别管柱性能,可以考虑数组
    2) 若数据大小事先已知,并且涉及的数据操作非常简单,可以使用数组
    3) 表示多维数组时,数组往往更加直观。
    4) 业务开发容器即可,底层开发,如网络框架,性能优化。选择数组。
    5. 解答开篇问题
    1) 从偏移角度理解a[0] 0为偏移量,如果从1计数,会多出K-1。增加cpu负担。为什么循环要写成for(int i = 0;i<3;i++) 而不是for(int i = 0 ;i<=2;i++)。第一个直接就可以算出3-0 = 3 有三个数据,而后者 2-0+1个数据,多出1个加法运算,很恼火。
    2) 也有一定的历史原因
    2018-10-01
    3
    182
  • Rain
    根据我们前面讲的数组寻址公式,a[3] 也会被定位到某块不属于数组的内存地址上,而这个地址正好是存储变量 i 的内存地址,那么 a[3]=0 就相当于 i=0,所以就会导致代码无限循环。

    *而这个地址正好是存储变量 i 的内存地址*这个地方没看太懂,为什么正好就是i的内存地址呢?

    谢谢老师。
    2018-10-01
    2
    168
  • Zzzzz
    对于死循环那个问题,要了解栈这个东西。栈是向下增长的,首先压栈的i,a[2],a[1],a[0],这是我在我vc上调试查看汇编的时候看到的压栈顺序。相当于访问a[3]的时候,是在访问i变量,而此时i变量的地址是数组当前进程的,所以进行修改的时候,操作系统并不会终止进程。

    作者回复: 👍

    2018-10-01
    106
  • 何江
    有个小问题,我觉得 随机访问Ramdom Acess 更应该翻译成 任意访问,更能表达数组的特性。不过国内书籍都是翻译成随机。新手朋友刚看到时会有一些理解问题,如数组怎么会是随机访问的呢(当初我就是这么想的)
    2018-10-02
    90
  • 李朋远
    老师,您好,个人觉得您举例的内存越界的循环应该限制在x86架构的小端模式,在别的架构平台上的大端模式应该不是这样的!

    作者回复: 说的没错 👍

    2018-10-03
    1
    54
  • shane
    无限循环的问题,我认为内存分配是从后往前分配的。例如,在Excel中从上往下拉4个格子,变量i会先被分配到第4个格子的内存,然后变量arr往上数分配3个格子的内存,但arr的数据是从分配3个格子的第一个格子从上往下存储数据的,当访问第3索引时,这时刚好访问到第4个格子变量i的内存。
    不知道对不对,望指正!

    作者回复: 形象👍

    2018-10-01
    1
    49
  • hope
    根据我们前面讲的数组寻址公式,a[3] 也会被定位到某块不属于数组的内存地址上,而这个地址正好是存储变量 i 的内存地址,那么 a[3]=0 就相当于 i=0,所以就会导致代码无限循环。

    这块不是十分清晰,希望老师详细解答一下,谢谢!

    看完了 ,之前说总结但是没总结,这次前连天的总结也补上了,打卡

    作者回复: 1. 不同的语言对数组访问越界的处理方式不同,即便是同一种语言,不同的编译器处理的方式也不同。至于你熟悉的语言是怎么处理的,请行百度。
    2. C语言中,数组访问越界的处理是未决。并不一定是错,有同学做实验说没问题,那并不代表就是正确的。
    3. 我觉得那个例子,栈是由高到低位增长的,所以,i和数组的数据从高位地址到低位地址依次是:i, a[2], a[1], a[0]。a[3]通过寻址公式,计算得到地址正好是i的存储地址,所以a[3]=0,就相当于i=0.
    4. 大家有不懂的多看看留言,留言区还是有很多大牛的!我可能有时候回复的不及时,或者同样的问题只回复一个同学!

    2018-10-01
    38
  • 1. 我认为文中更准确的说法可能是标记-整理垃圾回收算法。标记-清除算法在垃圾收集时会先标记出需要回收的对象,标记完成后统一回收所有被标记的对象。清除之后会产生大量不连续的内存碎片。标记-整理垃圾回收算法在标记完成之后让所有存活的对象都向一端移动,然后直接清理掉边界以外的内存。
    2. 假设二维数组大小为m*n,那么寻址公式为
    a[i][j]_address = base_address + (i * n+j)*data_type_size

    3. C语言变量的内存申请可以看做是地址按照从大到小连续申请的,因为i在arr前面申请,所以arr[3]的地址和i的地址相同。

    例如对于如下代码:
    int i = 0;int j = 1;int k = 2; int arr[3] = {0}; cout<<"i-"<<&i<<endl;
    cout<<"j-"<<&j<<endl;
    cout<<"k-"<<&k<<endl;
    cout<<"arr-"<<&arr<<endl;
    cout<<"arr3-"<<&arr[3]<<endl;

    运行结果:
    i-0x28ff0c

    j-0x28ff08

    k-0x28ff04

    arr-0x28fef8

    arr3-0x28ff04

    作者回复: 👍

    2018-10-03
    37
  • wistbean
    ————总结一下————

    什么是数组

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



    1.线性表
    线性表就是数据排成像一条线一样的结构。
    常见的线性表结构:数组,链表、队列、栈等。

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

    优点:两限制使得具有随机访问的特性
    缺点:删除,插入数据效率低

    数组怎么根据下标随机访问的?

    通过寻址公式,计算出该元素存储的内存地址:
    a[i]_address = base_address + i * data_type_size

    为何数组插入和删除低效

    插入:
    若有一元素想往int[n]的第k个位置插入数据,需要在k-n的位置往后移。
    最好情况时间复杂度 O(1)
    最坏情况复杂度为O(n)
    平均负责度为O(n)

    如果数组中的数据不是有序的,也就是无规律的情况下,可以直接把第k个位置上的数据移到最后,然后将插入的数据直接放在第k个位置上。

    这样时间复杂度就将为 O(1)了。

    删除:
    与插入类似,为了保持内存的连续性。
    最好情况时间复杂度 O(1)
    最坏情况复杂度为O(n)
    平均负责度为O(n)

    提高效率:将多次删除操作中集中在一起执行,可以先记录已经删除的数据,但是不进行数据迁移,而仅仅是记录,当发现没有更多空间存储时,再执行真正的删除操作。这也是 JVM 标记清除垃圾回收算法的核心思想。

    数组访问越界问题
    C语言中的数据越界是一种未决行为,一般比较难发现的逻辑错误。相比之下,Java会有越界检查。

    用数组还是容器?
    数组先指定了空间大小
    容器如ArrayList可以动态扩容。
    1.希望存储基本类型数据,可以用数组
    2.事先知道数据大小,并且操作简单,可以用数组
    3.直观表示多维,可以用数组
    4.业务开发,使用容器足够,开发框架,追求性能,首先数组。

    为什么数组要从 0 开始编号?
    由于数组是通过寻址公式,计算出该元素存储的内存地址:
    a[i]_address = base_address + i * data_type_size
    如果数组是从 1 开始计数,那么就会变成:
    a[i]_address = base_address + (i-1)* data_type_size

    对于CPU来说,多了一次减法的指令。
    当然,还有一定的历史原因。

    ————课后思考————

    1.我理解的JVM标记清除垃圾回收算法:在标记阶段会标记所有的可访问的对象,在清除阶段会遍历堆,回收那些没有被标记的对象。现在想想,和「如果数组中的数据不是有序的,也就是无规律的情况下,可以直接把第k个位置上的数据移到最后,然后将插入的数据直接放在第k个位置上。」思想类似。

    2. 对于一维数组:a[i]_address = base_address + (i)* data_type_size
    二维数组如果是m*n,那么a[i][j]== base_address + (i*n+j)* data_type_size。
    2.
    2018-10-02
    35
  • qx
    1.老师您好,二维数组存储也是连续的吧。
    2.对于数组删除abc,还没太理解?申请的是三个地址空间,a(3)越界了,那么它会去找哪个地址的数据呢?而且for循环就是三次啊,如何无限打印?
    3.老师时候每讲完一节数据结构可以对应到一些编程题目给大家思考啊例如leetcode或其他的?
    2018-10-01
    23
  • HCG
    对于无线循环那个问题解释

    个人认为应该按照这样的顺序声明:
    int arr[3]={0};
    int i;
    因为在计算机中程序一般顺序分配存储空间,这样声明,首先分配0 1 2三个存储单元给数组arr,然后再分配 4 存储单元给变量i,然后根据数组访问公式即会出现无线循环。
    不知道对不对,还请老师指点。
    2018-10-01
    19
  • CathyLin
    看完 & 写完笔记来打卡,发现评论区好多大牛!光是翻看了评论区就收获了好多!
    2018-10-02
    16
  • Teanmy
    汇总一下各位大神关于那段代码无限循环的总结:
    这段代码无限循环原因有2,以及一个附加条件:
    1.栈空间从高往低依次分配,i占4字节,接着arr占12字节,内存从高往低是这样:存i的4字节|arr[2]|arr[1]|arr[0],数组访问是通过“baseAddr+index乘typeSize”得到,算下来当index=3时,刚好是i的地址
    2.这里刚好满足字节对齐,系统为64位系统,字长64,那么字节对齐必须是8字节的倍数,刚好i变量和arr变量占了16字节,对齐了
    如果这里将arr[3]改为arr[4],为了对齐,内存从高往低是这样:存i的4字节|空4字节|arr[3]|arr[2]|arr[1]|arr[0],那么arr[4]刚好是空的4字节,无法影响到i的值,则并不会无限循环

    附加条件:编译时gcc默认会自动添加越界保护,此处要达到无限循环效果,编译时需加上-fno-stack-protector去除该保护
    2019-04-07
    2
    15
  • 韩某众
    我也是js开发者,前面的那位js开发者同学的问题其实不难解决。
    如果不知道老师的“数组”究竟是什么,只要查一下数据结构里的“数组”和“链表”的定义,然后搜一些关于js引擎对js定义下“数组”的底层实现的文章,比如“深究 JavaScript 数组 —— 演进&性能”。就知道老师在说什么了。
    互联网从业者更要善用互联网,加油!

    作者回复: 说得好!

    2018-10-01
    15
  • Kudo
    假设二维数组的维度为m * n,则 a[i][j]_address = base_address + (i * n + j) * type_size
    2018-10-01
    14
收起评论
99+
返回
顶部