遞歸函數如何在堆棧概念的鏈接列表中工作？

Question

在這裏我給出了一個代碼來打印鏈接列表的反轉。

fun1（）以相反的方式打印給定的鏈接列表。對於鏈接列表1-> 2-> 3-> 4-> 5，fun1（）打印5-> 4-> 3-> 2-> 1。

void fun1(struct node* head) 
{ 
    if(head == NULL) 
    return; 

    fun1(head->next); 
    printf("%d ", head->data); 
} 

任何人都可以解釋如何在每次調用fun1（）時構建棧幀嗎？我期待鏈接列表的最後一個節點將被打印。但我正在以相反的順序獲取鏈接列表。它沒有使鏈表反向。它只是反向打印。我認爲這是由於像Push/Pop這樣的堆棧操作。但我不完全清楚。請在圖表中逐步操作的幫助下幫助我理解。

Answer 1

我不太確定你想要達到的目標。你的代碼完全打印出它應該做的事情。以下是符合您的期望的代碼段：

我期望鏈接列表的最後一個節點將被打印。

void fun1(struct node* head) 
{ 
    if(head == NULL) 
    return; 
    if(head->next == NULL) 
    { 
    printf("%d ", head->data); 
    return; 
    } 
    else 
    fun1(head->next); 
} 

Answer 2

如果提供列表1-> 2到它：

1. 頭= 1-> 2，頭不爲空，復發與2（5續）
2. => head = 2，head不爲null，null爲null（繼續4）
3. => => head = null，head爲null，返回
4. => print head-> data「2」並返回
5. 打印頭數據 「1」，並返回

如果你移動你的print語句重複發生之前：

void fun1(struct node* head) 
{ 
    if(head == NULL) 
    return; 

    printf("%d ", head->data); 
    fun1(head->next); 
} 

這將是這樣的：

1. 頭= 1-> 2，頭不爲空，打印頭 - >數據「1」，重複2（5上繼續）
2. => head = 2，頭不爲空，打印頭 - >數據「2」重複發生null（繼續4）
3. => =>頭= NULL，頭部爲空時，返回
4. =>返回
5. 返回

在這兩種情況下的所有非空的節點被打印。只能獲得印刷他們中的一個，你的代碼必須從其他區分開來，像這樣：

void print_last(struct node* n) 
{ 
    if(n == NULL) 
    { 
     printf("empty list!"); 
    }   
    else if(n->next == NULL) 
    { 
     printf("%d", n->data); 
    } 
    else 
    { 
     print_last(n->next); 
    } 
} 

與同一列表1-> 2叫你;

1. N = 1-> 2，N！= null，並且正>下！= NULL，復發與2（3續）
2. => n = 2時，正！= NULL且n = = null。打印N->數據「2」，並返回
3. 回報

請注意，當最後一個元素髮現所以唯一的辦法，n是空的，如果你嘗試打印一個空鏈表（NULL）不遞歸。