cc非递归算法
❶ 求C语言快排非递归算法解析。非递归。。
//快排非递归算法
void merge(int a[], int low, int center, int high){//这里的merge与教科书上有不同。我们用两个数组L[],R[]来存储a[]需要合并的两段
int i = 0;
int j = 0;
int k = 0;
int count = 0;
if(low >= high) return;
int m = center - low + 1;
int n = high - center;
int *L = (int *)malloc(sizeof(int)*SCALE);
int *R = (int *)malloc(sizeof(int)*SCALE);
if(!L || !R){
printf("归并排序merge（）内存分配故障！");
exit(0);
}
for( count=0; count<=m; count++){
L[count] = a[low+count];
}
for( int count=0; count<=n; count++){
R[count] = a[low+count+m];
}
for(i=0,j=0,k=low; i<m&&j<n; ++k){
if( L[i] <= R[j] ){
a[k] = L[i++];
}
else{
a[k] = R[j++];
}
}
while(i < m){
a[k++] = L[i++];
}
while(j < n){
a[k++] = R[j++];
}
free(L);
free(R);
}
❷ 程序的递归算法与非递归的区别
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. 总结： 直接引用《算法设计与分析（第二版）》里的一段话： 结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，而且它为设计算法，调试程序带来很大方便。 然而递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多 仅仅是机械地模拟还不能达到减少计算时间和存储空间的目的。因此，还需要根据具体程序和特点对递归调用的工作栈进行简化，尽量减少栈的操作，压缩栈存储以达到节省计算时间和存储空间的目的。
❸ 程序的递归算法与非递归有什么区别
递归算法是一种直接或者间接地调用自身的算法。
在计算机编写程序中，递归算法对解决一大类问题是十分有效的，它往往使算法的描述简洁而且易于理解。
递归就是在过程或函数里调用自身。
在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出。
❹ 二叉树中序遍历的非递归算法
推荐这篇文章，把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html
❺ c++关于递归与非递归
调用函数是要付出一定开销的，比如上下文的保存与恢复，会不断有堆栈操作。所以会慢。。
递归就是不断地调用函数，只不过调用的是自己。
一般来讲，同一个算法的非递归程序一定不慢于递归程序。
适用环境嘛……这个不能明确划分。。。不如这样说吧~
能不用递归的时候都不用递归，也就是有非递归算法的时候尽量避免递归。
什么时候用递归呢？我想有这样几个吧~
1.算法有比较简单的逻辑，比如阶乘，再比如遍历树
2.不用递归就解不开的问题（这个解不开是指要花费不少多余的力气才能解开）
3.你不想让别人看懂你写的程序
4.你想炫耀你高超的编程技术
❻ 二叉树非递归遍历的算法
以下为先序，中序，后序三种递归算法
#include
#define MAX 30
typedef struct TreeNode
{
char a;
TreeNode *left;
TreeNode *right;
}TreeNode,*BinTree;
typedef struct
{
TreeNode* data[MAX];
int top;
}SeqStack;
void InitStack(SeqStack &S)
{
S.top=0;
}
int StackEmpty(SeqStack S)
{
if(S.top==0)
return 1;
else return 0;
}
int StackFull(SeqStack S)
{
if(S.top==MAX) return 1;
else return 0;
}
void Push(SeqStack &S,TreeNode *node)
{
if(!StackFull(S))
{
S.data[S.top]=node;
S.top++;
}
else cout<<"Stack is full!\n";
}
void Pop(SeqStack &S,TreeNode* &e)
{
if(!StackEmpty(S))
{
S.top--;
e=S.data[S.top];
}
else cout<<"Stack is empty!";
}
TreeNode* GetTop(SeqStack S)
{
if(!StackEmpty(S))
{
TreeNode *node;
node=S.data[S.top-1];
return node;
}
else cout<<"Stack is empty!";
}
void CreateBinTree(BinTree &T)
{
char b;
cin>>b;
if(b=='0')T=NULL;
else
{
T=new TreeNode;
T->a=b;
CreateBinTree(T->left);
CreateBinTree(T->right);
}
}
void Inorder(BinTree T)
{
TreeNode * p;
SeqStack S;
p=T;
InitStack(S);
while(!StackEmpty(S)||p)
{
while(p)
{
Push(S,p);
p=p->left;
}
if(!StackEmpty(S))
{
Pop(S,p);
cout cout<<"\nA----------二叉树的建立\n";
cout<<"\nB----------非递归先序遍历\n";
cout<<"\nC----------非递归中序遍历\n";
cout<<"\nD----------非递归后序遍历\n";
cout<<"\nX----------退出\n";
}
void main()
{
BinTree T;
char ch='\0';
bool flag=true;
while(flag)
{
info();
cin>>ch;
switch(ch)
{
case'a':
case'A':
cout<<"请按先序次序输入结点，空结点用'0'表示:\n";
CreateBinTree(T);
cout<<"二叉树建立成功!\n";
break;
case'b':
case'B':
cout<<"先序遍历的结果为:\n";
Preorder(T);
break;
case'c':
case'C':
cout<<"中序遍历的结果为:\n";
Inorder(T);
break;
case'd':
case'D':
cout<<"后序遍历的结果为:\n";
Postorder(T);
break;
case'x':
case'X':
flag=false;
break;
default:
cout<<"输入无效,请重新输入!\n";
}
}
}
❼ 非递归算法比较有哪些主要的优点和缺点
非递归算法和递归算法的主要优缺点：
非递归算法的优点：如果需要处理的数据规模比较大的时候，适合使用非递归算法。缺点：程序代码的可读性差一些。
递归算法的优点：程序代码的可读性要比非递归算法的好，如果需要处理的数据量比较小的时候，适合使用递归算法。缺点：当需要处理的数据规模比较大的时候，就不适合使用递归算法了。因为递归算法涉及到对堆栈的频繁操作（入栈、出栈），系统效率会很低，严重的时候会导致系统崩溃。
❽ 关于树的非递归算法
package com.lip.datastructure.tree;
import java.util.Stack;
/**
* @author lip
*/
public class Tree
{
public static void main(String[] args)
{
Node<Integer>root=getNode();
System.out.println("前序遍历（非递归）");
preOrder(root);
System.out.println("前序遍历（递归）");
preOrderRecursive(root);
System.out.println();
System.out.println("中序遍历（非递归）");
infixOrder(root);
System.out.println("中序遍历（递归）");
infixOrderRecursive(root);
System.out.println();
System.out.println("后序遍历（非递归）");
postOrder(root);
System.out.println("后序遍历（递归）");
postOrderRecursive(root);
}
public static Node getNode()
{
Node<Integer>node1=new Node(1);
Node<Integer>node2=new Node(2);
Node<Integer>node3=new Node(3);
node1.left=node2;
node1.right=node3;
Node<Integer>node4=new Node(4);
Node<Integer>node5=new Node(5);
node2.left=node4;
node2.right=node5;
Node<Integer>node6=new Node(6);
Node<Integer>node7=new Node(7);
node3.left=node6;
node3.right=node7;
Node<Integer>node8=new Node(8);
Node<Integer>node9=new Node(9);
node4.left=node8;
node4.right=node9;
return node1;
}
//前序遍历，非递归
@SuppressWarnings("rawtypes")
public static void preOrder(Node root)
{
Stack<Node>stack=new Stack<Node>();
stack.push(root);
while(stack.size()>0)
{
Node tempNode=stack.pop();
if(tempNode!=null)
{
System.out.print(tempNode.data);
stack.push(tempNode.right);
stack.push(tempNode.left);
}
}
System.out.println();
}
//前序遍历(根左右)，递归
public static void preOrderRecursive(Node root)
{
if(root!=null)
{
System.out.print(root.data);
preOrderRecursive(root.left);
preOrderRecursive(root.right);
}
}
//中序遍历（左根右），非递归
public static void infixOrder(Node root)
{
Stack<Node>stack=new Stack<Node>();
stack.push(root);
while(stack.size()>0)
{
Node temp=stack.pop();
if(temp!=null)
{
if((temp.left==null)&&(temp.right==null))
System.out.print(temp.data);
else
{
stack.push(temp.right);
stack.push(new Node(temp.data));
stack.push(temp.left);
}
}
}
System.out.println();
}
//中序遍历（左根右），递归
public static void infixOrderRecursive(Node root)
{
if(root!=null)
{
infixOrderRecursive(root.left);
System.out.print(root.data);
infixOrderRecursive(root.right);
}
}
//后序遍历（左右根），非递归
public static void postOrder(Node root)
{
Stack<Node>stack=new Stack<Node>();
stack.push(root);
Node temp;
while(stack.size()>0)
{
temp=stack.pop();
if(temp!=null)
{
if(temp.left==null&&temp.right==null)
System.out.print(temp.data);
else {
stack.push(new Node(temp.data));
stack.push(temp.right);
stack.push(temp.left);
}
}
}
System.out.println();
}
//后序遍历（左右根），递归
public static void postOrderRecursive(Node root)
{
if(root!=null)
{
postOrderRecursive(root.left);
postOrderRecursive(root.right);
System.out.print(root.data);
}
}
}
class Node <T>
{
public Node left;
public Node right;
public T data;
public Node(T data)
{
this.data=data;
}
}
❾ 求Java List 递归算法..
无需JAVA递归取！
从设计角度看，表结构设计已经有问题了！
即使是树状结构，为何表结构没有体现？这也构成了为何楼主需要想办法来应对非树状结构数据的树状显示问题。
先进一步来说，表加一个grade字段，来表明当前记录处于第几级。那么直接一个SQL就可以取出来：
select lpad(' ',a.grade,'-')||a.name from myList a
这样就可以按楼主需要的结构取出数据；
但还存在一个问题，就是顺序问题，这样取出的数据是无序的！
那么我们再进一步看，我在做这种数据结构的表设计时，往往会给每个结点增加两个字段，left/right，分别代表其在树中的左右值。
这样就可以在上面SQL后增加order by a.left以保证取出数据的顺序。
❿ 二叉树后序遍历非递归算法
#include
<stdio.h>
#include
<stdlib.h>
struct
tree
{
char
data;
struct
tree
*lchild;
struct
tree
*rchild;
};
typedef
struct
tree
*
treptr;
treptr
build(treptr
t)//先序建树
{
char
c;
c=getchar();
if(c=='#')
{
t=NULL;
}
else
{
t=(treptr)malloc(sizeof(struct
tree));
t->data=c;
t->lchild=build(t->lchild);
t->rchild=build(t->rchild);
}
return
t;
}
void
postdorder(treptr
root)//这是递归实现
{
if
(root!=NULL)
{
postdorder(root->lchild);
postdorder(root->rchild);
printf("%c",root->data);
}
}
struct
stack
{
treptr
*top,*base;
};
typedef
struct
stack
*stackptr;
void
init
(stackptr
s)//初始化栈
{
s->base=(treptr*)malloc(sizeof(treptr)*100);
s->top=s->base;
}
void
push(stackptr
s,treptr
t)//入栈
{
*(s->top++)=t;
}
treptr
pop(stackptr
s)//弹出栈顶元素
{
treptr
t;
t=*(--(s->top));
return
t;
}
treptr
gettop(stackptr
s)//取栈顶元素
{
treptr
*l=s->top-1;
return
*(l);
}
void
postorder(treptr
t)//这是非递归后序实现
{
stackptr
s=(stackptr)malloc(sizeof(struct
stack));
treptr
temp=t;
treptr
p;
treptr
lastvist=NULL;
init(s);
p=t;
while(p||s->top!=s->base)
{
while(p)
{
push(s,p);
p=p->lchild;
}
temp=gettop(s);
if(temp->rchild==NULL||temp->rchild==lastvist)
{
putchar(temp->data);
lastvist=pop(s);
}
else
p=temp->rchild;
}
}
int
main()
{
treptr
t=NULL;
t=build(t);
postdorder(t);
printf("非递归后序遍历\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以运行。
我空间中有中序遍历的非递归实现。
不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。
输入
234##5#6##7##回车
就可以看到结果。
中序遍历及其对应树可以参考我空间中的文章
http://hi..com/huifeng00/blog/item/2ca470f56694f62e730eec39.html