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