发布时间 : 星期日 文章数据结构习题答案 耿国华主编 第五章更新完毕开始阅读762b436b561252d380eb6ec1
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(\ 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
分析:层序遍历的问题,一般都是借助队列来完成的,每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.