Re: [問題] 資料結構裡的單向鏈結是如何儲存資料的

看板C_and_CPP (C/C++)作者maerdimer (void)時間13年前 (2012/08/11 16:15)推噓2(2推 0噓 9→)

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

※ 引述《fishlinghu (令狐瑜)》之銘言： : 暑假在家自學Data Structure : 算是新手中的新手 : 用的語言是C++ 建議先去翻計算機概論的書，如果沒有修過的話 : 對於單向鏈結這部分一直有個疑問 : 就是輸進去的資料在電腦裡是如何儲存的? : 像是array在存資料的時候 : 每筆資料是一個接著一個的儲存 : 然後每筆資料都有一個相對應的位址而且是有規律的在記憶體裡也不是只有 array 有位址，所有宣告出來的變數都有位址 int x; // 宣告一個變數，有一個相對應的記憶體位址和數值 int array[10]; // 宣告一個陣列，裡面有十個變數，每個陣列的元素裡都有一個相對應的位址和數值，這些元素位址是連續的譬如 array[0] 的下一個元素就是 array[1] 在記憶體裡就是 array[0] 往後移動 4 byte ( sizeof(int) ) 就可以找到 array[1] int *p; // 宣告一個指標變數，也有一個相對應的位址和數值 : 但我就不太清楚用單向鏈結這個方式儲存資料時 : 資料是存在哪裡?又是用什麼方式(規則)被儲存的? : 他們也像array裡的資料每個都佔有一個個別的位址嗎? 我想你的問題可能是不懂 structure structure 就只是把一堆宣告變數包起來而已例如 sturct point { int x; int y; } 所以在宣告的時候 struct point p1; 在記憶體裡面分別會有兩個型別為 int 的資料，一個是 p1.x ，一個是 p2.x 這兩個當然也都各別有相對應的記憶體位址阿但是由於是用 struct 宣告，所以 x 和 y 的記憶體位址是相連的，想像 int x; 和 int y; 是被 structure 包起來的例如宣告 struct point 的陣列 struct point p[10]; 在記憶體裡就會像這樣 ┌───┐ p[0]│int x │ │int y │ ├───┤ p[1]│int x │ │int y │ ├───┤ p[2]│int x │ │int y │ ├───┤ . . . (這裡請詳閱課本 structure 的部份) : 目前我對單向鏈結的理解 : 就是它是利用 [資料 | 指向下一個位置的指標] 這樣的格式來做排序或插入資料等處理 : 不過每筆資料沒辦法讓我以位址的對應關係來聯想我就會覺得怪怪的...... 以下略，我寫個最簡單的 linked list typedef struct Node { int data; struct node *next; } Node_t; 宣告一個 Node_t structure ，在記憶體裡就會長這樣 Node_t node; ┌──────┐ │int data │ │Node_t *next│ └──────┘ 宣告一個 Node_t 的指標的話，就和上面的 structure member: Node_t *next 一樣 Node_t *head; ┌──────┐ │Node_t *head│ └──────┘ head = new struct Node; // 透過系統呼叫，在不知道什麼地方出現一塊記憶體空間 // 大小就是 struct Node ，也就是 sizeof(struct Node) // head 是個指標，指著這塊空間 ┌──────┐ ┌──────┐ │Node_t *head┼→│int data │ └──────┘ │Node_t *next│ └──────┘ 然後經過一次次 new 的操作以後，linked list 就會長這樣 ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │Node_t *head┼→│int data │ │int data │ │int data │ └──────┘ │Node_t *next┼→│Node_t *next┼→│Node_t *next│... └──────┘ └──────┘ └──────┘ 對照一下上面陣列的樣子這樣畫的意思就是 linked list 的空間是不連續的，因為每次 new 的時候都是透過系統呼叫，在不知道什麼地方突然出現一塊空間，所以每個 structure 裡才需要一個指標 next 指到下一個元素最後，因為你透過系統呼叫借來的記憶體空間，程式結束以後不會自己幫你把記憶體還給系統所以每次 new 完一塊空間，程式結束以後要記得 delete 這塊空間不然會造成 memory leak (你的程式碼是照書上寫的，書上沒有 delete 嗎？) 以上，有誤請指正，謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 111.252.68.38 ※ 編輯: maerdimer 來自: 111.252.68.38 (08/11 16:16)