快速排序--C语言非递归实现
struct node
void fun(int min,int max,int a[])
&int key = a[min];
&&& struct node
Stack[100];
&&& int top =
Stack[top].min =
Stack[top].max =
&while(top&-1)
max记录当前处理的这个区间的左极限和有极限
&&& i = min =
Stack[top].
&&& j = max =
Stack[top].
&&& top--;
while(i&j)
while((i&j) && (key
&&&&&&&&&&temp
= a[i];a[i] = a[j];a[j] =
&&&&&&&&&&i++;
while((i&j) && (key
temp = a[i];a[i] = a[j];a[j] =&
}//处理一次& 即将比绑定值小的全部放左边&
比绑定值大的放右边
&&& if(min
Stack[top].min =
Stack[top].max = i-1;
if(max&i+1)
Stack[top].min = i+1;
Stack[top].max =
&int a[10] = {49,38,65,97,76,13,27,9,2,1};
&for(i=0;i&10;i++)
&&printf("
%d&& ",a[i]);
&printf("\n");
&& fun(0,9,a);
&for(i=0;i&10;i++)
&&printf("
%d&& ",a[i]);
&printf("\n");
&return 0;
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。关于阿克曼函数的非递归算法 满意加300 C语言高手求解 在线等_百度知道
关于阿克曼函数的非递归算法 满意加300 C语言高手求解 在线等
先看一下标准阿克曼函数的实现akm(m,n)=n+1;(m=0时)akm(m-1,1);(n=0时)akm(m-1,akm(m,n-1));（m!=0且n!=0时)intakm_nonrecursive(intm,intn){intm1[50],n1[50],cp=0;m1[0]=m;n1[0]...
先看一下标准阿克曼函数的实现 akm(m, n) = n + 1;
akm(m - 1, 1);
akm(m - 1, akm(m, n - 1)); （m != 0且n != 0时)int akm_nonrecursive(int m, int n) {
int m1[50], n1[50],
while (m1[cp] &; 0) {
/* 压栈, 直到m1[cp] = 0 */
while (n1[cp] &; 0) {
/* 压栈, 直到n1[cp] = 0 */
m1[cp] = m1[cp - 1];
n1[cp] = n1[cp - 1] - 1;
/* 计算akm(m - 1, 1),当n = 0时 */
m1[cp] = m1[cp] - 1;
n1[cp] = 1;
/* 改栈顶为akm(m - 1, n + 1),当m = 0时 */
m1[cp] = m1[cp] - 1;
n1[cp] = n1[cp + 1] + 1;
} while (cp &; 0 || m1[cp] &; 0);
return n1[0] + 1; }现在将阿克曼函数变化一下补充为————注意看：将阿克曼函数稍稍变化：akm2(n,x,y)= x+1; (n=0) x; (n=1,y=0) 0; (n=2,y=0) 1; (n=3,y=0) 2; (n&3,y=0) akm2(n-1,akm2(n,x,y-1),x) (n!=0,y!=0)模拟上面问题中的算法 将新的函数的程序实现代码写出来 同样利用二叉树！！！！！！！！！！！！！！！！！！！！+300分
答题抽奖
首次认真答题后
即可获得3次抽奖机会，100%中奖。
采纳数：1596
获赞数：8926
楼主如果要加300分，可能要开2贴了，因为1贴最多只能200分，追加最多只能50分。你给的那个解法，写的本来就有问题。不信，你自己试试这个程序：#include&stdio.h&//非递归解法int akm_nonrecursive(int m, int n) { int m1[50], n1[50], cp = 0; m1[0] = n1[0] = do { while (m1[cp] & 0) { /* 压栈, 直到m1[cp] = 0 */ while (n1[cp] & 0) { /* 压栈, 直到n1[cp] = 0 */ cp++; m1[cp] = m1[cp - 1]; n1[cp] = n1[cp - 1] - 1; } /* 计算akm(m - 1, 1),当n = 0时 */ m1[cp] = m1[cp] - 1; n1[cp] = 1; } /* 改栈顶为akm(m - 1, n + 1),当m = 0时 */ cp--; m1[cp] = m1[cp] - 1; n1[cp] = n1[cp + 1] + 1; } while (cp & 0 || m1[cp] & 0); return n1[0] + 1; } int main(){printf(&%d\n&,akm_nonrecursive(0,2));printf(&%d\n&,akm_nonrecursive(2,0));printf(&%d\n&,akm_nonrecursive(2,3));return 0;}
采纳数：31
获赞数：63
int f(int n,int x,int y) { int n1[100],x1[100],y1[100]; int cp=0; n1[0]= x1[0]=x; y1[0]=y; do{ if(n1[cp]==0) { cp--; n1[cp]--; y1[cp]=x1[cp]; //根据计算函数 每次x移到y的位置x1[cp]=x1[cp+1]+1; } else{ while(y1[cp]&0) { cp++; n1[cp]=n1[cp-1]; x1[cp]=x1[cp-1]; y1[cp]=y1[cp-1]-1; } cp--; y1[cp]=x1[cp]; if(n1[cp]==0) x1[cp]=x1[cp+1]+1; if(n1[cp]==1) x1[cp]=x1[cp+1]; if(n1[cp]==2) x1[cp]=0; if(n1[cp]==3) x1[cp]=1; if(n1[cp]&=3) x1[cp]=2; n1[cp]--; } }while(cp&0||n1[cp]&0); return x1[0]+1; }
为你推荐：
其他类似问题
您可能关注的内容
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。博客访问： 120294
博文数量： 144
博客积分： 0
博客等级： 民兵
技术积分： 493
注册时间：
分类： C/C++ 18:50:09
原文地址： 作者：
这一篇主要是二叉树中各种遍历的非递归和递归算法的实现：
void PreOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{// 先序递归遍历T，对每个节点调用函数visit一次且仅一次
&&&&Visit(T->data);
&&&&PreOrderTraverse(T->lchild,Visit);
&&&&PreOrderTraverse(T->rchild,Visit);
void InOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//中序递归遍历T，对每个节点调用函数visit一次
&&&&InOrderTraverse(T->lchild,Visit);
&&&&Visit(T->data);
&&&&InOrderTraverse(T->rchild,Visit);
typedef BiTree_1 SElemType;
#include "Stack.h"
#include "Stack.c"
Status InOrderTraverse1(BiTree *T,Status(*Visit)(TElemType))
{//中序遍历二叉树T的非递归算法（利用栈），对每个数据元素调用函数visit
&&SqStack S;
&&BiTree *p;
&&InitStack(&S);
&&while(T||!StackEmpty(S))
&&&&&&Push(&S,T);
&&&&&&T=T->lchild;
&&&&&&Pop(&S,&T);
&&&&&&if(!Visit(T->data))
&&&&&&&&&return ERROR;
&&&&&&&&&T = T->rchild;
&&&&printf("\n");
&&&&return OK;
Status InOrderTraverse2(BiTree *T,Status(*Visit)(TElemType))
{//中序遍历二叉树T的非递归算法（利用栈），对每个数据元素调用函数visit，
&&SqStack S;
&&BiTree *p;
&&InitStack(&S);
&&Push(&S,T);
&&while(!StackEmpty(S))
&&&&while(GetTop(S,&p) && p)
&&&&&&Push(&S,p->lchild);
&&&&Pop(&S,&p);
&&&&if(!StackEmpty(S))
&&&&&&Pop(&S,&p);
&&&&&&if(!Visit(p->data))
&&&&&&&&return ERROR;
&&&&&&Push(&S,p->rchild);
&&printf("\n");
&&return OK;
void PostOrderTraverse(BiTree *T,Status(*Visit)(TElemType))
{//后序递归遍历T,对每个节点调用函数Visit一次
&&&&PostOrderTraverse(T->lchild,Visit);
&&&&PostOrderTraverse(T->rchild,Visit);
&&&&Visit(T->data);
void LevelOrderTraverse(BiTree *T,Status (*Visit)(TElemType))
{//层序递归遍历T，利用队列，对每个节点调用函数Visit一次
&&LinkQueue *q;
&&QElemType a;
&&q = (LinkQueue *)malloc(sizeof(struct QNode));
&&&&InitQueue(&q);
&&&&EnQueue(q,T);
&&&&while(!QueueEmpty(q))
&&&&&&DeQueue(q,&a);
&&&&&&Visit(a->data);
&&&&&&if(a->lchild!=NULL)
&&&&&&&&EnQueue(q,a->lchild);
&&&&&&if(a->rchild!=NULL)
&&&&&&&&EnQueue(q,a->rchild);
&&&&printf("\n");
&&free(q);
Status PreOrderN(BiTree *T,Status (*Visit)(TElemType))
{//先序遍历二叉树T非递归算法
&&SqStack s;
&&BiTree *p;
&&InitStack(&s);
&&Push(&s,T);//根指针入栈
&&while(!StackEmpty(s))
&&&&while(GetTop(s,&p) && p)
&&&&&&if(!Visit(p->data))
&&&&&&&&return ERROR;
&&&&&&Push(&s,p->lchild);//向左走到尽头
&&&&Pop(&s,&p);//空指针出栈
&&&&if(!StackEmpty(s))
&&&&&&Pop(&s,&p);
&&&&&&Push(&s,p->rchild);
void PreOrder(BiTree *T,Status(*Visit)(TElemType))
{//先序遍历的递归算法
&&&&Visit(T->data);
&&&&PreOrder(T->lchild,Visit);
&&&&PreOrder(T->rchild,Visit);
Status PostOrderN(BiTree *T,Status (*Visit)(TElemType))
{//后序遍历的非递归算法
&&SqStack s;
&&BiTree *p;
&&BiTree *r;
&&InitStack(&s);
&&Push(&s,T);
&&while(!StackEmpty(s))
&&&&while(GetTop(s,&p) && p)
&&&&&&Push(&s,p->lchild);
&&&&Pop(&s,&p);
&&&&if(!StackEmpty(s))
&&&&&&GetTop(s,&p);
&&&&if(p->rchild && p->rchild!=r)
&&&&&&p=p->rchild;
&&&&&&Push(&s,p);
&&&&&&p=p->lchild;
&&&&&&Pop(&s,&p);
&&&&&&if(!Visit(p->data))
&&&&&&&&&return ERROR;
&&&&&&r = p;
&&&&&&p=NULL;
&&&&&&Push(&s,p);
阅读(341) | 评论(0) | 转发(0) |
给主人留下些什么吧！~~
请登录后评论。首先非常感谢&hicjiajia&的博文：
这篇随笔开启我的博客进程，成为万千程序员中的一员，坚持走到更远！
折磨了我一下午的后序遍历中午得到解决，关键在于标记右子树是否被访问过，考虑过修改二叉树结点的数据结构，增加一个visit域，或者建一个栈存储已访问的结点。都比较麻烦没有调试成功。若将右子树也入栈，如果没有访问标记的话，会改变访问的次序，甚至出现死循环，这是比较危险的情况。从借鉴的博文里，摘录并改写为C的代码，基本上没有改动。后续问题努力写出自己的原创代码。
二叉树存储的数据类型为int型，用数字0表示子树为空
输入：1 2 3 0 8 0 0 4 0 0 5 6 0 0 7 0 0
得到后序遍历结果：
1 #include &stdio.h&
2 #include &stdlib.h&
4 #define OK
5 #define ERROR
6 #define MaxSize
8 typedef int ElemT
9 typedef int S
11 typedef struct BTNode{
struct BTNode *lchild,*
16 typedef struct St{
struct BTNode*
data[MaxSize];
20 //1.按先序次序生成二叉树
21 BTree* CreateT(){
BTree *BT;
scanf("%d",&ch);
BT=(BTree*)malloc(sizeof(BTree));
if(!BT){exit(OVERFLOW);}
BT-&lchild=CreateT();
BT-&rchild=CreateT();
return BT;
37 //4.后序遍历
38 Status PostOrder(BTree *BT) {
PostOrder(BT-&lchild);
PostOrder(BT-&rchild);
printf("%3d",BT-&data);
return OK;
else return ERROR;
47 //4.后序遍历-非递归
48 Status PostOrder2(BTree *BT) {
Stack s,s2;
int flag[MaxSize];
while(s.top!=0||T){
s.data[s.top++]=T;
flag[s.top-1]=0;
while(s.top!=0&&flag[s.top-1]==1){
T=s.data[--s.top];
printf("%3d",T-&data);
if(s.top!=0){
flag[s.top-1]=1;
T=s.data[s.top-1];
return OK;
74 int main(){
BTree *BT;
BT=CreateT();
if(PostOrder(BT)){
printf("\n后序遍历完成！\n");
if(PostOrder2(BT)){
printf("\n非递归后序遍历完成！\n");
&//-------------------------华丽的分割线-------------------------------------
下面是我自己写的后序遍历程序
1 //非递归后序遍历-test
2 void PostOrder3(BTree *T){
BTree *p=T;Ss.top=-1;
int tag[MaxSize];
while(p||s.top!=-1){
s.data[++s.top]=p;
tag[s.top]=0;
while(tag[s.top]==1){
p=s.data[s.top--];
printf("%d",p-&data);
p=s.data[s.top];
tag[s.top]=1;
if(s.top==-1) break;
阅读(...) 评论()一、基础概念：
，又称数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）
#include &stdio.h&
int fib1(int n)
int fib2(int n)；
int main()
printf("fibonacci数列下标:\n");
scanf("%d",&n);
printf("第n=%d的数列值是：%d\n",n, fib1(n));
int fib2(int n)
int a = 1;
int b = 1;
int c = a =
int i = 0;
for (i = 3; i &= i++)
int fib1(int n)
if (n &= 2)
return fib1(n - 2) + fib1(n - 1);
三、运行结果
四、递归的优劣
递归好处：代码更简洁清晰，可读性更好 递归可读性好这一点，对于初学者可能会反对。实际上递归的代码更清晰，但是从学习的角度要理解递归真正发生的什么，是如何调用的，调用层次和路线，调用堆栈中保存了什么，可能是不容易。但是不可否认递归的代码更简洁。一般来说，一个人可能很容易的写出前中后序的二叉树遍历的递归算法，要写出相应的非递归算法就比较考验水平了，恐怕至少一半的人搞不定。所以说递归代码更简洁明了。
递归坏处：由于递归需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能系统撑不住。
总之，调用函数要消耗资源，所以递归空间和时间消耗都大，而且，如果递归太深，会堆栈溢出，系统撑不住。
因此，若出现类似伪递归算法，尽量使用非递归方式解决
递归法求斐波那契数列（C语言版）
斐波那契数列：
又称黄金分割数列，指的是这样一个数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
C语言递归方法实现斐波那契数列
本文介绍面试题经典试题之一：C语言用递归方法实现斐波那契数列（从第三个数起，后一个数等于前面两个数之和）：1、1、2、3、5、8、13、21、34.........
long int...
C语言斐波那契数列的四种实现方式—递归，迭代，数组，队列
自博客园转载：
效率低，除了最后一个数，每个数都被重复计算若干次
1: //递归实现
2: public static int Fib1(int n)
C语言经典算法（八）——递归实现斐波那契数列的两种方法
后继续整理算法并写出自己的理解和备注。 C++实现的：递归实现斐波那契数列
递归实现斐波那契数列Fib(n)
题目描述:输入n值，求解第n项的斐波那契数列值
方法一:概念法
斐波那契数列-数组和递归-C语言
兔子在出生两个月后,就有繁殖能力,一对兔子每一个月能生成一对小兔子来,假设所有的兔子都不死,那么一年之后可以繁殖多少对兔子?
这个问题就是 典型的 斐波那契数列
斐波那契数列的特点是: 前...
一、非递归实现第N个菲波那切数列：
程序如下：
int fib(int n)
int a1 = 1;
int a2 = 1;
int a3 = 0;
#include&stdio.h&
int Fib(int n){ // 自定义函数
return ...
C语言实现斐波那契数列递归和非递归算法
// c_dataStructure.cpp : 定义控制台应用程序的入口点。
#include &stdafx.h&
算法——Fibonacci数列的多种解法（递归算法）
咳咳，金宸欧巴今天来更新博客了，今天想写的一点内容是关于斐波那契数列的解法，fibonacci数列的定义如下：F(n)=
Fibonacci （斐波那契数列）-循环，递归实现方式
Fibonacci （斐波那契数列）-循环，递归实现方式
long fibonacci(int
long fibonacci_loop(int
没有更多推荐了，