数据结构严蔚敏习题册 答案

}

for(p=A;p;p=p->ptr.tp) //重新按逆序排列各子表的顺序 p->ptr.hp=ptr[--i]; }

}//GList_Reverse 5.35

Status Create_GList(GList &L)//根据输入创建广义表L,并返回指针 {

scanf(\ if(ch==' ') {

L=NULL;

scanf(\

if(ch!=')') return ERROR; return OK; }

L=(GList)malloc(sizeof(GLNode)); L->tag=1;

if(isalphabet(ch)) //输入是字母 {

p=(GList)malloc(sizeof(GLNode)); //建原子型表头 p->tag=0;p->atom=ch; L->ptr.hp=p; }

else if(ch=='(') Create_GList(L->ptr.hp); //建子表型表头 else return ERROR; scanf (\

if(ch==')') L->ptr.tp=NULL;

else if(ch==',') Create_GList(L->ptr.tp); //建表尾 else return ERROR; return OK; }//Create_GList

分析:本题思路见书后解答. 5.36

void GList_PrintList(GList A)//按标准形式输出广义表 {

if(!A) printf(\空表

else if(!A->tag) printf(\原子 else {

printf(\

for(p=A;p;p=p->ptr.tp) {

GList_PrintList(p->ptr.hp);

if(p->ptr.tp) printf(\ //只有当表尾非空时才需要打印逗号 }

printf(\ }//else

}//GList_PrintList 5.37

void GList_DelElem(GList &A,int x)//从广义表A中删除所有值为x的原子 {

if(A&&A->ptr.hp) {

if(A->ptr.hp->tag) GList_DelElem(A->ptr.hp,x); else if(!A->ptr.hp->tag&&A->ptr.hp->atom==x) {

q=A;

A=A->ptr.tp; //删去元素值为x的表头 free(q);

GList_DelElem(A,x); } }

if(A&&A->ptr.tp) GList_DelElem(A->ptr.tp,x); }//GList_DelElem 5.39

void GList_PrintElem_LOrder(GList A)//按层序输出广义表A中的所有元素 {

InitQueue(Q);

for(p=L;p;p=p->ptr.tp) EnQueue(Q,p); while(!QueueEmpty(Q)) {

DeQueue(Q,r);

if(!r->tag) printf(\ else

for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r); }//while

}//GList_PrintElem_LOrder

分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想. 第六章 树和二叉树

6.33

int Is_Descendant_C(int u,int v)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0 {

if(u==v) return 1; else {

if(L[v])

if (Is_Descendant(u,L[v])) return 1;

if(R[v])

if (Is_Descendant(u,R[v])) return 1; //这是个递归算法 }

return 0;

}//Is_Descendant_C 6.34

int Is_Descendant_P(int u,int v)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0 {

for(p=u;p!=v&&p;p=T[p]); if(p==v) return 1; else return 0;

}//Is_Descendant_P 6.35

这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的. 6.36

int Bitree_Sim(Bitree B1,Bitree B2)//判断两棵树是否相似的递归算法 {

if(!B1&&!B2) return 1;

else if(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild)) return 1; else return 0; }//Bitree_Sim 6.37

void PreOrder_Nonrecursive(Bitree T)//先序遍历二叉树的非递归算法 {

InitStack(S);

Push(S,T); //根指针进栈 while(!StackEmpty(S)) {

while(Gettop(S,p)&&p) {

visit(p->data); push(S,p->lchild); } //向左走到尽头 pop(S,p);

if(!StackEmpty(S)) {

pop(S,p);

push(S,p->rchild); //向右一步 } }//while

}//PreOrder_Nonrecursive 6.38

typedef struct {

BTNode* ptr;

enum {0,1,2} mark;

} PMType; //有mark域的结点指针类型

void PostOrder_Stack(BiTree T)//后续遍历二叉树的非递归算法,用栈 {

PMType a;

InitStack(S); //S的元素为PMType类型 Push (S,{T,0}); //根结点入栈 while(!StackEmpty(S)) {

Pop(S,a);

switch(a.mark) {

case 0:

Push(S,{a.ptr,1}); //修改mark域

if(a.ptr->lchild) Push(S,{a.ptr->lchild,0}); //访问左子树 break; case 1:

Push(S,{a.ptr,2}); //修改mark域

if(a.ptr->rchild) Push(S,{a.ptr->rchild,0}); //访问右子树 break; case 2:

visit(a.ptr); //访问结点,返回 } }//while

}//PostOrder_Stack

分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作. 6.39

typedef struct {

int data;

EBTNode *lchild; EBTNode *rchild; EBTNode *parent; enum {0,1,2} mark;

} EBTNode,EBitree; //有mark域和双亲指针域的二叉树结点类型 void PostOrder_Nonrecursive(EBitree T)//后序遍历二叉树的非递归算法,不用栈 { p=T; while(p)

switch(p->mark) {

case 0:

p->mark=1;

if(p->lchild) p=p->lchild; //访问左子树 break; case 1:

p->mark=2;

if(p->rchild) p=p->rchild; //访问右子树 break; case 2: visit(p);

p->mark=0; //恢复mark值 p=p->parent; //返回双亲结点 }

}//PostOrder_Nonrecursive

分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历. 6.40

typedef struct {

int data;

PBTNode *lchild; PBTNode *rchild; PBTNode *parent;

} PBTNode,PBitree; //有双亲指针域的二叉树结点类型