if(p->tp->exp==0) p->tp->coef+=x; //当多项式中含有常数项时,加上常数项 if(!p->tp->coef) {
free(p->tp); p->tp=NULL; } else {
q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q;
} //否则新建常数项,下同 }//else if else {
x=A->coef;
for(p=B;p->tp->tp;p=p->tp);
if(p->tp->exp==0) p->tp->coef+=x; if(!p->tp->coef) {
free(p->tp); p->tp=NULL; } else {
q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q; } }//else
}//MPList_Add 5.30
int GList_Getdeph(GList L)//求广义表深度的递归算法 {
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
分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.
第六章 树和二叉树
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))
