AnyView DC05-06
2020-12-18 本文已影响0人
kekxy
/**********
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|p*p-A|<e
sqrt(A,p,e) = sqrt(A,(p+A/p)/2,e) 当|p*p-A|>=e
其中，p是A的近似平方根，e是结果允许误差。试写出相
应的递归算法。
**********/
float Sqrt(float A, float p, float e)
{
if(fabs(p*p-A)<e) return p; else
return Sqrt(A,(p+A/p)/2,e);
}
/**********
【题目】试写出求递归函数F(n)的递归算法：
F(n) = n+1 当n=0
F(n) = nF(n/2) 当n>0
**********/
int F(int n)
/* 如果 n<0 则返回 -1 */
{
if(n<0) return -1;
if(n==0) return n+1; else return n*F(n>>1);
}
/**********
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|p*p-A|<e
sqrt(A,p,e) = sqrt(A,(p+A/p)/2,e) 当|p*p-A|>=e
其中，p是A的近似平方根，e是结果允许误差。试写出相
应的递归算法。
**********/
float Sqrt(float A, float p, float e)
{
if(fabs(p*p-A)<e) return p; else
return Sqrt(A,(p+A/p)/2,e);
}
/**********
【题目】已知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; else
if(n==0) return Akm(m-1,1); else return Akm(m-1,Akm(m,n-1));
}
/**********
【题目】试写出求递归函数F(n)的非递归算法：
F(n) = n+1 当n=0
F(n) = nF(n/2) 当n>0
**********/
int F(int n)
/* 如果 n<0 则返回 -1 */
{
int s=1;
while(n)
{
s*=n;
n>>=1;
}
return s;
}
/**********
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|p*p-A|<e
sqrt(A,p,e) = sqrt(A,(p+A/p)/2,e) 当|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;
}
/**********
【题目】假设以二维数组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 */
{
char ch=g[i0][j0];
g[i0][j0]=c;
if(i0<m && g[i0+1][j0]==ch) ChangeColor(g,m,n,c,i0+1,j0);
if(i0>1 && g[i0-1][j0]==ch) ChangeColor(g,m,n,c,i0-1,j0);
if(j0<n && g[i0][j0+1]==ch) ChangeColor(g,m,n,c,i0,j0+1);
if(j0>1 && g[i0][j0-1]==ch) ChangeColor(g,m,n,c,i0,j0-1);
return;
}
/**********
【题目】试按依次对每个元素递归分解的分析方法重写求广义表的深度的递归算法。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode *hp, *tp;
} ptr;
}un;
} *GList;
**********/
int GListDepth(GList ls)
/* Return the depth of list */
{
int ans=0;
if(ls==NULL) return 1;
if(ls->tag==ATOM) return 0;
int h1=GListDepth(ls->un.ptr.hp)+1;
int h2=GListDepth(ls->un.ptr.tp);
return (h1>h2)?h1:h2;
}
/**********
【题目】试编写判别两个广义表是否相等的递归算法。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode *hp, *tp;
} ptr;
}un;
} *GList;
**********/
Status Equal(GList A, GList B)
/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */
{
if(((A==NULL)+(B==NULL))==1) return FALSE;
if(A->tag!=B->tag) return FALSE;
if(A->tag==ATOM && A->un.atom!=B->un.atom) return FALSE;
if(A->tag==LIST)
{
if(!Equal(A->un.ptr.hp,B->un.ptr.hp)) return FALSE;
if(!Equal(A->un.ptr.tp,B->un.ptr.tp)) return FALSE;
}
return TRUE;
}
/**********
【题目】试编写递归算法，输出广义表中所有原子项及其所在层次。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode *hp, *tp;
} ptr;
}un;
} *GList;
**********/
void OutAtom(GList A, int layer, void(*Out2)(char, int))
/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */
{
if(A==NULL) return;
if(A->tag==LIST)
{
if(A->un.ptr.hp!=NULL) OutAtom(A->un.ptr.hp,layer+1,Out2);
if(A->un.ptr.tp!=NULL) OutAtom(A->un.ptr.tp,layer,Out2);
} else Out2(A->un.atom,layer);
}
/**********
【题目】若两棵二叉树T1和T2皆为空，或者皆不空
且T1的左、右子树和T2的左、右子树分别相似，则
称二叉树T1和T2相似。试编写算法，判别给定两棵
二叉树是否相似。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
Status Similar(BiTree T1, BiTree T2)
/* 判断两棵二叉树是否相似的递归算法 */
{
if(T1==NULL && T2==NULL) return TRUE;
if((T1==NULL && T2!=NULL) || (T1!=NULL && T2==NULL)) return FALSE;
if(Similar(T1->lchild,T2->lchild)==FALSE) return FALSE;
if(Similar(T1->rchild,T2->rchild)==FALSE) return FALSE;
return TRUE;
}
/**********
【题目】编写递归算法，求对二叉树T先序遍历时
第k个访问的结点的值。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
TElemType PreOrderK(BiTree T, int k)
/* 求对二叉树T先序遍历时第k个访问的结点的值。*/
/* 若失败，则返回'#' */
{
//stack instead of dfs
BiTree* s,now;
s=(BiTree*)malloc(sizeof(BiTree)*100);
int p=1; s[p]=T;
int ks=0;
while(p)
{
now=s[p--]; ++ks;
if(ks==k) return now->data;
if(now->rchild!=NULL) s[++p]=now->rchild;
if(now->lchild!=NULL) s[++p]=now->lchild;
}
return '#';
}
/**********
【题目】编写递归算法，计算二叉树T中叶子结点的数目。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
int Leaves(BiTree T)
/* 计算二叉树T中叶子结点的数目 */
{
int s=0;
if(T==NULL) return 0;
if(T->lchild!=NULL) s+=Leaves(T->lchild);
if(T->rchild!=NULL) s+=Leaves(T->rchild);
if(!s) s=1; return s;
}
/**********
【题目】试利用栈及其基本操作写出二叉树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 */
{
if(T==NULL) return;
BiTree now; Stack S;
InitStack(S);
Push(S,T);
while(!StackEmpty(S))
{
GetTop(S,now);
Pop(S,now);
visit(now->data);
if(now->rchild!=NULL) Push(S,now->rchild);
if(now->lchild!=NULL) Push(S,now->lchild);
}
}
/**********
【题目】试利用栈及其基本操作写出二叉树T的非递归
的后序遍历算法(提示：为分辨后序遍历时两次进栈的
不同返回点，需在指针进栈时同时将一个标志进栈）。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef struct {
struct BiTNode *ptr; // 二叉树结点的指针类型
int tag; // 0..1
} 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 PostOrder(BiTree T, void (*visit)(TElemType))
/* 使用栈，非递归后序遍历二叉树T， */
/* 对每个结点的元素域data调用函数visit */
{
if(T==NULL) return;
SElemType now,nson; Stack S;
InitStack(S);
now.ptr=T; now.tag=0;
Push(S,now);
while(!StackEmpty(S))
{
GetTop(S,now);
Pop(S,now);
if(now.tag) visit(now.ptr->data); else
{
nson.ptr=now.ptr; nson.tag=1;
Push(S,nson);
if(now.ptr->rchild!=NULL)
{
nson.ptr=now.ptr->rchild;
nson.tag=0;
Push(S,nson);
}
if(now.ptr->lchild!=NULL)
{
nson.ptr=now.ptr->lchild;
nson.tag=0;
Push(S,nson);
}
}
}
}
/**********
【题目】二叉树采用三叉链表的存储结构，试编写
不借助栈的非递归中序遍历算法。
三叉链表类型定义：
typedef struct TriTNode {
TElemType data;
struct TriTNode *parent, *lchild, *rchild;
} TriTNode, *TriTree;
**********/
void InOrder(TriTree PT, void (*visit)(TElemType))
/* 不使用栈，非递归中序遍历二叉树PT， */
/* 对每个结点的元素域data调用函数visit */
{
if(PT==NULL) return;
TriTree x=PT;
bool flag=1;
while(flag)
{
while(x->lchild!=NULL) x=x->lchild;
while(x->rchild==NULL)
{
visit(x->data);
while(x->parent->rchild==x) x=x->parent;
if(x==PT) { flag=0; break; }
x=x->parent;
}
if(!flag) break;
visit(x->data); x=x->rchild;
}
}
/**********
【题目】假设在三叉链表的结点中增设一个标志域
(mark取值0,1或2)以区分在遍历过程中到达该结点
时应继续向左或向右或访问该结点。试以此存储结
构编写不用栈辅助的二叉树非递归后序遍历算法。
带标志域的三叉链表类型定义：
typedef struct TriTNode {
TElemType data;
struct TriTNode *lchild, *rchild, *parent;
int mark; // 标志域
} TriTNode, *TriTree;
**********/
void PostOrder(TriTree T, void (*visit)(TElemType))
/* 不使用栈，非递归后序遍历二叉树T， */
/* 对每个结点的元素域data调用函数visit */
{
if(T==NULL) return;
TriTree x=T;
for(;;)
{
if(x->mark==0)
{
x->mark=1;
if(x->lchild!=NULL)
{
x=x->lchild;
continue;
}
}
if(x->mark==1)
{
x->mark=2;
if(x->rchild!=NULL)
{
x=x->rchild;
continue;
}
}
visit(x->data);
if(x==T && x->mark==2) break;
x=x->parent;
}
}
/**********
【题目】编写递归算法，将二叉树中所有结点的
左、右子树相互交换。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
void ExchangeSubTree(BiTree &T)
/* 将二叉树中所有结点的左、右子树相互交换 */
{
if(T==NULL) return;
swap(T->lchild,T->rchild);
ExchangeSubTree(T->lchild);
ExchangeSubTree(T->rchild);
}
/**********
【题目】编写递归算法：求二叉树中以元素值
为x的结点为根的子树的深度。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
int Depthx(BiTree T, TElemType x)
/* 求二叉树中以值为x的结点为根的子树深度 */
{
if(T==NULL) return 0;
int d1=(T->data==x)?1:0,d2=d1;
if(T->lchild!=NULL)
{
if(T->data==x) d1=1+Depthx(T->lchild,T->lchild->data);
else d1=Depthx(T->lchild,x);
}
if(T->rchild!=NULL)
{
if(T->data==x) d2=1+Depthx(T->rchild,T->rchild->data);
else d2=Depthx(T->rchild,x);
}
return (d1>d2)?d1:d2;
}
/**********
【题目】编写递归算法：对于二叉树中每一个元素值为x
的结点，删去以它为根的子树，并释放相应的空间。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
void ReleaseX(BiTree &T, char x)
/* 对于二叉树T中每一个元素值为x的结点， */
/* 删去以它为根的子树，并释放相应的空间 */
{
if(T==NULL) return;
if(T->data==x)
{
free(T);
T=NULL; return;
}
BiTree y;
if(T->lchild!=NULL)
{
y=T->lchild;
if(T->lchild->data==x)
{
T->lchild=NULL;
free(y);
} else ReleaseX(y,x);
}
if(T->rchild!=NULL)
{
y=T->rchild;
if(T->rchild->data==x)
{
T->rchild=NULL;
free(y);
} else ReleaseX(y,x);
}
}
/**********
【题目】编写复制一棵二叉树的递归算法。
二叉链表类型定义：
typedef char TElemType; // 设二叉树的元素为char类型
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
**********/
void CopyBiTree(BiTree T, BiTree &TT)
/* 递归复制二叉树T得到TT */
{
if(T==NULL) return;
BiTNode *now;
now=(BiTNode*)malloc(sizeof(BiTNode));
now->data=T->data;
TT=now;
if(T->lchild!=NULL) CopyBiTree(T->lchild,TT->lchild);
if(T->rchild!=NULL) CopyBiTree(T->rchild,TT->rchild);
}
/**********
【题目】编写算法判别给定二叉树是否为完全二叉树。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
可用队列类型Queue的相关定义：
typedef BiTree QElemType; // 设队列元素为二叉树的指针类型
Status InitQueue(Queue &Q);
Status EnQueue(Queue &Q, QElemType e);
Status DeQueue(Queue &Q, QElemType &e);
Status GetHead(Queue Q, QElemType &e);
Status QueueEmpty(Queue Q);
**********/
Status CompleteBiTree(BiTree T)
/* 判别二叉树T是否为完全二叉树 */
{
Queue Q;
InitQueue(Q);
EnQueue(Q,T);
bool fixed=1,flag=1;
while(!QueueEmpty(Q))
{
BiTree now;
GetHead(Q,now); DeQueue(Q,now);
if(now->lchild!=NULL)
{
if(fixed) EnQueue(Q,now->lchild); else
{
flag=0; break;
}
}
if(now->rchild!=NULL)
{
if(fixed) EnQueue(Q,now->rchild); else
{
flag=0; break;
}
}
if(now->lchild==NULL || now->rchild==NULL) fixed=0;
}
return (flag)?TRUE:FALSE;
}
/**********
【题目】试编写一个二叉排序树的判定算法。
二叉排序树的类型BSTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} TElemType;
typedef struct BiTNode {
TElemType data;
struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
**********/
Status IsBSTree(BSTree T)
/* 判别二叉树T是否为二叉排序树。*/
/* 若是，则返回TRUE，否则FALSE */
{
if(T->lchild){
if((T->lchild->data.key)>(T->data.key) || !IsBSTree(T->lchild)) return 0;
}
if(T->rchild){
if((T->rchild->data.key)<(T->data.key) || !IsBSTree(T->rchild)) return 0;
}
return 1;
}
/**********
【题目】编写递归算法，从大到小输出给定二叉排序树
中所有关键字不小于x的数据元素。
二叉排序树的类型BSTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
}BSTNode, *BSTree;
**********/
void OrderOut(BSTree T, KeyType k, void(*visit)(TElemType))
/* 调用visit(T->data)输出 */
{
if(!T) return;
if(T->data.key<k) OrderOut(T->rchild,k,visit); else
{
if(T->rchild) OrderOut(T->rchild,k,visit);
visit(T->data);
if(T->lchild) OrderOut(T->lchild,k,visit);
}
}
/**********
【题目】试写一非递归算法，在二叉查找树T中插入元素e。
二叉查找树的类型BSTree定义如下：
typedef struct {
KeyType key;
... ... // 其他数据域
} TElemType;
typedef struct BSTNode {
TElemType data;
struct BSTNode *lchild,*rchild;
} BSTNode, *BSTree;
**********/
Status InsertBST_I(BSTree &T, TElemType k)
/* 在二叉查找树T中插入元素e的非递归算法 */
{
BSTree now=T,fl;
while(now)
{
fl=now;
if(k.key==now->data.key) break;
if(k.key<now->data.key) now=now->lchild;
else now=now->rchild;
}
if(!now) {
now=(BSTNode*)malloc(sizeof(BSTNode));
now->data=k; now->lchild=now->rchild=NULL;
if(k.key<fl->data.key) fl->lchild=now; else fl->rchild=now;
}
}
/**********
【题目】试编写算法，求二叉树T中结点a和b的最近共同祖先。
二叉链表类型定义：
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
} BiTNode, *BiTree;
可用栈类型Stack的相关定义：
typedef struct {
BiTNode *ptr; // 二叉树结点的指针类型
int tag; // 0..1
} SElemType; // 栈的元素类型
Status InitStack(Stack &S);
Status StackEmpty(Stack S);
int StackLength(SqStack S);
Status Push(Stack &S, SElemType e);
Status Pop(Stack &S, SElemType &e);
Status GetTop(Stack S, SElemType &e);
**********/
void add(Stack &S,BiTree tf)
{
if(tf)
{
SElemType g;
g.tag=0; g.ptr=tf;
Push(S,g);
}
}
void work(Stack &S,BiTree T,TElemType ef)
{
SElemType e;
e.tag=0; e.ptr=T;
Push(S,e);
while(!StackEmpty(S))
{
Pop(S,e);
if(e.tag==0)
{
if(e.ptr->data==ef) return;
e.tag=1; Push(S,e);
add(S,e.ptr->lchild);
} else
if(e.tag==1)
{
e.tag=2; Push(S,e);
add(S,e.ptr->rchild);
}
}
}
BiTree CommAncestor(BiTree T, TElemType a, TElemType b)
/* 求二叉树T中结点a和b的最近共同祖先 */
{
Stack P,Q;
InitStack(P); InitStack(Q);
work(P,T,a); work(Q,T,b);
SElemType pa,qa;
while(StackLength(P)>StackLength(Q)) Pop(P,pa);
while(StackLength(P)<StackLength(Q)) Pop(Q,qa);
while(!StackEmpty(P))
{
Pop(P,pa); Pop(Q,qa);
if(pa.ptr==qa.ptr) return pa.ptr;
}
return NULL;
}
/**********
【题目】在二叉排序树的每个结点中增设一个lsize域，
其值为该结点的左子树中的结点数加1。试编写时间复杂
度为O(logn)的算法，求树中第k小的结点的位置。
二叉排序树的类型BSTree定义如下：
typedef char KeyType;
typedef struct BSTNode {
KeyType key;
struct BSTNode *lchild,*rchild;
int lsize; // 新增域，值为左子树的结点数+1
} BSTNode, *BSTree;
**********/
BSTNode *Ranking(BSTree T, int k)
/* 在含lsize域的二叉排序树T中，*/
/* 求指向T中第k小的结点的指针 */
{
if(!T || k<1) return NULL;
if(T->lsize==k) return T;
if(T->lsize>k) return Ranking(T->lchild,k);
else return Ranking(T->rchild,k-T->lsize);
}
/**********
【题目】假设二叉排序树T的每个结点的平衡因子域bf当前
均为0。试编写算法，求二叉排序树T的深度，并为每个结点
的bf域赋予正确的平衡因子值。
平衡二叉排序树的类型BBSTree定义如下：
typedef char KeyType;
typedef struct BBSTNode {
KeyType key;
int bf; // 平衡因子
struct BBSTNode *lchild,*rchild;
} BBSTNode, *BBSTree;
**********/
int Depth_BF(BBSTree T)
/* 求二叉排序树T的深度，并为每个结点 */
/* 的bf域赋予正确的平衡因子值。 */
{
if(!T) return 0;
int lf=Depth_BF(T->lchild);
int rf=Depth_BF(T->rchild);
T->bf=lf-rf;
if(lf>rf) swap(lf,rf); return rf+1;
}
/**********
【题目】编写平衡二叉排序树的右平衡处理算法。
平衡二叉排序树的类型BBSTree定义如下：
typedef char KeyType;
typedef struct BBSTNode {
KeyType key;
int bf; // 平衡因子
struct BBSTNode *lchild,*rchild;
} BBSTNode, *BBSTree;
可调用下列旋转调整操作：
void L_Rotate(BBSTree &p); // 对最小失衡子树p做左旋调整
void R_Rotate(BBSTree &p); // 对最小失衡子树p做右旋调整
**********/
void RightBalance(BBSTree &T)
/* 实现对二叉树T的右平衡处理 */
{
BBSTree rc,ld;
rc=T->rchild;
switch(rc->bf) {
case RH:
T->bf=rc->bf=EH; L_Rotate(T); break;
case LH:
ld=rc->lchild;
switch(ld->bf) {
case RH:T->bf=LH; rc->bf=EH; break;
case EH:T->bf=rc->bf=EH; break;
case LH:T->bf=EH; rc->bf=RH; break;
}
ld->bf=EH;
R_Rotate(T->rchild);
L_Rotate(T); break;
}
}
