前几天做题的时候，发现《数据结构高分笔记》第一章有这样一个思考题，对理解递归调用帮助很大，题目如下：
题目：逆序输出单链表的数据域，要求 指针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;}————————————————————————————————————输出结果如下：
新闻热点
疑难解答
