非递归算法
Ⅰ 二叉树非递归算法利用哪种数据结构
二叉树非递归算法利用递归算法数据结构。二叉树遍历算法都采用的是递归算法，递归算法虽然结构简洁，但在时空开销上相对较大悄隐高，从而导致运行效率较低，并且有些程序设携物计环境不支持递归，这就启尺要求将递归算法转换成非递归算法。
Ⅱ 编写 快速排序的非递归算法
终于编写出来了，我写了两种，你看看：下面是代码：
/*非递归算法1
递归算法的开销很大，告盯所以在下编了一个非递归的，算法描述如下：
A non-recursive version of quick sort using stack:
There are 2 stacks, namely one which stores the start of
a subarray and the other which stores the end of the
subarray.
STEP 1: while the subarray contains more than one element
,i.e. from Do {
SUBSTEP 1. pivot=Partion(subarray);
SUBSTEP 2. keep track of the right half of the current
subarray i.e. push (pivot+1) into stackFrom, push (to) into stackTo
SUBSTEP 3. go on to deal with the left half of
the current subarray i.e. to=pivot-1
}
STEP 2: if(neither of the stacks is empty)
Get a new subarray to deal with from the stacks.
i.e. start=pop(stackFrom); to=pop(stackTo);
STEP 3: both stacks are empty, and array has
been sorted. The program ends.
*/*/
void UnrecQuicksort(int q[],int low,int high)
{stack s1;<br/>stacks2;<br/> s1.push(low);<br/> s2.push(high);<br/> int tl,th,p;<br/> while(!s1.empty() && !s2.empty())<br/> {tl=s1.top();th=s2.top();<br/> s1.pop();s2.pop();<br/> if(tl>=th) continue;<br/> p=partition(q,tl,th);<br/> s1.push(tl);s1.push(p+1);<br/> s2.push(p-1);s2.push(th);<br/> }
}
/*非递归算法2
要把递归算法改写成非递归算法，可引进一个栈，这个栈的大小取决于递归调用的深度，最
多不会超过n，如果每次都选较大的部分进栈，处理较短的部分，递归深度最多不超过log2n
，也就是说快速排序需要的附加存储开销为O（log2n）。
*/
void UnrecQuicksort2(int q[],int low,int high)
{int *a;<袜瞎和br/> int top=0,i,j,p;<br/> a=new int[high-low+1];<br/> if(a==NULL) return;<br/> a[top++]=low;<br/>神正 a[top++]=high;<br/> while(top>0)<br/> {i=a[--top];<br/> j=a[--top];<br/> while(j {p=partition(q,j,i);<br/> if(p-j {//先分割前部,后部进栈<br/>a[top++]=p+1;<br/> a[top++]=i;<br/> i=p-1;<br/> }
else
{//先分割后部,前部进栈
a[top++]=j;
a[top++]=p-1;
j=p+1;
}
}
}
}
/*打印输出*/
void display(int p[],int len)
{for(int i=0;i cout<}
/*测试*/
int _tmain(int argc, _TCHAR* argv[])
{int a[]={49,65,97,12,23,41,56,14};
quicksort(a,0,7);
//UnrecQuicksort(a,0,7);
//UnrecQuicksort2(a,0,7);
display(a,8);
return 0;
}
Ⅲ 程序的递归算法与非递归的区别
1、递归和非递归（用栈） 非递归（用栈），也用到栈函数了，和递归就没多大区别了! 每次递归进栈出栈，非递归（用栈）的每次调用栈函数也是进栈出栈。主要是在非递归（用栈）中，它的栈函数里比递归多了些赋值语句。。。所以效率上，非递归（用栈）比递归差。 只不过，递归越深，占用栈空间越多。非递归（用栈），占用的栈空间少。如果，递归的深度还没达到超出栈空间的程度，那么递归比非递归（用栈）好。 如果是非递归（不用栈），当然是非递归最好。 在下面的这个例子（解决“整数划分问题”）中，说明了如果只是用栈机械的模拟，得到的结果只是： 空间不变（事实上，非递归应该多一些），而非递归的时间数倍的增加。。 感兴趣的朋友运行就知道了 #include<iostream> #include<stack> #include<ctime> using namespace std; //---------------------------递归算法 int q(int n,int m) { if((n<1) || (m<0)) return 0; if((n==1) ||(m==1)) return 1; if(n<m) return q(n,n); if(n==m) return q(n,m-1)+1; return q(n,m-1)+q(n-m,m); } int q(int num) { return q(num,num); } struct Point { int n,m; Point(int _n,int _m){ n=_n; m=_m;} }; //-------------------------非递归算法 int _q(int n,int m) { int sum=0; Point tmp(n,m); stack<Point> s; s.push (tmp); while(!s.empty()) { tmp=s.top(); n=tmp.n; m=tmp.m; s.pop(); if((n<1) || (m<0)) ++sum; else if((n==1) ||(m==1)) ++sum; else if(n<m) s.push(Point(n,n)); else if(n==m) { ++sum; s.push(Point(n,m-1)); } else { s.push(Point(n,m-1)); s.push(Point(n-m,m)); } } return sum; } int _q(int num) { return _q(num,num); } int main() { int num; unsigned int p; do{ cout<<"Input a num:"; cin>>num; p=clock(); cout<<" 递归： "<<q(num)<<endl; cout<<"\t\t用时:"<<clock()-p<<endl; p=clock(); cout<<"非递归： "<<_q(num)<<endl; cout<<"\t\t用时:"<<clock()-p<<endl<<endl; }while(num); return 0; } 2. 如果非递归不是用栈做的 这里有一个网友做的汉诺塔问题的非递归解法 看了真让人汗颜 这样的规律都有人发现 下载地址是： http://wenku..com/view/cfd56b3610661ed9ad51f3f9.html 此算法不是用大家以前熟悉的递归算法 虽然没运行 可以猜想 这个程序的空间和时间效率毫无疑问会大幅度提高。 3. 总结： 直接引用《算法设计与分析（第二版）》里的一段话： 结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，而且它为设计算法，调试程序带来很大方便。 然而递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多 仅仅是机械地模拟还不能达到减少计算时间和存储空间的目的。因此，还需要根据具体程序和特点对递归调用的工作栈进行简化，尽量减少栈的操作，压缩栈存储以达到节省计算时间和存储空间的目的。
Ⅳ 非递归算法比较有哪些主要的优点和缺点
非递归算法和递归算法的主要优缺点：
非递归算法的优点：如果需要处理的数据规模比较大的时候，适合使用非递归算法。缺点：程序代码的可读性差一些。
递归算法的优点：程序代码的可读性要比非递归算法的好，如果需要处理的数据量比较小的时候，适合使用递归算法。缺点：当需要处理的数据规模比较大的时候，就不适合使用递归算法了。因为递归算法涉及到对堆栈的频繁操作（入栈、出栈），系统效率会很低，严重的时候会导致系统崩溃。
Ⅳ 二叉树的遍历非递归算法中应注意哪些问题
先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应扮谈弯为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法一，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法二，流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求厅闷在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法侍升，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右，当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}
while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 设置栈顶标记
T = GetTopPointer(S); // 取栈顶保存的指针
T = T->rchild;
}else break;
}
}
Ⅵ 后序遍历的非递归算法是什么
对于树的遍历我们最常用的三种遍历方法分别是前序遍历、中序遍历和后序遍历，使用的方法是深度优先遍历树的每一个节点，这些遍历方法都是使用递归函数来进行实现的。
在数据量大的情况下是比较低效的，原因在于系统帮助我们调用了一个栈并且做了诸如保护现场和恢复现场等复杂的操作。
才使得遍历可以使用非常简单的代码来实现，所以我们可以模仿系统中调用的栈自己可以来写一下栈，模仿其中的过程就可以完成对于三种遍历算法的实现，使用自定义的栈来代替系统栈可以得到效率上的提升，下面是对于后序遍历的非递归算法的实现。
简介
从逆后序遍历与先序遍历的关系中我们可以知道逆后序遍历序列为先序遍历交换左右子树的遍历顺序得到的。
所以我们得到了逆后序序列之后然后逆序就可以得到后序遍历的序列了，所以需要两个栈，第一个栈用来存储先序遍历交换左右子树的遍历的中介结果。
Ⅶ 递归算法与非递归算法的比较
否，一般而言非递归算法更有效；但很多时候递归算法容易实现，编程简单。
Ⅷ 二叉树中序遍历的非递归算法
推荐这篇文章，把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
Ⅸ n阶乘的非递归算法
#include <stdio.h>
int f(int n)//n的阶乘
{
int res=1;
int i;
for(i=1;i<=n;i++)
res*=i;
return res;
}
int main()
{
int n=6;
int no=f(n);
printf("%d\n",no);
return 0;
}
如上n=6;6的阶乘
Ⅹ 二叉树先序遍历递归算法和非递归算法本质区别
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}