数据结构及应用算法教程（修订版） 数据结构_第7章图和广义表习题.ppt

《数据结构及应用算法教程（修订版） 数据结构_第7章图和广义表习题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图和广义表习题(1)习题7.1:顶点123456入度321221出度022214(2)邻接矩阵123456100000021001003010001400101051000006110110(5)强连通分量:156234(3)邻接表习题7.1:(4)逆邻接表01^12.23.34.45.56.0.3^1.5^2.4^0.0.1.3.4^01.12.23.34.45.56.5.4.5.2^3^2^1^5.1^5.5^习题7.2:01234567890123456789深度优先生成树广度优先生成树习题7.3:intvisited[MAX

2、SIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj){//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p->nextarc)    {      k=p->adjvex;if(!visited[k]&&exist_path_DFS(G,k,j))return1;//i下游的顶点到j有路径}//for}//e

3、lse}//exist_path_DFS习题7.4:(1)邻接矩阵abcdefgha∞23∞∞∞∞∞b2∞∞2∞∞∞∞c3∞∞1∞∞∞∞d∞21∞24∞∞e∞∞∞2∞12∞f∞∞∞41∞21g∞∞∞∞22∞3h∞∞∞∞∞13∞adgfbhce最小生成树adgfbhce习题7.4:(2)邻接表0a.1b.2c.3d.4e.5f.6g.7h.02.32^03.31^12.23^12.21.42.54^32.51.62^34.41.62.71^42.52.73^51.63^Dist[k]bcdefS(终点集)K=120(a,b)MAXMAXMA

4、XMAX{a,b}K=2MAXMAX30(a,b,e)50(a,b,f){a,b,e}K=3MAX45(a,b,e,d)50(a,b,f){a,b,e,d}K=4MAX50(a,b,f){a,b,e,d,f}K=5MAX{a,b,e,d,f,c}习题7.5:习题7.6:561234516234512634512364156234152634152364习题7.7:αABDFGIHCKJEωve0163431131722313444vl0202419837132622313444关键路径:α→G→H→K→J→E→ω边eeelel-eew<α

5、,A>019191<α,B>018186<α,D>016163<α,F>0444<α,G>0003<α,I>06611201966241823191673262383252264231911边eeelel-eew48453232021330101766172698132294132714413130922220931310331321123434010习题7.8

6、:1··1··1··1··1^·1·^1^^0a1·^1··0b1·^0c0d1·^1·^1·^0e表头：(())表尾：(a,((b,c),(),d),(((e))))深度：4习题7.8:1··1·^1··1·^0a1·^1··0b1·^0d1·^1··1··0e1·^1··0e表头：(((a),b))表尾：((((),d),(e,f)))深度：4习题7.9:1··0a0e1··1··1··1^^1··1·^1·^1··1·^1··1·^0d1··1·^0c0b习题7.10:intGList_Getdeph(GListL)//求广义表深度

7、的递归算法{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_Getdeph