《数据结构——用C语言描述》+课后题答案(5)

{ if (p->ltag==1) return(p->rchild)； // 左标记为1时，若p的右子树非空，p的右子树的根p->rchild为p的后继；若右子树为空，p->rchild指向后继

else return(p->lchild); // 左标记为0时，p的左子女p->lchild为p的后继 . } // 算法结束

6.18 bitree *search（b：tree *p）

//在后序线索二叉树中查找给定结点的后序前驱的算法

{ if(p->rtag==0) return(p->rchild); //p有右子女时，其右子女p->rchild是p的后序前驱 else return(p->lchild);

//p的左标记为0，左子女p->lchild是后序前驱, 否则，线索p->lchild指向p的后序前驱 } 6.19

前序序列：ABCDEFGHIJKLMPQRNO 后序序列：BDEFCAIJKHGQRPMNOL 6.21

F D P E J Q K R O N I B A G L C H M

6.22

7,19,2,6,32,3,21,10其对应字母分别为a,b,c,e,f,g,h。

哈夫曼编码：a：0010

b：10 c：00000 d：0001 e：01 f：00001 g：11 h：0011

第七章图（参考答案）

7．1（1）邻接矩阵中非零元素的个数的一半为无向图的边数；

（2）A[i][j]= =0为顶点，I 和j无边，否则j和j有边相通； （3）任一顶点I的度是第I行非0元素的个数。 7．2（1）任一顶点间均有通路，故是强连通； （2）简单路径 V4 V3 V1 V2; （3） 0 1 ∞ 1 ∞ 0 1 ∞ 1 ∞ 0 ∞ ∞ ∞ 1 0 邻接矩阵 V1 V2 V3 V4 邻接表

V4 | V3 |^ V1 | ^ V2 | ^ V3 |^

V1 V2 V3 V4 逆邻接表

7．3（1）邻接表 V1 V2 V3 V4 V5 V6 5 | 6 | 5 | 5 | 3 | 5 | 3 | 1 | ^ 4 | 3 | 1 | 4 | 1 | ^ 6 | 4 | 2 | 1 | ^ 5 | ^ 1 | ^ 4 | 6 | 2 | ^ V1 |^ V3 |^ V1 |^ V4 | ^ V2 | ^ （2）从顶点4开始的DFS序列：V5,V3,V4,V6,V2,V1

（3）从顶点4开始的BFS序列：V4,V5,V3,V6,V1,V2 7．4（1）① adjlisttp g; vtxptr i,j; //全程变量 ② void dfs(vtxptr x)

//从顶点x开始深度优先遍历图g。在遍历中若发现顶点j，则说明顶点i和j间有路径。 { visited[x]=1; //置访问标记 if (y= =j)

{ found=1;exit(0);}//有通路，退出

else { p=g[x].firstarc;//找x的第一邻接点 while (p!=null)

{ k=p->adjvex;

if （!visited[k]）dfs(k); p=p->nextarc;//下一邻接点 }

}

③ void connect_DFS (adjlisttp g)

//基于图的深度优先遍历策略，本算法判断一邻接表为存储结构的图g种，是否存在顶点i

//到顶点j的路径。设 1<=i ,j<=n,i<>j.

{ visited[1..n]=0;found=0;

scanf (&i,&j); dfs (i);

if (found) printf （” 顶点”,i,”和顶点 ”,j,”有路径 ”）；

else printf （” 顶点”,i,”和顶点 ”,j,”无路径 ”）； }// void connect_DFS (2)宽度优先遍历

全程变量，调用函数与（1）相同，下面仅写宽度优先遍历部分。 void bfs(vtxptr x) //

{ initqueue(q);enqueue(q,x); while (!empty(q));

{ y=delqueue(q); if (y= =j)

{ found=1;exit(0);}//有通路，退出 else {p=g[x].firstarc;//第一邻接点 while (p!=null) {k=p->adjvex;

if (! Visted[k]) enqueue(q,k); p=p->nextarc }

}// if(y= =j)

}//while(!empty(q))

7．5。假定该有向图以邻接表存储，各顶点的邻接点按增序排列 DFS序列：V1,V3,V6,V7,V4,V2,V5,V8

BFS序列：V1,V3,V4,V6,V7,V2,V5,V8

DFS森林 BFS森林 V1 V3 V4 V6 V7

7．6简单回路指起点和终点相同的简单路径。算法基本思想是利用图的遍历，以顶点VK开始，若遍历中再通到VK，则存在简单回路，否则不存在简单回路。 Adjlisttp g ; visited[1..n]=0; Int found =0;//全程变量

Int dfs(btxptr x)

//从k顶点深度优先遍历图g，看是否存在k的简单回路 { visited[x]=1;

V2 V1 V2

V3 V4 V5 V5 V6

V8

V7

V8

p=g[x].firstarc;

while(p!=null) { w=p->adjvex; if(w= =k)

{ found=1;exit(0);}//有简单回路，退出 if (!visited[k] ) dfs(w ); p=p->nextarc; }//while(p!=null) }// dfs

7．7 （1）PRIM算法的最小生成树

2 a c 2 a a d a 1 c b 2 b 2 2 b 2 d a d b 2 e b 2 2 d 1 c e b 2 a 1 c f 1 h c d 2 2 e 2 b 2 2 1 e g 1 f 1 a d 1 1 1 a 1 1 1 h

（2）KRUSKAL算法的最小生成树

d c 1

1 c 1 e g 2 b 2 2 e g a d 1 1 1 a h

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《数据结构——用C语言描述》+课后题答案(5)在线全文阅读。