Re: [問題] 救命!完全看不懂LINK LIST

看板C_and_CPP作者EdisonX (閉上眼的魚)時間12年前 (2012/07/23 01:55)推噓12(12推 0噓 3→)

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

→

07/23 00:17,

07/23 00:17

j 大都出「好人的召喚」了，我只好簡單畫個圖。這裡前提假設 (一般書本假設) 幾個 : sizeof(int)=4, CHAR_BIT=8, sizeof(TYPE*)=4 翻白話的說 int 是 4bytes, 1 byte=8bit, 指標大小=4bytes 也不考慮 big/little endian 、padding 問題, 敘述以簡易清楚為主。 #1G2cRmDn (C_and_CPP) 這篇前六點先看完，再來接這裡會適當一點。 ※ 引述《a0916327869 (左)》之銘言： : #include<stdio.h> : #include<stdlib.h> : #include<memory.h> : int main() : { : struct rst : { : int i; : struct rst *link; : }; : struct rst node,*head,*tail,*p; 上面那篇文章 #1G2cRmDn (C_and_CPP) 前六點有看完的話，我曾引重一個重點：指標本身是存放別人的位址，而記憶體裡面的位址本身是一串數字，這裡假設這個位址是用 32bits, 也就是 4bytes 存下。所以記憶體配置圖大概如下。 ┌────┬────┬────┬────┬────┬──┬───┐ Addr│0x1200 │0x1204 │0x1208 │0x120b │0x1210 │... │0x1300│ ├────┴────┼────┼────┼────┼──┼───┤ Var1│ Node │ *head │ *tail │ *p │... │ │ ├────┬────┼────┼────┼────┼──┼───┤ Var2│int i │ *link │ │ │ │... │ │ ├────┼────┼────┼────┼────┼──┼───┤ 內容│ ? │ ? │ ? │ ? │ ? │... │ │ └────┴────┴────┴────┴────┴──┼───┤ Var1, Var2 要合在一起看才看得清楚，但有幾點注意 (1) Node 不一定剛好佔用 8 bytes (int 4bytes + 指標 4bytes)，關係到 padding 問題，只是這裡說了不考慮 padding 。 (2) Node, *head, *trail, *p, 這四個變數的記憶體位址不一定連續，但為了方便畫圖說明，所以我畫的時候是連續的。 (3) *head, *trail, *p 本身是「指向 struct rst」的指標，前提假設(也說了是一般書本的假設)說過，指標大小假設為 4bytes。 : head = (struct rst *)malloc(sizeof(node)); : tail = (struct rst *)malloc(sizeof(node)); 這裡我是比較習慣寫成 head = (struct rst *)malloc(sizeof(struct rst)); 語意上會比較好一點，還有其他更好的寫法，細節我就不講了。這段實際上是拆兩部份看的， malloc 它去向 os 要一塊大小為 struct rst 的記憶體出來，這時候 os 會找一塊較合適的記憶體給它，所以可能是這樣 malloc(sizeof(struct rst)) ┌───────────┐ 配置的空間範圍 │ 0x8000~0x8007 │ ├───────────┤ 內容值 │ (全未知) │ └───────────┘ 可能配置的空間範圍是 0x8000~0x8007(這個大小要等於 sizeof(struct rst)), 接下來有做到強制轉型的東西，此時可這麼去看 malloc 出來的記憶體 (struct rst*) malloc(sizeof(struct rst)) ┌───────────┐ 配置的空間範圍 │ 0x8000 0x8004 │ 0x8008 ├───────────┤ 變數 │ i *link │ ├───────────┤ 內容值 │ ???? ???? │ └───────────┘ 最後，malloc 有傳回值，是傳回剛剛配置好 address 的頭, (head of address , 恕中文不知怎敘述, 第一個 byte ??), 也就是 0x8000, 把這個 address value 再給 head, 一樣的， tail = (struct rst *)malloc(sizeof(node)); 也是做一樣的事情，所以整體的記憶體變如此。 head = (struct rst *)malloc(sizeof(struct rst)); tail = (struct rst *)malloc(sizeof(node)); ┌────┬────┬────┬────┬────┬──┬───┐ Addr│0x1200 │0x1204 │0x1208 │0x120b │0x1210 │... │0x1300│ ├────┴────┼────┼────┼────┼──┼───┤ Var1│ Node │ *head │ *tail │ *p │... │ │ ├────┬────┼────┼────┼────┼──┼───┤ Var2│int i │ *link │ │ │ │... │ │ ├────┼────┼────┼────┼────┼──┼───┤ 內容│ ? │ ? │ 0x8000 │ 0x9000 │ ? │... │ │ └────┴────┴────┴────┴────┴──┴───┘ ↓ └────────────┐ ┌───────────┐ │ head 配置記憶體空間 │ 0x8000 0x8004 │ 0x8008 │ ├───────────┤ │ 變數 │ i *link │ │ ├───────────┤ │ 內容值 │ ???? ???? │ │ └───────────┘ │ ┌──────────────────┘ ↓ ┌───────────┐ trail 配置配憶體空間 │ 0x9000 0x9004 │ 0x9008 ├───────────┤ 變數 │ i *link │ ├───────────┤ 內容值 │ ???? ???? │ └───────────┘ : head->i=11; : tail->i=99; head 指到的記憶體空間裡，去設定 i 為 11, tail 指到的記憶體空間裡，去設定 i 為 99 ┌────┬────┬────┬────┬────┬──┬───┐ Addr│0x1200 │0x1204 │0x1208 │0x120b │0x1210 │... │0x1300│ ├────┴────┼────┼────┼────┼──┼───┤ Var1│ Node │ *head │ *tail │ *p │... │ │ ├────┬────┼────┼────┼────┼──┼───┤ Var2│int i │ *link │ │ │ │... │ │ ├────┼────┼────┼────┼────┼──┼───┤ 內容│ ? │ ? │ 0x8000 │ 0x9000 │ ? │... │ │ └────┴────┴────┴────┴────┴──┴───┘ ↓ └────────────┐ ┌───────────┐ │ head 配置記憶體空間 │ 0x8000 0x8004 │ 0x8008 │ ├───────────┤ │ 變數 │ i *link │ │ ├───────────┤ │ 內容值 │ 11 ???? │ │ └───────────┘ │ ┌──────────────────┘ ↓ ┌───────────┐ trail 配置配憶體空間 │ 0x9000 0x9004 │ 0x9008 ├───────────┤ 變數 │ i *link │ ├───────────┤ 內容值 │ 99 ???? │ └───────────┘ : head->link = tail; 將 tail 「存的位址值」，設給「head 配置出來的 link」 ┌────┬────┬────┬────┬────┬──┬───┐ Addr│0x1200 │0x1204 │0x1208 │0x120b │0x1210 │... │0x1300│ ├────┴────┼────┼────┼────┼──┼───┤ Var1│ Node │ *head │ *tail │ *p │... │ │ ├────┬────┼────┼────┼────┼──┼───┤ Var2│int i │ *link │ │ │ │... │ │ ├────┼────┼────┼────┼────┼──┼───┤ 內容│ ? │ ? │ 0x8000 │ 0x9000 │ ? │... │ │ └────┴────┴────┴────┴────┴──┴───┘ ↓ └────────────┐ ┌───────────┐ │ head 配置記憶體空間 │ 0x8000 0x8004 │ 0x8008 │ ├───────────┤ │ 變數 │ i *link │ │ ├───────────┤ │ 內容值 │ 11 0x9000 │ │ └───────────┘ │ ┌──────────────────┘ ↓ ┌───────────┐ trail 配置配憶體空間 │ 0x9000 0x9004 │ 0x9008 ├───────────┤ 變數 │ i *link │ ├───────────┤ 內容值 │ 99 ???? │ └───────────┘ 再補個例子，如果是 head->link->i 的話會怎麼找？ ┌────┬────┬────┬────┬────┬──┬───┐ Addr│0x1200 │0x1204 │0x1208 │0x120b │0x1210 │... │0x1300│ ├────┴────┼────┼────┼────┼──┼───┤ Var1│ Node │ *head │ *tail │ *p │... │ │ ├────┬────┼────┼────┼────┼──┼───┤ Var2│int i │ *link │ │ │ │... │ │ ├────┼────┼────┼────┼────┼──┼───┤ 內容│ ? │ ? │ 0x8000 │ 0x9000 │ ? │... │ │ └────┴────┴────┴────┴────┴──┴───┘ └───┐ ↓(head->link) ┌───────────┐ head 配置記憶體空間 │ 0x8000 0x8004 │ 0x8008 ├───────────┤ 變數 │ i *link │ ├───────────┤ 內容值 │ 11 0x9000 │ └───────────┘ ┌────┘ ↓ (head->link->i) ┌───────────┐ trail 配置配憶體空間 │ 0x9000 0x9004 │ 0x9008 ├───────────┤ 變數 │ i *link │ ├───────────┤ 內容值 │ 99 ???? │ └───────────┘ 所以在合理範圍裡，你可以一直用連續技，接招接到沒招可接 : NULL 為止。 head->link->link->link->link->link->link->....->i; 圖示上粉紅色的箭頭就會一直指下去，只是這個動作通常是交由 loop 去完成，所以才有變數 tmp, 怎麼做的話再去翻書。整個記憶體概念大概就這樣，但針對 link 一般不會這麼畫，原因是這部份應該會用較清楚示意之方式，大致像這類型， http://edisonx.pixnet.net/album/photo/127028035 <　這系列實作是 head with value, 和一般的範例較不同 > 只是您的狀況是，可能沒辦法和 struct 聯想起來，故認為這篇文章之示意圖應對您有所幫助，唯用這種示意圖來學 LinkList, 是較不智的行為。 : head : free(tail); : free(head); : system("pause"); : return 0; : } 這幾行沒寫全，就不講了。 : 以上是照著書寫出的很簡單的LINK LIST 但是實在無法解讀他是怎麼做的 : 問題1 : struct rst 內又宣告了一個 struct rst *link 這代表甚麼 ORZ link 為一指標，指向 struct rst 資料型態之指標。 : 問題2 : 關於符號"->"是指向的意思嗎? : head->i=11; 這是說head 指向i i=11嗎?還是說head的i等於11 head 指向之變數(是一個 struct rst)，裡面的 i 成員，設定成 11 : 那head -> link = tail 這該如何解讀上面圖解有了，落落長，慢慢看。 : head 的 link 是 tail? : 救命阿!!有沒有比較白話的解釋 : 請高手幫忙 -- 「自從我學了 C# , 人都變聰明 , 考試都考一百分」「自從我學了 VB , 皮膚都變好 , 人也變漂亮了」「自從我學了 Java , 明顯變壯 , 個子也變高了」「自從我學了 C++ , 內分泌失調 , 頭都禿了... 」 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.161 ※ 編輯: EdisonX 來自: 180.177.76.161 (07/23 02:41)

→

uranusjr

07/23 02:52, , 1^F

07/23 02:52, 1^F

推

k387259

07/23 03:48, , 2^F

07/23 03:48, 2^F

→

handsome616

07/23 07:37, , 3^F

07/23 07:37, 3^F