前幾天做題的時候，發現《數據結構高分筆記》第一章有這樣一個思考題，對理解遞歸調用幫助很大，題目如下：
題目：逆序輸出單鏈表的數據域，要求 指針l指向鏈表首元結點，且只用l一個指針（一）分析：在單鏈表的情況下，要逆序輸出結點數據只用一個指針，除了用遞歸調用，好象沒有別的方法了。關鍵在于，如何設計遞歸調用？ 遞歸調用屬于分治法的一種思想，一個包含直接或者間接調用自身函數的語句的函數被稱為遞歸函數，但不是所有的調用自身都是遞歸，必須滿足以下條件： （1）在每一次調用自身時，必須是（在某種意義上）更接近于解； （2）必須有一個終止 處理或者計算 的準則；設計的算法如下：————————————————————————————————————void reversePRint(LNode *l) //逆序輸出鏈表{if (l->next!= NULL){reversePrint(l->next);}cout << l->data<<" -- ";}———————————————————————————————————— 我們假設從首元結點到尾元結點共有9個結點，指針l指向首元結點，當執行到if語句時，很明顯” l->next!= NULL “成立，于是執行“ reversePrint(l->next); ”進入遞歸第二層，第二層循環執行到if語句后同樣” l->next!= NULL “成立，于是進入到遞歸第三層……值得說明的是“ reversePrint(l->next); ”語句中，( )中必須寫成”( l->next )“，如果寫成(l)，便會進入死循環，違背了上面條件（1）。而” l->next!= NULL “就是終止處理的準則，也就是上面的條件（2）； 當進入遞歸第九層以后，” l->next!= NULL “不成立，于是直接執行" cout << l->data<<" -- "; "輸出結點9的數據，第九層遞歸執行結束。但第九層遞歸執行結束以后，第八層遞歸if語句執行完畢，也進入" cout << l->data<<" -- "; "語句輸出結點9的數據域，第八層遞歸執行結束。以此類推，7、6、5、4、3、2、1依次執行" cout << l->data<<" -- "; "語句，于是整個鏈表就被逆序輸出，而且從頭到尾l指針所指的始終是首元結點（每一層的l可以看成每一層自己定義的指針，只不過名字相同，這點很重要）。因此，使用指針l，如果用for循環輸出則為正序，使用遞歸就可以達到逆序輸出的目的。 另外值得一提的是" cout << l->data<<" -- "; "語句的位置因該放在函數哪里，也是一個值得深思的問題。 （二）關于遞歸調用的時間復雜度問題 如上九個結點，九層循環的時間復雜度為9，也就是說這個算法時間復雜度為O(n)。初學者可能會懷疑時間復雜度為n次方，但是仔細比較就會發現，遞歸和循環的時間復雜度很類似。遞歸九層逆序輸出，時間復雜度為9；for(i=1;i<=9;i++){……}循環順序輸出9次，時間復雜度也是9。 因此，靈活的使用遞歸和循環，可以解決線性表的各種順序以及逆序問題！完整的代碼如下（VS2013編譯環境）：————————————————————————————————————// 逆序打印單鏈表的數據 指針l指向鏈表開始 要求只用l一個指針/*分析: 采用遞歸 printNode {if(l->next!=NULL)printNode(l->next);cout<<l->data;} 很神奇的想法！對理解遞歸有很大幫助！！！*/#include "stdafx.h"#include <iostream>#include "stdlib.h"using namespace std;static int length = 9;typedef struct LNode{ //結點的定義int data;struct LNode *next;}LNode;LNode *createLink( )//創立鏈表 {//創立頭結點LNode *head;head = (LNode *)malloc(sizeof(LNode));head->data = 0; head->next = NULL;//創立剩下的結點LNode *newNode, *p = head;for (int i = 1; i <= length; i++) {newNode = (LNode *)malloc(sizeof(LNode));newNode->data = i; newNode->next = NULL;p->next = newNode;p = p->next;}return head;}void printLink(LNode *head)//輸出鏈表 {cout << "當前鏈表為：";LNode *temp = head->next;do{cout << temp->data << " -- ";temp = temp->next;} while (temp->next!=NULL);cout << temp->data;cout << endl;}void reversePrint(LNode *l) //逆序輸出鏈表{if (l->next!= NULL){reversePrint(l->next);}cout << l->data<<" -- ";}int _tmain(int argc, _TCHAR* argv[]){LNode *head = createLink();printLink(head);cout << "逆序鏈表為：";reversePrint(head->next); cout << endl;return 0;}————————————————————————————————————輸出結果如下：
新聞熱點
疑難解答
