A. c語言漢諾塔問題非遞歸解法代碼求大神講解
int game2()要改為int main()後才可編譯運行：
#include<stdio.h>
#include<stdlib.h>
#define CSZL 10
#define FPZL 10
typedef struct hanoi
{
int n;
char x,y,z;
}hanoi;
typedef struct Stack //定義棧結點
{
hanoi *base,*top;
int stacksize;
}Stack;
int InitStack(Stack *S)
{
S->base=(hanoi *)malloc(CSZL*sizeof(hanoi)); //申請棧空間
if(!S->base) //若申請不成功返回失敗信息
return 0;
S->top=S->base; //置為空棧
S->stacksize=CSZL; //棧結點數
return 1;
}
int PushStack(Stack *S,int n,char x,char y,char z) //入棧
{
if(S->top-S->base==S->stacksize) //若棧已滿
{
S->base=(hanoi *)realloc(S->base,(S->stacksize+FPZL)*sizeof(hanoi)); //補充申請，擴充棧空間
if(!S->base) //若申請不成功返回失敗信息
return 0;
S->top=S->base+S->stacksize; //重置棧頂指針
S->stacksize+=FPZL; //重置棧空間尺寸
}
S->top->n=n; //新結點信息存入棧頂結點
S->top->x=x;
S->top->y=y;
S->top->z=z;
S->top++; //棧中元素加1
return 1;
}
int PopStack(Stack *S,int *n,char *x,char *y,char *z) //出棧
{
if(S->top==S->base) //若棧已空
return 0; //返回出錯信息
else
{
S->top--; //棧頂指針減1
*n=S->top->n; //返回出棧元素信息
*x=S->top->x;
*y=S->top->y;
*z=S->top->z;
return 1;
}
}
int EmptyStack(Stack *S) //判定是否空棧
{
if(S->base==S->top)
return 1;
else
return 0;
}
int i=1;
void Move(char x,char z) //列印移動盤子的信息
{
printf(" 第%d步，%c-->%c",i++,x,z);
}
int main() /* 非遞歸法 */
{
int n;
char x,y,z;
Stack *S;
system("cls"); /*清屏指令*/
S=(Stack *)malloc(sizeof(Stack)); //申請棧空間
if(!S)
return 0;
if(!InitStack(S)) //初始化棧
return 0;
printf("請輸入漢諾塔的初始盤子數量以及軸的名稱：");
scanf("%d %c%c%c",&n,&x,&y,&z);
if(!PushStack(S,n,x,y,z)) //要移動的盤子數及各軸名稱入棧
return 0;
while(!EmptyStack(S)) //當棧非空時循環
{
if(!PopStack(S,&n,&x,&y,&z)) //若空棧則退出循環，否則出棧一個任務
break;
if(n==1) //若只有一個盤子，直接移動
{
Move(x,z);
}
else //有1個以上的盤子時入棧（注意棧的工作特點，是後進先出，所以最先做的事要最後入棧）
{
if(!PushStack(S,n-1,y,x,z)) //將上層的n-1個盤子從y移向z
break;
if(!PushStack(S,1,x,y,z)) //將底層的盤子從x移向z
break;
if(!PushStack(S,n-1,x,z,y)) //將上層的n-1個盤子從x移向y
break;
}
}
free(S->base);
S->base=NULL;
S->top=NULL;
S->stacksize=0;
return 0;
}
B. 急求C語言編程答案——遞歸、非遞歸
#include<stdio.h>
void apart(long);
void main()
{
long N;
printf("請輸入要拆分的數N：\n");
scanf("%ld",&N);
printf("\n");
printf("拆分後的結果是：\n");
apart(N);
printf("\n");
}
void apart(long N)
{
int i;
char a[30]; // 存放N中的各位數
i=0;
while(N)
{
a[i++]=N%10+'0'; //轉換成ascii碼
N/=10;
}
while(i--) //倒序輸出
{
printf("%c ",a[i]);
}
}
C. 數據結構C語言 一個遞歸和非遞歸的代碼
#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //棧的初始長度
#define STACKINCREMENT 5 //棧的追加長度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉樹結點定義
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 鏈棧結點定義top棧頂 base棧底 且棧元素是指向二叉樹結點的二級指針
//建立一個空棧
int initstack(sqstack *s)
{s->base=(bitree **)malloc(STACK_INIT_SIZE*sizeof(bitree *)); //棧底指向開辟空間
if(!s->base) exit(1); //拋出異常
s->top=s->base; //棧頂=棧尾 表示棧空
s->stacksize=STACK_INIT_SIZE; //棧長度為開辟空間大小
return 1;
}
//進棧
int push(sqstack *s,bitree *e)
{if(s->top-s->base>=s->stacksize) //如果棧滿 追加開辟空間
{s->base=(bitree **)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree*));
if(!s->base) exit(1); //拋出異常
s->top=s->base+s->stacksize; //感覺這一句沒用
s->stacksize+=STACKINCREMENT;}
*(s->top)=e;s->top++; //進棧 棧頂後移
return 1;
}
//出棧
int pop(sqstack *s,bitree **e)
{if(s->top==s->base) return 0; //棧空 返回0
--s->top;*e=*(s->top); //棧頂前移 取出棧頂元素給e
return 1;}
//取棧頂
int gettop(sqstack *s,bitree **e) //去棧頂元素 注意top指向的是棧頂的後一個
{if(s->top==s->base) return 0; //所以 s->top-1
*e=*(s->top-1);
return 1;
}
/*------------------------非遞歸-----先序建立二叉樹----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=(sqstack *)malloc(sizeof(bitree)); //加上這一句為s 初始化開辟空間
ch=getchar();
if(ch!='#'&&ch!='\n') /* 輸入二叉樹先序順序 是以完全二叉樹的先序順序
不是完全二叉樹的把沒有的結點以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht->data=ch;
ht->lchild=ht->rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根節點進棧
while((ch=getchar())!='\n') // 算
{if(ch!='#') {q=(bitree *)malloc(sizeof(bitree)); // 法
q->data=ch; //
if(p==*(s->top-1)) p->lchild=q; // 核
else p->rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s->top-1)) p->lchild=NULL; // 的
else p->rchild=NULL; //
pop(s,&p);} // 步
//
} // 驟
return ht;
}
else return NULL;
}
/*--------------------------遞歸---------先序建立二叉樹-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序輸入二叉樹中的結點的值（一個字元），空格字元表示空樹，
//構造二叉鏈表表示二叉樹
char ch;
scanf("%c",&ch);
if(ch=='#') *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)->data=ch; //生成根結點
CreateBiTree(&(*T)->lchild); //構造左子樹
CreateBiTree(&(*T)->rchild); //構造右子樹
}
}
/*--------------------------非遞歸-------中序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------中序建立二叉樹-------------------------------*/
/*--------------------------非遞歸-------後序建立二叉樹-------------------------------*/
/*--------------------------遞歸---------後序建立二叉樹-------------------------------*/
/*-----------------------非遞歸------先序輸出二叉樹------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h->data);h=h->lchild;}
else{pop(&m,&h);
h=h->rchild;}
}
}
/*------------------------非遞歸-----中序輸出二叉樹----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h->lchild;}
else {
pop(&m,&h);
printf("%c",h->data);
h=h->rchild;
}
}
}
/*---------------------非遞歸----後序遍歷二叉樹----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h->lchild;}
else {
bitree *r; //使用r結點表示訪問了右子樹 代替標志域
gettop(&m,&h);
if(h->rchild&&h->rchild!=r)
{h=h->rchild;
push(&m,h);
h=h->lchild;}
else{pop(&m,&h);
printf("%c",h->data);
r=h;h=NULL;}
}
}
}
//層次遍歷二叉樹
/*-------------------------------主過程-------------------------------*/
int main()
{bitree *ht;
printf("先序非遞歸建立一個二叉樹:");
if((ht=createprebitree())!=NULL) //非遞歸建立
//CreateBiTree(&ht);
//if(ht!=NULL) //遞歸建立
{
printf("先序遍歷輸出二叉樹:");
preordertraverse(ht);
putchar('\n');
printf("中序遍歷輸出二叉樹:");
inordertraverse(ht);
putchar('\n');
printf("後序遍歷輸出二叉樹:");
postordertraverse(ht);
putchar('\n');
}
else printf("空二叉樹\n");
}
D. 編寫遞歸和非遞歸求階乘的函數，用C語言
C語言遞歸函數和非遞歸函數求階乘，參考代碼如下:
#include<stdio.h>
long fun1(int n)
{
if(n<=1) return 1;
return fun1(n-1)*n;
}
long fun2(int n)
{
int i;
long m=1;
for(i=1; i<=n; ++i)
m*=i;
return m;
}
int main()
{
printf("%ld\n",fun1(9));
printf("%ld\n",fun2(9));
return 0;
}
E. C語言遞歸函數和反遞歸函數
//由於整數的位數是不確定的，可以很長，所以不能用int類型
//為了能表示長整數，我們採用字元串來表示
//一下的代碼是用c++寫的，和c區別不大
#include<iostream>
#include<cstring>
using namespace std;
void revstr1(char *str){
int length=strlen(str);
if(length>0){
char c=*(str+length-1);
*(str+length-1)='\0';
cout<<revstr1(str);
cout<<c;
}
}
void revstr2(char *str){
char *p;
int length=strlen(str);
//從後面將整數反序輸出
for(p=str+length-1; p>=str,p--)
cout<<*p;
//補上換行符
cout<<endl;
}
void main(){
//整數最大長度100，可以調節
char str[101];
cin.getline(str,100);
//遞歸輸出
revstr1(str);
//補上換行符
cout<<endl;
//非遞歸輸出
revstr2(str);
return 0;
}
F. 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;
}
G. C語言中，遞歸先序遍歷和非遞歸先序遍歷的有何區別各自優缺點
1、遞歸就是函數調用函數本身，運行起來就是函數嵌套函數，層層嵌套，所以函數調用、參數堆棧都是不小的開銷，但是程序簡單。
2、非遞歸就是不斷地對參數入棧、出棧，省去了函數層層展開、層層調用的開銷。雖然參數出入棧次數多了，但是一般都開辟固定的足夠大的內存來一次性開辟、重復使用。
3、非遞歸是從堆棧的角度來編寫程序，速度快，但代碼復雜。
遞歸是從問題本身的邏輯角度來編寫，雖然速度相對慢，但代碼容易理解。
如果對速度要求不高，建議用遞歸方式。
4、摘錄例子如下：
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
} BiTNode,*BiTree;//二叉樹的節點類型
typedef struct QNode
{
BiTNode data;
struct QNode *next;
} QNode,*QueuePtr;//隊列節點類型
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;//隊列的頭尾指針
void InitQueue(LinkQueue *Q)//創建隊列
{
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->rear->next=NULL;
}
void EnQueue(LinkQueue *Q,BiTNode e)//入隊操作
{
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
BiTNode DeQueue(LinkQueue *Q)//出對操作
{
BiTNode e;QueuePtr p;
p=Q->front->next;
e=p->data;
Q->front->next=p->next;
if(Q->rear==p)
Q->rear=Q->front;
free(p);
return (e);
}
int QueueEmpty(LinkQueue *Q)//判斷隊列是否為空
{
if(Q->front==Q->rear )
return 1;
else
return 0;
}
BiTree CreateBiTree()//創建二叉樹
{
char p;BiTree T;
scanf("%c",&p);
if(p==' ')
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
T->data=p;
T->lchild=CreateBiTree(T->lchild);
T->rchild=CreateBiTree(T->rchild);
}
return (T);
}
void PreOrder(BiTree T)//先序
{
if(T!=NULL)
{
printf("%c",T->data);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
void LevelOrder(BiTree T)//層次遍歷
{
LinkQueue Q; BiTNode p;
InitQueue(&Q);
EnQueue(&Q,*T);
while(!QueueEmpty(&Q))
{
p = DeQueue(&Q);
printf("%c",p.data);
if(p.lchild!=NULL)
EnQueue(&Q,*(p.lchild));
if(p.rchild!=NULL)
EnQueue(&Q,*(p.rchild));
}
}
void main()
{
BiTree Ta;
Ta=CreateBiTree();
printf("層次遍歷:");
printf("\n");
LevelOrder(Ta);
printf("\n");
printf("先序遍歷:");
printf("\n");
PreOrder(Ta);
}
層次使用非遞歸的，用到隊列
先序是用遞歸的
創建樹使用先序遞歸建樹
輸入個例子：
abc**de*f**g***(注意*代表空格，因為空格你看不到就不好表示).
H. C語言的兩個問題： 所有的遞歸程序均可以用非遞歸演算法實現遞歸函數中的形式參數是自動變數嗎 c語言中
C語言所有遞歸都可以用非遞歸演算法實現，最典型的就是迭代法，有時比遞歸更容易理解。至於遞歸中的形式參數是自動變數，沒明白樓主的意思，形參就是形參啊，形參變數也是變數，其內存分配在棧區，隨著函數的結束，其內存也會被釋放，形參的生命周期與函數生命周期相同哈（同生共死）
I. C語言中遞歸函數是，非遞歸函數是能否舉例子
直接或間接調用自已的函數就是遞歸函數，否則為非遞歸函數。如：
unsignedfun(unsignedx){
if(x==1||x==0)
return1;
returnx*fun(x-1);
}這個函數的體中出現了調用自己的語句fun(x-1);，所以是遞歸函數。
J. 用C語言編寫非遞歸演算法實現折半查找（二分查找）
char a[10][5];//按字典序遞增
int search(char *x)//二分查找，返回有序表中大於等於x的元素位置
{
int low=0,high=9,mid,t;
while(low<=high)
{
mid=(low+high)/2;
t=strcmp(a[mid],x);//比較中點位置與x
if(t==0) return mid;//相等返回其位置
else
if(t>0) high=mid-1;//x小於mid元素，則在中點前
else low=mid+1;
}
return high+1;//返回大於x的第一個元素
}
這個是我曾經用過的字元串的二分查找~
請根據需要修改數據類型。。。