第五章 数组和广义表.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

　　　　pa=pa->right;
　　　} //pa右移一步
　　　else if(pa->e+pb->e)
　　　{
　　　　pa->e+=pb->e;
　　　　pre=pa;pa=pa->right;
　　　　pb=pb->right;
　　　} //直接相加
　　　else
　　　{
　　　　if(!pre) A.rhead[i]=pa->right;
　　　　else pre->right=pa->right;
　　　　p=pa;pa=pa->right; //从行链表中删除
　　　　if(A.chead[p->j]==p)
　　　　　A.chead[p->j]=cp[p->j]=p->down;
　　　　else cp[p->j]->down=p->down; //从列链表中删除
　　　　free (p);
　　　}//else
　　}//while
　}//for
}//OLMatrix_Add
分析:本题的具体思想在课本中有详细的解释说明.

5.28

void MPList_PianDao(MPList &L)//对广义表存储结构的多元多项式求第一变元的偏导
{
　for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp)
　{
　　if(p->tag) Mul(p->hp,p->exp);
　　else p->coef*=p->exp; //把指数乘在本结点或其下属结点上
　　p->exp--;
　}
　pre->tp=NULL;
　if(p) free (p); //删除可能存在的常数项
}//MPList_PianDao

void Mul(MPList &L,int x)//递归算法,对多元多项式L乘以x
{
　for(p=L;p;p=p->tp)
　{
　　if(!p->tag) p->coef*=x;
　　else Mul(p->hp,x);
　}
}//Mul
　　
5.29

void MPList_Add(MPList A,MPList B,MPList &C)//广义表存储结构的多项式相加的递归算法
{
　C=(MPLNode*)malloc(sizeof(MPLNode));
　if(!A->tag&&!B->tag) //原子项,可直接相加
　{
　　C->coef=A->coef+B->coef;
　　if(!C->coef)
　　{
　　　free(C);
　　　C=NULL;
　　}
　}//if
　else if(A->tag&&B->tag) //两个多项式相加
　{
　　p=A;q=B;pre=NULL;
　　while(p&&q)
　　{
　　　if(p->exp==q->exp)
　　　{
　　　　C=(MPLNode*)malloc(sizeof(MPLNode));
　　　　C->exp=p->exp;
　　　　MPList_Add(A->hp,B->hp,C->hp);
　　　　pre->tp=C;pre=C;
　　　　p=p->tp;q=q->tp;
　　　}
　　　else if(p->exp>q->exp)
　　　{
　　　　C=(MPLNode*)malloc(sizeof(MPLNode));
　　　　C->exp=p->exp;
　　　　C->hp=A->hp;
　　　　pre->tp=C;pre=C;
　　　　p=p->tp;
　　　}
　　　else
　　　{
　　　　C=(MPLNode*)malloc(sizeof(MPLNode));
　　　　C->exp=q->exp;
　　　　C->hp=B->hp;
　　　　pre->tp=C;pre=C;
　　　　q=q->tp;
　　　}
　　}//while
　　while(p)
　　{
　　　C=(MPLNode*)malloc(sizeof(MPLNode));
　　　C->exp=p->exp;
　　　C->hp=p->hp;
　　　pre->tp=C;pre=C;
　　　p=p->tp;
　　}
　　while(q)
　　{
　　　C=(MPLNode*)malloc(sizeof(MPLNode));
　　　C->exp=q->exp;
　　　C->hp=q->hp;
　　　pre->tp=C;pre=C;
　　　q=q->tp;
　　} //将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题
　}//else if
　else if(A->tag&&!B->tag) //多项式和常数项相加
　{
　　x=B->coef;
　　for(p=A;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 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("%d %d\n",A->atom,layer);
　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("%c",&ch);
　if(ch==' ')
　{
　　L=NULL;
　　scanf("%c",&ch);
　　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 ("%c",&ch);
　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("%d",A->atom);//原子
　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("%d",r->atom);
　　else
　　　for(r=r->ptr.hp;r;r=r->ptr.tp) EnQueue(Q,r);
　}//while
}//GList_PrintElem_LOrder

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