『壹』 C++ 使用递归及非递归两种方法,编程实现单向链表的反转。
不知道你是需要用STL来写还是类似C的写法,给个简单的例子吧#include "stdafx.h"
#include "malloc.h"
#include "ostream.h"typedef struct _Node
{
int value;
_Node * pNext;
}Node;Node * InitList()
{
Node * pHead = (Node*)malloc(sizeof(Node));
Node * pNode = pHead;
pHead->value = 0;
for(int i = 1; i < 50; i ++)
{
pNode->pNext = (Node *)malloc(sizeof(Node));
pNode = pNode->pNext;
pNode->value = i;
pNode->pNext = NULL;
}
return pHead;
}
//返回尾节点
Node * Revert1(Node * pHead)
{
Node * pfather = pHead;
Node * pNode;
if(!pfather) return NULL;
pHead = pHead->pNext;
pfather->pNext = NULL;
while(pHead != NULL)
{
pNode = pHead->pNext;
pHead->pNext = pfather;
pfather = pHead;
pHead = pNode;
}
return pfather;
}
//返回尾节点
Node * Revert2(Node * pHead, Node * pfather = NULL)
{
Node * ret = NULL;
if(!pHead) return NULL;
if(pHead->pNext)
ret = Revert2(pHead->pNext, pHead);
pHead->pNext = pfather;
if(!ret)
return pHead;
else
return ret;
}void PrintNode(Node * pNode)
{
while(pNode)
{
cout<<pNode->value<<" ";
pNode = pNode->pNext;
}
}
int main(int argc, char* argv[])
{
Node * pNode = Revert2(InitList());
PrintNode(pNode);
return 0;
}
『贰』 F(N)=2*F(N-1)+3*F(N-2)的非递归算法是怎么写的用C++1
用循环去做
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
int n;
double f0, f1;
cin >> n; //计算到f(n)
cin >> f0 >> f1; //初始值
if(n < 2)
return -1;
int t = 2;
double f = 0.;
while(t <= n)
{
f = 2*f1+3*f0;
f0 = f1;
f1 = f;
++t;
}
cout << "fn is " << f << endl;
return 0;
}
希望我的回答能得到采纳
『叁』 如何编程实现二叉树的非递归遍历
前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。
1.递归实现
void preOrder1(BinTree *root) //递归前序遍历
{
if(root!=NULL)
{
cout<<root->data<<" ";
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
2.非递归实现
根据前序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子。即对于任一结点,其可看做是根结点,因此可以直接访问,访问完之后,若其左孩子不为空,按相同规则访问它的左子树;当访问其左子树时,再访问它的右子树。因此其处理过程如下:
对于任一结点P:
1)访问结点P,并将结点P入栈;
2)判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1);若不为空,则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空,则遍历结束。
void preOrder2(BinTree *root) //非递归前序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
二.中序遍历
中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。
1.递归实现
void inOrder1(BinTree *root) //递归中序遍历
{
if(root!=NULL)
{
inOrder1(root->lchild);
cout<<root->data<<" ";
inOrder1(root->rchild);
}
}
2.非递归实现
根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。因此其处理过程如下:
对于任一结点P,
1)若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理;
2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子;
3)直到P为NULL并且栈为空则遍历结束
void inOrder2(BinTree *root) //非递归中序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
『肆』 C语言编程:用递归和非递归法输出斐波那契数列
你用的什么编译器我用VC++6.0完全正常我给你贴图
循环版 
========================================= 
#include    <stdio.h> 
int    main() 
{ 
        unsigned    int    a[40]    =    {0,    1}; 
        printf    ("%d %d ",    a[0],    a[1]); 
        for    (    int    i    =    2;    i    <    40;    ++i) 
        { 
                a[i]    =    a[i-1]    +    a[i-2]; 
                printf    ("%d ",    a[i]); 
        } 
        return    0; 
} 
=========================================== 
递归版 
=========================================== 
#include    <stdio.h> 
int    fb    (int    i) 
{ 
        if    (    i    <    2    ) 
                return    i    ==    0    ?    0    :    1; 
        return    fb    (i    -    1)    +    fb    (i    -    2); 
} 
int    main() 
{ 
        for    (    int    i    =    0;    i    <    40;    ++i) 
                printf    ("%d ",    fb    (i)); 
        return    0; 
} 
『伍』 C语言,用非递归的算法(链栈)计算二叉树的结点数。
#包括
使用命名空间std;
定义MAX 100
类二叉树
{
char数据;
二叉树* lchild;
二叉树* rchild;
};的
二叉树* creatree()/ /非递归创建一棵二叉树
{ />字符CH;
诠释前面= 1,后= 0; / /初始化队列
B树*根*,S * Q [MAX];
根= NULL;
cout <<“请'@'表示'空','#',”结束“,他的贡献层:”<< endl;
CH = getchar函数();
而因素(ch! = '#')
{
= NULL,/ /读取的第一个假设是空的节点_at_
(ch! =“_at_')
{
新的二叉树;
- >数据= CH;
- > lchild = NULL;
- > rchild = NULL;
}
后端的团队+ +; / /指针递增
Q [后] =;
如果(后部== 1)
根= / /根
其他
{
(S && Q [前方])/ /当前节点的父节点是不是空的节点
(后部%2 == 0)
Q [前] - > lchild;
其他
Q [前] - > rchild =;
(背面%2 == 1)
前+ +;
} BR /> CH = getchar函数()/ /读出下一个节点的值
}
返回根;
}
无效后序(B树* BT)
二叉树* p = BT,*栈[MAX] ;/ / p表示当前节点协议栈栈[]
INT标记用于存储节点[MAX];
顶部= -1 ;
{
在while(p! = NULL)/ /第一个处理器节点的左子节点都留给孩子,反过来堆栈
{
>栈[+ +顶部] = P;
[顶] = 0;
P = P-> lchild;
}
(TOP> = 0)/ /所有留守儿童处理
{
(标记[顶])/ /如果当前节点的右子尚未被访问
{
P =堆栈[顶]; /输出的协议栈节点的顶部,但消失在堆栈中,因为要输出他们的孩子的第一个节点
p = P-> rchild; / /右子节点的处理
标签[顶] = 1; / /在被访问的的堆栈存储节点的右子榜首的位置,下一次你把它退栈直接输出
}
其他
{
法院<数据/ /在栈的栈顶元素,输出的节点,节点p指向NULL
}
}}而(( P = NULL)| |(> = 0));
}
廉政的main()
{
二叉树BT;
BT = creatree();
法院<<'\ n'<<“后序”;
后序(BT);
法院<< endl;
系统(“暂停“);
返回0;
}
『陆』 如何在linux系统中用C语言编程实现以非递归的方式查询指定目录下所有子目录的全部文件并保存文件名
把迭代得到的非文件文件夹项,即子目录保存到一个stack中。
随后逐个弹出栈顶元素并迭代之,就实现了以非递归方式遍历文件夹。
『柒』 这道数据结构编程题怎么做将非递归的折半查找改写为递归算法,用C++编程,求大神解答~~~
没看到你的具体题目,折半算法对被查找的数组是有要求的,必须是顺序排列,而且递增和递减是不一样的。因为没看到具体要求,我只能按我的想法给你讲讲折半算法。
【解题思路】
折半查找法,是指在一组按顺序排列的数中,每次都从中间位置开始比较,如果等于被查找数就是找到了,如果不等于被查找数,则在另外一半的元素中找,循环往复,一直到找到或找遍为止。折半查找法最好的就是用函数的递归调用。
比如,要在一个15个元素的递增数组S中查找数值A,查找范围是S[0]-S[14],那么首先是找出中间点S[7]作比较,如果S[7]等于A就是找到了,如果S[7]大于A,则说明A在S[0]-S[6]之间;反之,则说明A在S[8]-S[14]之间,然后再重复上述步骤,找出范围内的中间点进行比较,一直到找到或者不能再折半为止。
【程序代码】
#include<iostream>//控制台操作头文件
/*下面的Find()函数是在递增数组中用折半查找法的递归函数,其中S是要查找的数组,B是查找范围的起始下标,E是查找范围的终止下标,A是要查找的数值,如果找到了就返回该数值在数组中是第几个(从第0个开始算),如果找不到就返回-1*/
intFind(int*S,intB,intE,intA)//查找函数
{if(B>=E)//不能折半则无需继续递归
{if(S[B]==A)returnB;//找到则返回数组下标
elsereturn-1;}//找不到则返回-1
intI=B+(E-B+1)/2;//折半查找的中间点位置
if(S[I]==A)returnI;//和中间点比较,找到则返回I
if(S[I]>A)E=I-1;//大于A则在数组的前半段查找
elseB=I+1;//否则在数组的后半段查找
returnFind(S,B,E,A);}//递归调用查找函数
intmain()//主函数
{intS[]={1,3,5,7,9,11,13,15,17,//定义一个16个元素的递增数组
19,21,23,25,27,29,31,};
intA=0,O=0;//定义两个整型变量
while(A>=0)//当A为非负数的时候循环
{printf("请输入要找的数值:");//显示提示输入的信息
scanf("%d",&A);//从键盘输出要查找的数
O=Find(S,0,15,A);//调用函数在S数组中查找
if(O==-1)printf("没有找到 ");//如果找不到显示提示信息
elseprintf("%d在第%d个 ",A,O);//否则显示出找到的对应下标
printf(" ");}//换行开始查找下一个
system("PAUSE");//屏幕暂停,以便看到运行结果
return0;//结束程序
}
【运行结果】
以上程序在DEVC++中运行通过
『捌』 谁会汉诺塔非递归的编程(java),并真正了解含义
public class Hannuota {
private int n;//储存盘子个数
public Hannuota(int n){
this.n = n;
}
public void function(){
//初始化三个柱子,A是开始堆满盘子的柱子,C是目标柱子
Pillar a = new Pillar(n,n,"A");
Pillar b = new Pillar(n,"B");
Pillar c = new Pillar(n,"C");
//把三个柱子按顺序排好,详见后面的算法那里的解释
Pillar[] pillars = new Pillar[3];
pillars[0] = a;
if(n%2==0){
pillars[1] = b;
pillars[2] = c;
}else{
pillars[1] = c;
pillars[2] = b;
}
//开始移动,k用来计数,移动次数为2^n-1,至于为什么,我不太清楚,
//反正有人证明过。i是用来保存最小那个盘子正在哪跟柱子上的。
int i=0;
for(int k=0;k<(int)Math.pow(2, n)-1;){
int min;
//将最小的盘子顺时针移动一个柱子
min = pillars[i%3].Pop();
pillars[(i+1)%3].Push(min);
System.out.println(pillars[i%3]+"->"+pillars[(i+1)%3]);
k++;
i++;
//这个IF好像可以不要,当时写的,后面忘了删除。
if(k<(int)Math.pow(2, n)-1){
//如果,剩下两根柱子中,某一根为空,则一定是非空那根中最上面个盘子
//移动到空的那个柱子上。若两根都不为空,则把编号小的一个盘子
//移动到另外跟柱子上
if(!pillars[(i-1)%3].isEmpty()&&(pillars[(i+1)%3].isEmpty()||pillars[(i+1)%3].Top()>pillars[(i-1)%3].Top())){
min=pillars[(i-1)%3].Pop();
pillars[(i+1)%3].Push(min);
System.out.println(pillars[(i-1)%3]+"->"+pillars[(i+1)%3]);
}else{
min=pillars[(i+1)%3].Pop();
pillars[(i-1)%3].Push(min);
System.out.println(pillars[(i+1)%3]+"->"+pillars[(i-1)%3]);
}
k++;
}
}
}
//主函数,用来测试的。3表示3个盘子。
public static void main(String args[]){
new Hannuota(3).function();
}
}
class Pillar{//构造一个新类,表示柱子,实际是当一个栈在用
private int[] s;
private int top;
private String name;
public String toString(){
return name;
}
//这个构造函数用来构造BC两个柱子,下面那个用来构造柱子A。其实也可以写成一个构造函数。
public Pillar(int max,String name){
s = new int[max];
top = -1;
this.name = name;
for(int i=0;i s[i] = max+1;
}
}
public Pillar(int n,int max,String name){
s = new int[max];
top = n-1;
this.name = name;
for(int i=0;i s[i] = max - i;
}
}
//这后面这些就是栈的基本方法了,不用介绍了吧
public boolean isEmpty(){
return top==-1?true:false;
}
public int Top (){
return s[top];
}
public int Pop(){
return s[top--];
}
public void Push(int x){
s[++top] = x;
}
}
算法是这个
首先容易证明,当盘子的个数为n时,移动的次数应等于2^n - 1。
首先把三根柱子按顺序排成品字型,把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序:若n为偶数,按顺时针方向依次摆放 A B C;
若n为奇数,按顺时针方向依次摆放 A C B。
(1)按顺时针方向把圆盘1从现在的柱子移动到下一根柱子,即当n为偶数时,若圆盘1在柱子A,则把它移动到B;
若圆盘1在柱子B,则把它移动到C;若圆盘1在柱子C,则把它移动到A。
(2)接着,把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上,当两根柱子都非空时,移动较小的圆盘
这一步没有明确规定移动哪个圆盘,你可能以为会有多种可能性,其实不然,可实施的行动是唯一的。
(3)反复进行(1)(2)操作,最后就能按规定完成汉诺塔的移动。
这玩意要非递归真麻烦。需不需要加点注释?
『玖』 C#编程,利用递归、非递归编程实现输出如下字母金字塔
非递归:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
Console.WriteLine("输出a......k的字母金字塔为:");
string str="`abcdefghijklmnop";
for (int i = 1; i < 12; i++)
{
for (int j = 1; j < 50 - 2 * i; j++)
{
Console.Write(" ");
}
for (int j = -i+1; j < i; j++)
{
if (j < 0)
{
Console.Write(str[i+j] + " ");
}
else
{
Console.Write(str[i-j] + " ");
}
}
Console.WriteLine();
}
Console.Read();
}
}
}
递归:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
public static string str="`abcdefghijklmnop";
private static void fun(int i)
{
if (i > 11) return;
for (int j = 1; j < 50 - 2 * i; j++)
{
Console.Write(" ");
}
for (int j = -i + 1; j < i; j++)
{
if (j < 0)
{
Console.Write(str[i + j] + " ");
}
else
{
Console.Write(str[i - j] + " ");
}
}
Console.WriteLine();
fun(i + 1);
}
static void Main(string[] args)
{
Console.WriteLine("输出a......k的字母金字塔为:");
fun(1);
Console.Read();
}
}
}
『拾』 C语言编程:用递归和非递归法输出斐波那契数列
递归法:
#include<stdio.h>
void main()
{
int Fibonacci(int n);
int n,i,c=0;
printf("请输入n的值:");
scanf("%d",&n);
for(i=1; i<=n; i++)
{
c = Fibonacci(i);
printf("%12ld",c);
if(i%4==0) //用于换行 4个一行;
printf("\n");
}
}
int Fibonacci(int n)//函数部分;
{
long int f;
if(n==1 || n==2)
{
f=1;
}
else
if(n>=3)
f = Fibonacci(n-1) + Fibonacci(n-2);
return f;
}
非递归法:
#include<stdio.h>
void main()
{
int i,n;
int f[]= {1,1};
printf("请输入n的值:");
scanf("%d",&n);
for(i=2; i<=n; i++)
f[i] = f[i-2] + f[i-1];
for(i=0; i<=n; i++)
{
if(i%5==0) printf("\n");
printf("%12d",f[i]);
}
printf("\n");
}
递归可以使程序看起来比较简洁,但缺点是效率比较低,并且可能导致栈溢出,因此需要灵活使用递归。