程式扎記: [C 常見考題] Linked List Allocation Quiz

標籤

2013年3月12日 星期二

[C 常見考題] Linked List Allocation Quiz


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

Question:
首先假設你有一個 struct 結構如下:
  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 方法會如下:
  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 的其中一個寫法:
  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 改寫的代碼:
  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...


沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!