讀者來信問 Pointer 以及 Linked List - 創意海豚的部落格

字體：小中大

讀者來信問 Pointer 以及 Linked List

2011/12/29 16:21:14瀏覽2837｜回應1｜推薦0

有位讀者來信問道：

資料出處: http://c-faq.com/~scs/cclass/int/sx8.html

你對指標有個解釋 ── 用房子的住址來比喻 (Pointers 的部分則是以現實世界中的房子點出每個 data object 都有 address )；為了更懂 pointer to pointer，我上網查了，剛好有這個網站，有看了幾天，前幾頁還都可以懂，但若搭配 data struct 就真的看不懂了；紅色這些都是透過 pointer to pointer 來轉換程式所須的記憶體位置，可否用房子的比喻來說明？感謝！(一般人遇到pointer to pointer真的都轉不出來)

struct list **lpp, *list_ptr;

for (lpp = &list_ptr; *lpp != NULL; lpp = &(*lpp)->next) {
if ((*lpp)->item == i) {
*lpp = (*lpp)->next;
break;
}
}

*lpp = (*lpp)->next;
(*lpp)->next;
lpp = &(*lpp)->next;

筆者的回答如下：

pointer variable 本身也是一個 data object ── 亦即它也是一個實體，會佔據記憶體空間，因此它也有自己的 virtual address；下列的程式碼可以幫助你釐清一些觀念：

int i, *ptr; i = 99;

ptr = &i;

printf ("address of ptr = %p, size of ptr = %u, content of ptr = %p, deference the ptr = %d\n", &ptr, sizeof(ptr), ptr, *ptr);

其中，"sizeof(ptr)" 告訴我們，pointer variable 也是一個實體 ── It's a data object，所以它會佔據記憶體空間。一般而言，32-bit machine 上的 pointer 會佔據 4-byte memory space；64-bit machine 上的 pointer 會佔據 8-byte memory space。pointer variable 的內容是某個 data object 的 address。

以房子的比喻來說，pointer variable 是一棟四坪或八坪大小的房子，它也有自己的地址，而房內所儲存的內容是某棟房子的地址。

"&ptr" 是這個 pointer variable 的 address (starting address)。

"ptr" 是這個 pointer variable 的內容，該內容是某個 integer object 的 address，在此其內容是 integer i 的 address。

"*ptr" 是取得 ptr 所指向的那個 integer object 的 content，也就是它的 value，在此其值為 99。

以你所舉的程式碼為例，當中的 struct list 為：

struct list {
int item;
struct list *next;
};
(其實把這個 struct 叫做 node 會比叫做 list 來得恰當)

我們可以將它視為具有隔間結構的房子 (亦即這個房子有兩個房間)，其中第一個房間叫做 item，其 data type 為 int；第二個房間叫做 next，其 data type 為 struct list*，是一個 pointer to struct list，它可以指向自己或他人。下列的程式碼可以幫助你釐清一些觀念：

struct list to_myself, to_other;

to_myself.next = &to_myself;
to_other.next = &to_myself;

to_myself.next = &to_myself; <--- 將 to_myself 這個 object 中的 next pointer 指向自己 (我自己也是一個 object)；

to_other.next = &to_myself; <--- 將 to_other 這個 object 中的 next pointer 指向 to_myself 這個 object；

也許這麼問可以幫助你想得更清楚：

我現在抓到的內容，或是 dereferencing the pointer (例如 "*ptr" 或 "*ptr_ptr") 所抓到的內容，它是某個 data object 的 value (通常是 primitive data type 的 value)、還是某個 data object 的 address ？

Is the content a VALUE or an ADDRESS?

不論是 pointer to object、pointer to pointer to object、抑或是 pointer to pointer to pointer to object，pointer variable 的內容就是一個 address，pointer to object、pointer to pointer to object、以及 pointer to pointer to pointer to object 的宣告只是在說明必須做一次、兩次或三次的 dereferencing 之後，才能抓到真正的 object，並且以宣告的 data type 去解釋該 object 的內容。

據此解析你所舉例的程式碼如下：

struct list **lpp, *list_ptr;

for (lpp = &list_ptr; *lpp != NULL; lpp = &(*lpp)->next) {
if ((*lpp)->item == i) {
*lpp = (*lpp)->next;
break;
}
}

