※ 引述《jimmy5566 (jimmy)》之铭言： : 有个问题觉得怪怪的 : 想厘清一下 : 就是stack和queue都可以用array和linked list来制作 : 那linked list可以用array和stack来制作吗? : 麻烦了~谢谢 从你的问答中可以看到一些事情,第一,你思考的可能是单纯的对立关系: 如果这边这些可以用那边的东西实作,则那边的东西应该也可以用这边的东西实作. 虽然事实可能不是这麽单纯. 不过,如果你还是学生,恭喜你,你有足够的自由空间 可以做这样的思考,好处是一来别人可能不会想这种事情,所以你有投入时间思考 这问题的机会,二来是社会现实还不够近逼甚至倾轧得你不得想这个问题. 从你的问答中所看到的第二个情况,你可能还没熟识 stack, queue, array, linked list 的特徵. 有些资料结构会很认真把这些项目抽象化, 像 Horowitz 先生的那本经典的资料结构教科书,会直接用ADT表达. 你可以先看看那样的书. 你可以仔细想想这些资料结构或资料格式的特徵: Array: 一堆 key-value 配对, 所有的 key 是连续整数. Linked list: 一堆有限数目的物件,任何一个对另一个有前後关系. Stack: 与 linked list 类似之处是有限数目的物件,物件有前後关系. 并且加上 stack 自己的限制,只有一个端点可以将新物件加进去 产生另一个 stack, 或是把存在的物件拿走,剩下的也是 stack. queue: ... 如果要解 "用 stack 制作 linked list" 这样的问题,你可以先把 linked list 所拥有的特徵抓出来,像是二个物件之间有前後关系,以及它还可以删掉一些中间 的物件,剩下的也构成一个 linked list. 再来看看 stack 提供了哪些特徵 可以达到 linked list 所需要的功能: 新增, 删除, 随意位置删除, 前进定位, 回溯等等, 看用 stack 该怎麽组合可以做得到. 例如,令有一堆 stack S[1..N], 任何一个 stack S[i] 的规格为: S[i].push(D) => S[i]' ;; S[i]'是S[i]加了一项物件D S[i]'.pop => { D, S[i] } ;; 同上,而pop之後取出资料并得到另一stack 你可以说以下这样的结构拥有 linked list 一部份的特徵: LL = S[1].push(S[2].push(S[3].push(...S[N].push(nil)))...) 因为 LL.next = S[1].pop = { D[1], LL' = S[2] } LL'.next = S[2].pop = { D[2], LL'' = S[3] } ... 这样就是 linked list 前进并定位的功能. 第三个所见到的事情,很明显,有蛮多人会拒绝认真回答你的问题. 不过,仔细 Google, 用正确的关键字寻找,仍可以找得到有人问过这样的问题: 像是 "用 stack 可不可以做出 linked list", 然後他得到的回答是: "要问就先检查是不是问对问题." 一般来说,人可能都用 C++ 背景知识 回答你说:哎呀,不可能做得到的啦. 不过,既然你没有说你是在思考 C++ 的东西, 你也可以把所谓 array 当作抽象结构来思考. 谁管你怎麽想,这就是学习. 不过最後回归到特定电脑语言领域中的时候,就要把现实的范围限制加上去. 我想这些是你该厘清的. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 218.160.212.40