广工数据结构anyview答案(5)

{

if(fabs(p*p-A)=e))

return Sqrt(A,(p+A/p)/2,e); }

/***07*******

【题目】已知Ackerman函数的定义如下： akm(m,n) = n+1 当m=0 akm(m,n) = akm(m-1,1) 当m!=0,n=0 akm(m,n) = akm(m-1,akm(m,n-1)) 当m!=0,n!=0 请写出递归算法。 **********/

int Akm(int m, int n)

/* 若 m<0 或 n<0 则返回-1 */ {

if(m<0||n<0) return -1; if(m==0) return n+1;

if(m!=0&&n==0) return Akm(m-1,1);

if(m!=0&&n!=0) return Akm(m-1,Akm(m,n-1)); }

/***15*******

【题目】试写出求递归函数F(n)的非递归算法： F(n) = n+1 当n=0 F(n) = nF(n/2) 当n>0 **********/ int F(int n)

/* 如果 n<0 则返回 -1 */ {

int i = n;

if(n<0) return -1; if(n==0) return 1; n = n/2; while(n>0) {

i *=n; n = n/2; }

return i; }

/* //递归

if(n<0) return -1;

if(n==0) return 1;

if(n>0) return n*F(n/2); */

/***16*******

【题目】求解平方根 的迭代函数定义如下： sqrt(A,p,e) = p 当|p*p-A|=e

其中，p是A的近似平方根，e是结果允许误差。试写出相 应的非递归算法。 **********/

float Sqrt(float A, float p, float e) {

while(fabs(p*p-A)>=e) {

p = (p+A/p)/2;

} return p; }

/***20*******

【题目】假设以二维数组g[1..m][1..n]表示一个图像 区域，g[i][j]表示该区域中点(i,j)所具颜色，其值

为从0到k的整数。试编写递归算法，将点(i0,j0)所在 区域的颜色置换为颜色c。约定与(i0,j0)同色的上、 下、左、右的邻接点为同色区域的点。

表示图像区域的类型定义如下： typedef char GTYPE[m+1][n+1]; **********/

void ChangeColor(GTYPE g, int m, int n, char c, int i0, int j0) /* 在g[1..m][1..n]中，将元素g[i0][j0] */

/* 所在的同色区域的颜色置换为颜色c */ {

g[0][0] = g[i0][j0];

g[i0][j0] = c;

if(i0+1<=m&&g[0][0]==g[i0+1][j0]) ChangeColor(g, m, n, c, i0+1, j0); if(i0-1>=1&&g[0][0]==g[i0-1][j0]) ChangeColor(g, m, n, c, i0-1, j0); if(j0-1>=1&&g[0][0]==g[i0][j0-1]) ChangeColor(g, m, n, c, i0, j0-1); if(j0+1<=n&&g[0][0]==g[i0][j0+1]) ChangeColor(g, m, n, c, i0, j0+1); /*

g[0][0] = g[i0][j0];

g[i0][j0] = c;

if(g[0][0]==g[i0+1][j0]&&i0+1<=m) ChangeColor(g, m, n, c, i0+1, j0); if(g[0][0]==g[i0-1][j0]&&i0-1>=1) ChangeColor(g, m, n, c, i0-1, j0); if(g[0][0]==g[i0][j0-1]&&j0-1>=1) ChangeColor(g, m, n, c, i0, j0-1); if(g[0][0]==g[i0][j0+1]&&j0+1<=n) ChangeColor(g, m, n, c, i0, j0+1); */ }

第8章

/***06*******

【题目】编写复制一棵二叉树的递归算法。 二叉链表类型定义：

typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/

void CopyBiTree(BiTree T, BiTree &TT) /* 递归复制二叉树T得到TT */ {

BiTree t;

t = (BiTree)malloc(sizeof(BiTNode)); t->lchild = NULL; t->rchild = NULL; if(T ==NULL) return ; t->data = T->data ; TT = t;

CopyBiTree(T->lchild, TT->lchild); CopyBiTree(T->rchild, TT->rchild); }

/****11**************

void PreOrderi(BiTree T,int k,int &count,TElemType &A){ if(T == NULL) return ;

if(k == count) A = T->data; count++;

PreOrderi(T->lchild, k,count,A); PreOrderi(T->rchild, k,count,A);

}

/**********

【题目】编写递归算法，求对二叉树T先序遍历时 第k个访问的结点的值。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/

TElemType PreOrderK(BiTree T, int k)

/* 求对二叉树T先序遍历时第k个访问的结点的值。*/ /* 若失败，则返回'#' */ {

if(k == 0) return '#'; if(T == NULL) return '#'; int count = 1; TElemType A;

PreOrderi(T,k,count,A); return A; }

/****12******

【题目】编写递归算法，计算二叉树T中叶子结点的数目。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/

int Leaves(BiTree T)

/* 计算二叉树T中叶子结点的数目 */ {

int l,r;

if(NULL == T) return 0;

if(T->lchild ==NULL && T->rchild ==NULL) return 1; l = Leaves(T->lchild); r = Leaves(T->rchild); return l+r; }

/***21*******

【题目】试利用栈及其基本操作写出二叉树T的非递归 的先序遍历算法。 二叉链表类型定义： typedef struct BiTNode { TElemType data;

struct BiTNode *lchild,*rchild; } BiTNode, *BiTree;

可用栈类型Stack的相关定义：

typedef BiTree SElemType; // 栈的元素类型 Status InitStack(Stack &S); Status StackEmpty(Stack S);

Status Push(Stack &S, SElemType e); Status Pop(Stack &S, SElemType &e); Status GetTop(Stack S, SElemType &e); **********/

void PreOrder(BiTree T, void (*visit)(TElemType)) /* 使用栈，非递归先序遍历二叉树T， */ /* 对每个结点的元素域data调用函数visit */ {

Stack S; InitStack(S); BiTree p = T;

while(p!=NULL){ if(p !=NULL) {

while(p != NULL) {

visit(p->data);

if(p->rchild !=NULL) //把不为空的右结点入栈 Push(S,p->rchild ); p = p->lchild; } }

if(StackEmpty(S) != TRUE) Pop(S, p); else

p = NULL;//栈空表明遍历结束 } }

/***23*******

【题目】试利用栈及其基本操作写出二叉树T的非递归

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库广工数据结构anyview答案(5)在线全文阅读。