[C 常見考題] Linked List Allocation Quiz

Preface:
基本上 C 的 Pointer 常常會讓程式員頭痛不已 (debug 到天荒地老, 昏天暗地...), 因此它也成為常見的考題. 底下會以 Linked List 當作背景, 然後使用 Pointer 的 Pointer 進行 Linked List 的 Allocation. 聽起來饒舌, 解釋起來更饒舌... Orz.

Question:
首先假設你有一個 struct 結構如下:

view plaincopy to clipboardprint?

1. struct LinkedList{  
2.     int data;  
3.     struct LinkedList *next;  
4. };  
5.   
6. typedef struct LinkedList L;  
7. typedef struct LinkedList *PL;  
8. typedef struct LinkedList **PPL;  

常見的 Linked List 的 Allocation 方法會如下:

view plaincopy to clipboardprint?

1. PL createLL()  
2. {  
3.     printf("\t[Info] Create LinkedList...\n");  
4.     PL head = NULL, rear = NULL;  
5.     int i;  
6.     for(i=0; i<6; i++)  
7.     {  
8.         PL newNode = malloc(sizeof(L));  
9.         if(newNode==NULL)  
10.         {  
11.             printf("\t[Info] Memory error!\n");  
12.             return NULL;  
13.         }  
14.         newNode->data = i;  
15.         newNode->next = NULL;  
16.         if(rear == NULL)  
17.         {  
18.             head = rear = newNode;  
19.         }  
20.         else  
21.         {  
22.             rear->next = newNode;  
23.             rear = newNode;  
24.         }  
25.     }  
26.     return head;  
27. }  

上面代碼會建立下面的 Linked List:


接著問題來了, 題目要求你使用 Pointer 的 Pointer (PPL) 改寫 Linked List 的 Allocation.

Possible Sol:
底下是使用 PPL 改寫上面 Linked List 的 Allocation 的其中一個寫法:

view plaincopy to clipboardprint?

1. PL createLL2()  
2. {  
3.     PL head = NULL;  
4.     printf("\t[Info] Create LinkedList...\n");  
5.     PPL lastref = &head;  
6.     int i;  
7.     for(i=0; i<6; i++)  
8.     {  
9.         *lastref = malloc(sizeof(L));  
10.         (*lastref)->data = i;  
11.         (*lastref)->next = NULL;  
12.         lastref = &((*lastref)->next);      
13.     }  
14.   
15.     return head;  
16. }  

接著我們要一行行來解釋上述代碼的運作.
1. 使用 PPL 指向 head 的記憶體位置:


2. Memory allocation for struct LinkedList:


3. 移到 Linked List 當前 node 的下一個位置上 (方便下一個 loop 的 allocation)


4. 繼續 steps 2~3 直到 for loop 結束. (所以下一次為變數 *lastref 分配記憶體位置會指定到 變數 next 上面去!)

Complete Code Ref:
由上面的問題可以看出使用 PPL 的代碼簡潔多, 但是容易寫錯 :p (寫起來漂亮;維護起來痛苦?). 底下為完整代碼, 其中函數 createLL() 是舊有的 Linked List allocation; 而函數 createLL2() 則是使用 Pointer 的 Pointer 改寫的代碼:

view plaincopy to clipboardprint?

1. #include   
2. #include   
3.   
4. struct LinkedList{  
5.     int data;  
6.     struct LinkedList *next;  
7. };  
8.   
9. typedef struct LinkedList L;  
10. typedef struct LinkedList *PL;  
11. typedef struct LinkedList **PPL;  
12.   
13. PL createLL()  
14. {  
15.     printf("\t[Info] Create LinkedList...\n");  
16.     PL head = NULL, rear = NULL;  
17.     int i;  
18.     for(i=0; i<6; i++)  
19.     {  
20.         PL temp = malloc(sizeof(L));  
21.         if(temp==NULL)  
22.         {  
23.             printf("\t[Info] Memory error!\n");  
24.             return NULL;  
25.         }  
26.         temp->data = i;  
27.         temp->next = NULL;  
28.         if(rear == NULL)   
29.         {  
30.             head = rear = temp;  
31.         }  
32.         else   
33.         {  
34.             rear->next = temp;  
35.             rear = temp;  
36.         }  
37.     }      
38.     return head;  
39. }  
40.   
41. PL createLL2()  
42. {  
43.     PL head = NULL;  
44.     printf("\t[Info] Create LinkedList...\n");  
45.     PPL lastref = &head;  
46.     int i;  
47.     for(i=0; i<6; i++)  
48.     {  
49.         *lastref = malloc(sizeof(L));  
50.         (*lastref)->data = i;  
51.         (*lastref)->next = NULL;  
52.         lastref = &((*lastref)->next);      
53.     }  
54.     //printf("\t[Test] head->data=%d\n", head->data);  
55.     return head;  
56. }  
57.   
58. void showLinkedList(PL head)  
59. {  
60.     printf("\t[Info] Show LinkedList...\n");  
61.     PL temp = head;  
62.     while(temp!=NULL)  
63.     {  
64.         printf("%d ", temp->data);  
65.         temp = temp->next;  
66.     }  
67.     printf("\n");  
68. }  
69.   
70. void delLinkedList(PL head)  
71. {  
72.     printf("\t[Info] Free LinkedList...\n");  
73.     PL temp=head;  
74.     while(temp!=NULL)  
75.     {  
76.         temp = head->next;  
77.         free(head);  
78.         head = temp;  
79.     }  
80. }  
81.   
82. int main()  
83. {  
84.     PL head=NULL;  
85.     head = createLL2();  
86.     if(head == NULL)  
87.     {  
88.         printf("\t[Error] Fail!\n");  
89.         return 0;  
90.     }  
91.     showLinkedList(head);  
92.     delLinkedList(head);  
93.     return 0;  
94. }  

執行結果如下:

[Info] Create LinkedList...
[Info] Show LinkedList...
0 1 2 3 4 5
[Info] Free LinkedList...