search

DeathKing / Learning-SICP

MIT视频公开课《计算机程序的构造和解释》中文化项目及课程学习资料搜集。
https://learningsicp.github.io
10.95k stars 1.54k forks source link

《Lec2b：复合数据》课程答疑 #75

Closed DeathKing closed 2 years ago

DeathKing commented 6 years ago

同学们请在这里写下关于《Lec2b：复合数据》课程的相关疑惑。

mortis-0 commented 4 years ago

若LIsp中的一切数据对象对cons操作封闭，那么一切数据结构都可以看做二叉树，我想知道只使用这种构造方式，能否实现O(1)内可随机访问的数据结构（如C中的数组以下标访问）。才疏学浅，如有错漏或误解之处，还请各位赐教。

DeathKing commented 4 years ago

若LIsp中的一切数据对象对cons操作封闭，那么一切数据结构都可以看做二叉树，我想知道只使用这种构造方式，能否实现O(1)内可随机访问的数据结构（如C中的数组以下标访问）。才疏学浅，如有错漏或误解之处，还请各位赐教。

不行。因此常见的 Scheme 实现中，会有 Vector 类型的数据结构。

leetking commented 4 years ago

不行。目前内存的硬件结构决定了数组能实现O(1)访问，链表或树结构不能实现O(1)访问。从表达层面来看，忽略访问效率，底层采用数组或树都能实现上层的各种结构。