严蔚敏版数据结构C语言版参考答案第五章(7)

if(!L->tag) return 0; //原子深度为0 else if(!L) return 1; //空表深度为1 m=GList_Getdeph(L->ptr.hp)+1; n=GList_Getdeph(L->ptr.tp); return m>n?m:n; }//GList_Getdeph 5.31

void GList_Copy(GList A,GList &B)//复制广义表的递归算法 {

if(!A->tag) //当结点为原子时,直接复制 {

B->tag=0;

B->atom=A->atom; }

else //当结点为子表时 {

B->tag=1; if(A->ptr.hp) {

B->ptr.hp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.hp,B->ptr.hp); } //复制表头

if(A->ptr.tp) {

B->ptr.tp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.tp,B->ptr.tp); } //复制表尾 }//else

}//GList_Copy 5.32

int GList_Equal(GList A,GList B)//判断广义表A和B是否相等,是则返回1,否则返回0

{ //广义表相等可分三种情况:

if(!A&&!B) return 1; //空表是相等的

if(!A->tag&&!B->tag&&A->atom==B->atom) return 1;//原子的值相等 if(A->tag&&B->tag)

if(GList_Equal(A->ptr.hp,B->ptr.hp)&&GList_Equal(A->ptr.tp,B->ptr.tp)) return 1; //表头表尾都相等 return 0;

}//GList_Equal 5.33

void GList_PrintElem(GList A,int layer)//递归输出广义表的原子及其所在层次,layer表示当前层次 {

if(!A) return;

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

GList_PrintElem(A->ptr.hp,layer+1);

GList_PrintElem(A->ptr.tp,layer); //注意尾表与原表是同一层次 }

}//GList_PrintElem 5.34

void GList_Reverse(GList A)//递归逆转广义表A {

if(A->tag&&A->ptr.tp) //当A不为原子且表尾非空时才需逆转 {

D=C->ptr.hp;

A->ptr.tp->ptr.hp=A->ptr.hp;A->ptr.hp=D; //交换表头和表尾 GList_Reverse(A->ptr.hp);

GList_Reverse(A->ptr.tp); //逆转表头和表尾 }

}//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(\

GList_PrintList(A->ptr.hp); if(A->ptr.tp) {

printf(\

GList_PrintList(A->ptr.tp);

} //只有当表尾非空时才需要打印逗号 printf(\ }//else

}//GList_PrintList

5.37

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

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->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