Re: [問題] linkedlist 一個比較較不常見的問題

[EdisonX (閉上眼的魚)]

※ 引述《Dreamer77 (追夢)》之銘言：
: 其實我不懂 為什麼這樣的問題不能問 得要被版主刪掉？
: 是說這個版只能問語法嗎？

其實也不是這樣說，只是這問題可議性很大，一些髒髒的手法都有，
不是說一定要單純從 RunTime 那裡取得，
甚至可以在 pre-processor 那裡加點東西進去，
可能面試真的只有這樣的敘述，但似乎還是看 code 最清楚吧？

: 硬是要我先寫出code來的話 那就只能這樣寫 不過沒有比原文多初什麼info就是
: struct nodeTp{
:    int value;
:    struct nodeTp *next;
: };
: struct nodeTp *A, *B, *C;
: A->next = B;
: B->next = C;
: findPrvNode(B);
: struct nodeTp* findPrvNode(struct nodeTp *in)
: {
: // 該怎麼return previous node of in
: }

我不是要挑你有毛病的地方，但如果這真的是面試題目的話，
這題你也可以不用想了，實質上 A->next  B->next   C->next 都是非法存取。

: ※ 引述《Dreamer77 (追夢)》之銘言：
: 給定一個linkedlist
: 以及一個指標  這個指標指向這linkedlist 內部的某node（非head）
: 該怎麼找到這個node的前一個node呢？
: 非double linkedlist 是一個單向的
: 想不到有什麼方法...

這篇我覺得很可惜一點是，雖然是面試題目，
但原本推文裡之討論可引出更多知識與討論，
最後因不合題意要求 ( 其實我還沒完全抓到，最後的限制到底有哪些 ) 而作罷，
像 purpose 與 loveme00835 提的東西都是讓我很想知道的。

這裡我可以直接給一個「特例」 (可以丟雞蛋沒關係)

http://codepad.org/eZ35qFDp

        struct link* prev_node(struct link* node)
        {
                return node - 1;
        }

        struct link *bprev ;
        struct link arr[] = {
                {&arr[1], 1},
                {&arr[2], 2},
                {NULL,3}
        };
        travel(arr);
        bprev = prev_node(arr+1);

當然這是一組特例，但一些早期教科書上，或其他論壇裡，
是會拿 array-like link list 當 sample (當然不會用這麼爛的例子)

如果是 C language spec. 有用到 malloc 的話，
有很髒的手法可以達成，但重點就是不知道「前端」( new node 怎來的 )
是怎來的？
有興趣的話，可 google dbg_malloc，裡面的技巧可以拿來用，
最後的 single link list 是開放給 coder 看的，
實質上變成 "近似" double link list (要 polling 已 allocate 之 address)。

沒回答到問題的話只能說聲報歉，問題解讀能力沒很好。

--
 「自從我學了 C#   , 人都變聰明 , 考試都考一百分」
 「自從我學了 VB   , 皮膚都變好 , 人也變漂亮了  」
 「自從我學了 Java , 明顯變壯   , 個子也變高了  」
 「自從我學了 C++  , 內分泌失調 , 頭都禿了...   」

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.168.79.203
※ 編輯: EdisonX         來自: 118.168.79.203       (04/22 02:21)
推 james732:簽名檔XD
→ diabloevagto:A->next 為什麼是非法存取？？
→ EdisonX:沒事先 allocate 一塊 memory 出來.更壞的是,struct成員
→ EdisonX:順序,即使硬用,抓到的是 value,而非 next.
→ diabloevagto:感謝，但是->next怎麼會抓到value？
→ diabloevagto:我記得以前有看過說struct宣告順序滿重要的，但不甚
→ diabloevagto:了解，不知道用class會不會有這個影響
→ EdisonX:class 在建構初始列時會有影響。初始順序是宣告順序,非撰
→ EdisonX:寫初始列時之順序。另上面的"更壞"就別想了,一時想錯。
→ diabloevagto:另外請教，->next怎麼會抓到value?
→ EdisonX:一時想錯, 那句就去掉, 用 A->next,A->value 都是非法的。
→ diabloevagto:非法的原因是因為沒有allocate?如果有的話就合法嗎？
→ EdisonX:yes.或許你可自己實作一次,會較清楚問題在哪。
→ leiyan:看了這code我疑惑了一下 struct也有overload嗎
→ diabloevagto:http://ideone.com/2H6rS 這樣正常能用
→ diabloevagto:我把malloc跟free拿掉，一樣會印出2，但我想不能這樣
→ diabloevagto:這就是E大說的非法存取嗎？
推 damody:非法就是指hook malloc函數去把所有的記憶體掃過一遍
→ damody:不然以原原po的題意，直接說無解不是比較快？
→ EdisonX:@diabloevagto: 拿掉是非法無誤。
推 iamstudent:簽名檔好讚 XD