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

[maerdimer (void)]

※ 引述《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)
推 fishlinghu:謝謝!!大致上是懂了!!不過操作上還滿不熟練的Q__Q
→ fishlinghu:我在書上沒看到有delete欸......
→ fishlinghu:雖然他在function裡面都會像你一樣new那個struct的型態
→ maerdimer:哪一本啊? 放火燒了它吧!
→ EdisonX:是有不少中文書有 new/malloc 沒 delete/free 就是了..
→ maerdimer:不對 那個只有single_link::in() 沒有single_link::del
→ maerdimer:應該是我錯了 原PO再翻一下後面應該會有XD
推 fishlinghu:是蔡明志那本資結 他好像真的沒打欸=口=
→ maerdimer:真的假的 single_link::del()裡真的沒有嗎   囧
→ fishlinghu:咦~有欸XD可是他那是用來刪去資料的欸
→ fishlinghu:感覺不是專門釋放空間的
※ 編輯: maerdimer       來自: 111.252.99.212       (08/12 17:39)