Re: [問題] linked list& array

看板Programming作者yauhh (喲)時間13年前 (2011/02/25 01:12)推噓1(1推 0噓 15→)

留言16則, 4人參與討論串2/9 (看更多)

※ 引述《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

→

loveme00835

02/25 13:14, , 1^F

02/25 13:14, 1^F

→

loveme00835

02/25 13:35, , 2^F

02/25 13:35, 2^F

→

loveme00835

02/25 13:36, , 3^F

02/25 13:36, 3^F