常用数据结构必知必会
王争
前Google工程师
立即订阅
1 人已学习
课程目录
已完结 5 讲
01 | 数组：为什么很多编程语言中数组都从0开始编号？
02 | 链表（上）：如何实现LRU缓存淘汰算法?
03 | 链表（下）：如何轻松写出正确的链表代码？
04 | 栈：如何实现浏览器的前进和后退功能？
05 | 队列：队列在线程池等有限资源池中的应用
常用数据结构必知必会
登录|注册

01 | 数组：为什么很多编程语言中数组都从0开始编号？

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

如何实现随机访问？

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

精选留言(13)

  • jasonlee
    关于插入降时间复杂度的demo.若数组数据完全无序.还会在啥样的场景下出现需要插入到固定位置的需求么.感觉这个O(1)的场景有些矛盾.
    2019-08-27
    2
    8
  • 壹笙☞漂泊
    二维数组的寻址
    a[m][n]_addr ＝ base_addr + type_size(hLen×m + n)
    hLen是行长度
    这样对么老师？

    作者回复: 对的

    2019-08-26
    4
    5
  • Kody
    老师，是不是这样
    a[m][n] = base_address + m * n_typesize * n_arraysize + n * n_typesize

    作者回复: 不大对 看看其他留言的答案吧

    2019-08-26
    1
    2
  • Jr
    c语音数组指针的内存地址是储存了第一个元素得值，所以第一个元素的偏移量为0，所以从0开始，看完后我，是这么理
    2019-08-26
    1
  • VeryYoung
    ArrayList确实用的比较多
    2019-09-01
  • 深感不足
    老师 这个计算地址是按照存储类型一致来算的吗？

    作者回复: 是的，你可以看看这个：
    https://mp.weixin.qq.com/s/E-c41h2v_AfffrlAQpkyLg

    2019-08-29
  • 孟秋
    二维数组通常可以当做一个table表格，可以理解为横纵坐标，这是一个多个连续的内存空间：
    i表示横坐标；
    j表示纵坐标；
    i*(j+1)+j表示偏移量
    推导公式：
    a[i][j]_address = base_address + (i*(j+1)+j) * data_type_size
    老师对吗？

    作者回复: 不大对 看看留言其他同学的答案吧

    2019-08-29
  • 九三
    int main(int argc, char* argv[]){
        int i = 0;
        int arr[3] = {0};
        for(; i<=3; i++){
            arr[i] = 0;
            printf("hello world\n");
        }
        return 0;
    }
    这个我用xcode输出四次就奔了，没有无限打印“hello world”;
    还有就是 a[3] 也会被定位到某块不属于数组的内存地址上，而这个地址正好是存储变量 i 的内存地址，那么 a[3]=0 就相当于i=0，所以就会导致代码无限循环。这句话怎么理解呢

    作者回复: 你可以看看留言区的其他留言，有解释到的。

    2019-08-28
  • 👻 小二
    老师，文中的C死循环代码在windows系统是不会死循环的， 会崩溃，linux下就会死循环

    作者回复: 看看留言 里面有讲到

    2019-08-27
  • Usama Bin Laden
    链表适合插入、删除，时间复杂度 O(1)。感觉也是不够准确的，插入数据的时候，插入这个过程是O(1),但是，你插入之前，肯定要去查找这个节点，这个过程是O(logN)。所以整个插入来说，不能说是O(1)

    作者回复: 可以看下这篇文章
    https://mp.weixin.qq.com/s/Md8tprLiESR6oQKXs_Aihw

    2019-08-27
  • 狐狸
    c中 对于a[n][m]: a[i][j] = *(a + i + j * n)
    2019-08-27
  • 九三
    a[i][j]
    base_adress+ j * (col*element_size) + (j*element_size)
    base_adress+ j * (col*element_size)这个计算出每行的首地址 + 上每行的偏移量(j*element_size) = a[i][j]的地址
    col为总列数 element_size为每个元素大小
    式子没合并
    2019-08-27
  • ClassNotFoundException
    标记清除算法是先标记需要清除的内存，如没有被引用的类，内存等，然后一起删除，可以不动其他内存的位置，但是就会导致内存不连续
    2019-08-27
收起评论
13
下载
客户端
返回
顶部