1 / 12
文档名称:

数据结构课后习题标准答案.doc

格式:doc   大小:154KB   页数:12页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构课后习题标准答案.doc

上传人:phl0420371 2019/12/6 文件大小:154 KB

下载得到文件列表

数据结构课后习题标准答案.doc

文档介绍

文档介绍:数据结构课后****题标准答案————————————————————————————————作者:————————————————————————————————日期: (P235)的无向图,给出:表示该图的邻接矩阵。表示该图的邻接表。图中每个顶点的度。解:邻接矩阵:01110001001100100101011101110101001001**********邻接表: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----NULL;7:4----5----6----NULL;图中每个顶点的度分别为:3,3,3,6,3,3,3。,给出:(1)从顶点1出发,按深度优先搜索法遍历图时所得到的顶点序(2)从顶点1出发,按广度优先法搜索法遍历图时所得到的顶点序列。(1)DFS法:存储结构:本题采用邻接表作为图的存储结构,邻接表中的各个链表的结点形式由类型L_NODE规定,而各个链表的头指针存放在数组head中。数组e中的元素e[0],e[1],…..,e[m-1]给出图中的m条边,e中结点形式由类型E_NODE规定。visit[i]数组用来表示顶点i是否被访问过。遍历前置visit各元素为0,若顶点i被访问过,则置visit[i]:,选择一个与v相邻接且未被访问过的的顶点w访问之,再从w开始进行深度优先搜索。每当到达一个其所有相邻接的顶点都被访问过的顶点,就从最后访问的顶点开始,依次退回到尚有邻接顶点未曾访问过的顶点u,并从u开始进行深度优先搜索。这个过程进行到所有顶点都被访问过,或从任何一个已访问过的顶点出发,再也无法到达未曾访问过的顶点,则搜索过程就结束。另一方面,先建立一个相应的具有n个顶点,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,*q;for(i=1;i<=n;i++)head[i]=NULL;for(i=0;i<m;i++){u=e[i].ver1;v=e[i].ver2;p=(L_NODE*)malloc(sizeof(L_NODE));p->ver=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;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[]){L_NODE*t;visit[u]=1;printf("%4d",u);t=head[u];while(t!=NULL){if(visit[t->ver]==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=4;e[7].ver1=4;e[7].ver2=6;e[8].ver1=4;e[8].ver2=7;e[9].ver1

最近更新

2024年云南省玉溪市安全监控中心招聘16人历年.. 177页

2024年云南省自然资源厅所属事业单位招聘47人.. 177页

2024年兰州职业技术学院单招职业适应性测试题.. 58页

2024年内蒙古包头市直事业单位招聘570人历年高.. 175页

2024年内蒙古法院系统招聘457名书记员历年高频.. 178页

2024年内蒙古锡林郭勒事业单位招370人历年高频.. 177页

脑卒中症状急救措施的科学性和有效性评估 25页

2024年北京市昌平区事业单位招聘262人历年高频.. 176页

产品发货包装方案 4页

2024年吉林省四平市行政职业能力测验题库完美.. 147页

2024年大理农林职业技术学院单招职业适应性测.. 58页

2024年安徽省铜陵市行政职业能力测验题库及参.. 148页

香港高铁一地两检方案 3页

2024年山东省淄博市行政职业能力测验题库(黄.. 148页

2024年山西铁道职业技术学院单招职业适应性测.. 58页

2024年广西玉林市玉州区环境保护局事业单位招.. 89页

2024年广西百色市田阳县统计局招聘3人历年高频.. 90页

2024年广西科技大学图书馆招聘5人历年高频难、.. 90页

2024年广西贵港市事业单位招聘451人历年高频难.. 89页

2024年广西贵港桂平市环境保护局招聘5人历年高.. 89页

2024年广西钦州市钦南区事业单位招聘55人历年.. 88页

2024年江西省萍乡市行政职业能力测验题库加解.. 147页

老人丧事请柬集合6篇 4页

内蒙古兴安盟2022年中考物理试卷【含答案】 11页

生产安全事故管理培训课件 19页

2023年校园足球特色学校主要工作做法及特色汇.. 4页

医院收费管理办法 4页

最新建筑抗震设计规范GB50011-2022强制性条文.. 16页

运算单双公式 3页

S700K道岔故障处理方法 5页