※ 引述《Lordaeron (Terry)》之铭言： : ※ 引述《adrianshum (Alien)》之铭言： : : 就说你没在留心别人在说什麽. : : 你可以把 array 或 linked list 理解成实作 好,不要吵. 就算这个千万不能想成那个,那也只不过是: "直尺的边线很直" "太阳从东边出来" 那一类的常识,不是吗? 想想看,为什麽大家一开始学程式,老师说array的取值时间是O(1),他们就一点 没有怀疑,可能也没有具体思考过? 为什麽array的任一元素取值是O(1)时间成本? 在此所讲的array是 C 的记忆体对应的基本 array. 为什麽取值是 O(1) ? 是因为这个array对应记忆体,而 array的底层---记忆体的取值都是用base和offset 来算,任何位置全都是几个加法求出来,然後去取值,所以是 O(1). 由这项基本知识,我们可以隐约知道, array 的随机存取便利并不是因为 C 语言本身 的特质,而只不过是几乎大部份的程式语言基础都在这一台机器上. 机器特性是这样, 顺着机器的特性, array 才有随机存取的特徵. 最初那位love谁网友所回应说:stack或queue要怎麽做 array? 是,的确很具体. 但是如果就因为这样,就认为任何语言全部都是这样,太不切实际. 事实上,跳到不同语言中,思考的基础不会一样. 若你只是因为站在 C 语言中 看到 array 就是这样子,就拒绝接受其他种语言的可能,拒绝思考用其他模型实作 array, 那未免太可怜. 这种思考方式只不过是打从你学程式一开始,就已经养成拒绝思考的习惯. 说穿了,很多人跟你一样,全都是时薪多少钱的程式匠而已,没什麽了不起. 与其留在圈圈之内,因为无足够资讯而说不,倒不如跨出圈圈,多看一点点东西, 然後有足够的资讯可以说不. 另外... 如果把随机存取的便利抽掉, array 的原型是什麽? Array 就是一堆数字(索引)对应到一堆目标物,所以 array 的原型就是函数. 照电脑电路来看,可能是因为电力速度很快,所以从索引数字,base,offset算到目标元素 太快了. 但是,换作你用人力在真正的仓储系统找东西,给你一个编号,你还是找蛮久的, 所以随机存取可能不是必要. 不过,许多别的电脑语言也要实作 array, VM也需要实作 记忆空间,像 Java 的 heap. 在这时,所谓实体结构的坚持就很没有必要. 如你所想,你认为我用stack做出linked list其实是用linked list实作linked list, 显然是直接认定 stack 就是linked list. 但是这样想也很有缺陷,谁说stack就一定 是linked list了? 对一个抽象结构我们只关心介面,而不关心实作,你这样一下子 进去拆解里头的结构显然很乱. 同样的道理,用来做资料库索引的B-Tree,也直接想成 用array实作的树结构,那就回去慢慢分析所有的结构,被那堆资讯淹没. 我们只是需要那些抽象结构帮助好用好想而已,而不是强调抽象结构必须是怎麽样的 抽象结构,或不得是哪些实体结构. ------ 最後回归正题: 根本不值得争论stack可不可以做 linked list. 以我回应原po的文字意思,是说, "这种问题很好,表示你有在动脑袋." "如果你有在动脑袋,我建议你怎麽动脑袋比较好." 重点是在对原po的学习加以鼓励. 但是,你觉得我们真的要浪费时间争执 stack 和 queue 到底可以不可以做 array 和 linked list 吗? 等你争完了,会发现:一场空. 我随便举一个例子,例子可能很不完整很破烂,你却认真分析那个例子, 那麽谁是傻子? 你早就知道这没有意义了,不是吗? --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.160.209.63 ※ 编辑: yauhh 来自: 218.160.209.63 (03/10 23:37)