数据结构第七章课后习题答案

《数据结构第七章课后习题答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构7_1对于图题7.1（P235）的无向图，给出：（1）表示该图的邻接矩阵。（2）表示该图的邻接表。（3）图中每个顶点的度。解：（1）邻接矩阵：0111000100110010010101110111010100100110010001110（2）邻接表：1：2----3----4----NULL;2:1----4----5----NULL;3:1----4----6----NULL;4:1----2----3----5----6----7----NULL;5:2----4----7----NULL;6:3----4----7

2、----NULL;7:4----5----6----NULL;（3）图中每个顶点的度分别为：3，3，3，6，3，3，3。7_2对于图题7.1的无向图，给出：（1）从顶点1出发，按深度优先搜索法遍历图时所得到的顶点序（2）从顶点1出发，按广度优先法搜索法遍历图时所得到的顶点序列。（1）DFS法：存储结构：本题采用邻接表作为图的存储结构，邻接表中的各个链表的结点形式由类型L_NODE规定，而各个链表的头指针存放在数组head中。数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边，e中结点形式由类型E_NODE规定。v

3、isit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0，若顶点i被访问过,则置visit[i]为1.算法分析：首先访问出发顶点v.接着，选择一个与v相邻接且未被访问过的的顶点w访问之，再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点，就从最后访问的顶点开始，依次退回到尚有邻接顶点未曾访问过的顶点u,并从u10数据结构开始进行深度优先搜索。这个过程进行到所有顶点都被访问过，或从任何一个已访问过的顶点出发，再也无法到达未曾访问过的顶点，则搜索过程就结束。另一方面，先建立一个相应的具有n个顶点

4、,m条边的无向图的邻接表。初始化visit数组，使其各个元素置为0，表示图中每个顶点都没被访问过。下面给出程序：#include#defineMAXN50#defineMAXM100typedefstructl_node{intver;structl_node*link;}L_NODE;typedefstructe_node{intver1;intver2;}E_NODE;voidcreat_adj_list(L_NODE*head[],intn,E_NODEe[],intm){inti,u,v;L_NODE*p,

5、*q;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;iver=v;p->link=NULL;if(head[u]==NULL)head[u]=p;else{q=head[u];while(q->link!=NULL)q=q->link;q->link=p;}p=(L_NODE*)malloc(sizeof(L_NODE));p->ver=u;p->link=NULL;

6、if(head[v]==NULL)head[v]=p;else{q=head[v];while(q->link!=NULL)q=q->link;q->link=p;}}}voidinit(intvisit[],intn){inti;for(i=1;i<=n;i++)visit[i]=0;}voiddfs(intu,L_NODE*head[],intvisit[])10数据结构{L_NODE*t;visit[u]=1;printf("%4d",u);t=head[u];while(t!=NULL){if(visit[t->ver]==

7、0)dfs(t->ver,head,visit);t=t->link;}}测试报告：voidmain(){L_NODE*head[MAXN];intvisit[MAXN],n,m,u;E_NODEe[12];e[0].ver1=1;e[0].ver2=3;e[1].ver1=1;e[1].ver2=4;e[2].ver1=1;e[2].ver2=2;e[3].ver1=2;e[3].ver2=4;e[4].ver1=2;e[4].ver2=5;e[5].ver1=3;e[5].ver2=6;e[6].ver1=3;e[6].ver2

8、=4;e[7].ver1=4;e[7].ver2=6;e[8].ver1=4;e[8].ver2=7;e[9].ver1=4;e[9].ver2=5;e[10].ver1=5;e[10].ver2=7;e[11].ver1=6;e[1