*lpp = (*lpp)->next;
(*lpp)->next;
lpp = &(*lpp)->next;

list_ptr 已經指向某個 linked list 中的某個 node，通常是指向該 linked list 的第一個 node；lpp 是一個 pointer to pointer to struct list 的 pointer variable，它在 for loop 的起使點承接了 list_ptr 的 address，亦即 lpp 的內容是 list_ptr 這個 pointer variable 的 address，換個方式來說則為「lpp 是指向 list_ptr 這個 data object」，所以 *lpp 代表「指向某個 node」，而 *lpp->next 是代表「該 node 中的 next pointer」；在此請留意 operator "->" 的 precedence 是高於 operator "*" 與 operator "&"，由於 unary operator "&" 與 unary operator "*" 的 precedence 是相同的，所以得用 "(" 與 ")" 將運算的優先次序標示出來，所以該程式碼才會寫為 "lpp = &(*lpp)->next"，這行敘述代表將 *lpp 所指住的那個 node 的 next pointer 之 address 設定給 lpp。

以房子的比喻來說，就是房子裡的隔間也有它自己的地址，&(*lpp)->next 代表某棟長相如 struct list 的房子其隔間 next 的地址。更精確的比喻則是：

每一坪土地都有自己的地址；
房子的大小一定是 4 坪或 8 坪的倍數；
房子可以完全沒有隔間，也可以有數個隔間；隔間的大小也一定是 4 坪或 8 坪的倍數。
房子的地址就是該房屋起始地坪的地址；同理，隔間的地址就是該隔間的起始地坪之地址；
房子或隔間都可以儲存內容，而該內容可以是 value、也可以是 address；

不知道這樣的解釋有沒有讓你搞懂，在這裡建議你將 linked list 中的每一個 node 的 address，以及該 node 中的 next 之 address 與其 value 都列印出來，再畫個圖對照一下，應該就可以搞懂。

一般而言，我們在 traverse a linked list 的時候，不會使用 pointer to pointer to object 來做 traverse，而是使用 pointer to object；例如：

struct MyNode *head_node, *cursor;

for (cursor = head_node; NULL != cursor; cursor = cursor->next) {
......
}

會使用到 pointer to pointer to object 來 traverse a linked list 的時機，通常是 node 的結構相同，但卻需要在多個獨立的 linked list 之中作切換與 Traverse，而且每個 list 的 head node 都是透過個別的 pointer 去指住的情況；例如：

struct MyNode {
void *client_data;
struct MyNode *next;
};

struct MyNode
*head_G1_student_list, *head_G2_student_list,
*head_G3_student_list, *head_G4_student_list,
*head_G5_student_list, *head_G6_student_list,
*head_teacher_list, *head_staff_list;

void TraverseTheLinkedList(struct MyNode **lpp)
{
    for ( ; NULL != *lpp; lpp = &(*lpp)->next) {
        ......
    }
    ......
}

TraverseTheLinkedList(&head_G6_student_list);
TraverseTheLinkedList(&head_teacher_list);

其實如果有徹底地搞懂 pointer，也可以透過 call by value 與 type cast 來完成相同的事情；例如：

void TraverseTheLinkedList (long address) {
    MyNode *cursor = (MyNode *) address;

    for ( ; NULL != cursor; cursor = cursor->next) {
      ......
    }
    ......
}

TraverseTheLinkedList((long) head_G6_student_list);
TraverseTheLinkedList((long) head_staff_list);

為何透過 call by value 與 type cast 也能完成之前需要透過 pointer 才能完成的事情？這是因為：

Pointer is address；這個 address 就是 Computer Science 的科目 Operating System 裡所提到的 virtual memory 之 address (It's a virtual address)，其值不外乎是一個 32-bit 或 64-bit 的 integer；pointer 的宣告方式，let it be pointer to object、pointer to pointer to object、or pointer to pointer to pointer to object ... etc.，只是方便讓我們記住 address、幫助我們記憶如何去存取與解釋被指住的記憶體之內容，如此而已。

最後，多問問

Is the content a VALUE or an ADDRESS ?

問久了就懂了！

( 創作｜其他 )


	回應文章