數(shù)據(jù)結(jié)構(gòu)習(xí)題答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)習(xí)題答案if(p->tp->exp==0)p->tp->coef+=x;//當(dāng)多項(xiàng)式中含有常數(shù)項(xiàng)時(shí),加上常數(shù)項(xiàng)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;

}//否則新建常數(shù)項(xiàng),下同}//elseifelse{

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_Add5.30

intGList_Getdeph(GListL)//求廣義表深度的遞歸算法{

if(!L->tag)return0;//原子深度為0elseif(!L)return1;//空表深度為1m=GList_Getdeph(L->ptr.hp)+1;n=GList_Getdeph(L->ptr.tp);returnm>n?m:n;}//GList_Getdeph5.31

voidGList_Copy(GListA,GList

B->atom=A->atom;}

else//當(dāng)結(jié)點(diǎn)為子表時(shí){

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

B->ptr.hp=malloc(sizeof(GLNode));GList_Copy(A->ptr.hp,B->ptr.hp);}//復(fù)制表頭if(A->ptr.tp){

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

}//GList_Copy5.32

intGList_Equal(GListA,GListB)//判斷廣義表A和B是否相等,是則返回1,否則返回0

{//廣義表相等可分三種狀況:

if(!A//空表是相等的

if(!A->tag//原子的值相等if(A->tag//表頭表尾都相等return0;

}//GList_Equal5.33

voidGList_PrintElem(GListA,intlayer)//遞歸輸出廣義表的原子及其所在層次,layer表示當(dāng)前層次{

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

voidGList_Reverse(GListA)//遞歸逆轉(zhuǎn)廣義表A{

if(A->tag

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

GList_Reverse(A->ptr.tp);//逆轉(zhuǎn)表頭和表尾}

}//GList_Reverse5.35

StatusCreate_GList(GList

scanf(\

if(ch!=')')returnERROR;returnOK;}

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

elseif(ch=='(')Create_GList(L->ptr.hp);//建子表型表頭elsereturnERROR;scanf(\

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

elseif(ch==',')Create_GList(L->ptr.tp);//建表尾elsereturnERROR;returnOK;}//Create_GList

分析:此題思路見書后解答.5.36

voidGList_PrintList(GListA)//按標(biāo)準(zhǔn)形式輸出廣義表{

if(!A)printf(\空表

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

printf(\

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

printf(\

GList_PrintList(A->ptr.tp);

}//只有當(dāng)表尾非空時(shí)才需要打印逗號(hào)printf(\}//else

}//GList_PrintList5.37

voidGList_DelElem(GListelseif(!A->ptr.hp->tag

A=A->ptr.tp;//刪去元素值為x的表頭free(q);

GList_DelElem(A,x);}

if(A->ptr.tp)GList_DelElem(A->ptr.tp,x);}//GList_DelElem5.39

voidGList_PrintElem_LOrder(GListA)//按層序輸出廣義表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

分析:層序遍歷的問(wèn)題,一般都是借助隊(duì)列來(lái)完成的,每次從隊(duì)頭取出一個(gè)元素的同時(shí)把它下一層的孩子插入隊(duì)尾.這是層序遍歷的基本思想.

第六章樹和二叉樹

6.33

intIs_Descendant_C(intu,intv)//在孩子存儲(chǔ)結(jié)構(gòu)上判斷u是否v的子孫,是則返回1,否則返回0{

if(u==v)return1;else{

if(L[v])

if(Is_Descendant(u,L[v]))return1;if(R[v])

if(Is_Descendant(u,R[v]))return1;//這是個(gè)遞歸算法}

return0;

}//Is_Descendant_C6.34

intIs_Descendant_P(intu,intv)//在雙親存儲(chǔ)結(jié)構(gòu)上判斷u是否v的子孫,是則返回1,否則返回0{

for(p=u;p!=vp=T[p]);if(p==v)return1;elsereturn0;

}//Is_Descendant_P6.35

這一題根本不需要寫什么算法,見書后解釋:兩個(gè)整數(shù)的值是相等的.6.36

intBitree_Sim(BitreeB1,BitreeB2)//判斷兩棵樹是否相像的遞歸