（新编）实验六 图的邻接表存储及遍历

《（新编）实验六 图的邻接表存储及遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验六图的邻接表存储及遍历一、实验学时2学时二、背景知识1．图的邻接表存储结构在图的邻接表中，图中每个顶点都建立一个单链表，第i个单链表中的结点数为顶点i的出度。(逆邻接表中，第i个单链表中的结点数为顶点i的入度)邻接表的数据结构描述为：structnode{intvertex;structnode*nextnode;};typedefstructnode*graph;structnodehead[vertexnum];2.图的遍历深度优先遍历（DFS）法：算法步骤：1）初始化：（1）置所有顶点“未访问”标

2、志；（2）打印起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点进栈。2）当栈非空时重复做：（1）取栈顶点；（2）如栈顶顶点存在未被访问过的邻接顶点，则选择第一个顶点做：①打印该顶点；②置顶点为“已访问”标志；③该顶点进栈；否则，当前栈顶顶点退栈。3）结束。广度优先遍历（BFS）法：算法步骤：1)初始化：（1）置所有顶点“未访问”标志；（2）打印起始顶点；（3）置起始顶点“已访问”标志；（4）起始顶点入队。2）当队列非空时重复做：（1）取队首顶点；（2）对与队首顶点邻接的所有未被访问的顶点依次做：①打

3、印该顶点；②置顶点为“已访问”标志；③该顶点入队；否则，当前队首顶点出队。3)结束。三、目的要求1．掌握图的基本存储方法；2．掌握有关图的操作算法并用高级语言实现；3．熟练掌握图的两种搜索路径的遍历方法。四、实验内容1．编写程序实现下图的邻接表表示及其基础上的深度和广度优先遍历。五、程序实例图的邻接表表示法的C语言描述：#include#includestructnode/*图形顶点结构定义*/{intvertex;/*顶点*/structnode*nextnode;/

4、*指下一顶点的指针*/};typedefstructnode*graph;/*图形的结构重定义*/structnodehead[6];/*图形顶点结构数组*//*----------建立图形--------*/voidcreategraph(int*node,intnum){graphnewnode;/*新顶点指针*/graphptr;intfrom;/*边线的起点*/intto;/*边线的终点*/inti;for(i=0;i

5、起点*/to=node[i*2+1];/*边线的终点*//*申请存储新顶点的内存空间*/newnode=(graph)malloc(sizeof(structnode));newnode->vertex=to;/*建立顶点内容*/newnode->nextnode=NULL;/*设定指针初值*/ptr=&(head[from]);/*顶点位置*/while(ptr->nextnode!=NULL)/*遍历至链表尾*/ptr=ptr->nextnode;/*下一个顶点*/ptr->nextnode=newno

6、de;/*插入结尾*/}}/*------主程序:建立图形后,将邻接链表输出------*/voidmain(){graphptr;intnode[12][2]={{1,2},{2,1},/*边线数组*/{1,3},{3,1},{2,3},{3,2},{2,4},{4,2},{3,5},{5,3},{4,5},{5,4}};inti;for(i=1;i<=5;i++){head[i].vertex=i;/*设定顶点值*/head[i].nextnode=NULL;/*清除图形指针*/}creategraph

7、(*node,12);/*建立图形*/printf("图形的邻接链表内容:");for(i=1;i<=5;i++){printf("顶点%d=>",head[i].vertex);/*顶点值*/ptr=head[i].nextnode;/*顶点位置*/while(ptr!=NULL)/*遍历至链表尾*/{printf("%d",ptr->vertex);/*输出顶点内容*/ptr=ptr->nextnode;/*下一个顶点*/}printf("");/*换行*/}}1991年全国硕士研究生入学统一考

8、试中医综合真题及答案一、A型题：每一道考题下面都有A、B、C、D、E5个备选答案，在答题时请选择一个最合适的答案，写在答1.“阴在内，阳之守也，阳在外，阴之使也”，主要说明阴阳之间存在着：A.对立制约B.互根互用C.互为消长D.平衡协调E.互相转化2.与精神意识思维活动关系最密切的是A.心主血脉的生理功能B.肝主疏泄的生理功能C.脾主运化的生理功能D.肺主治节的生理功能E.肾主藏精的生理功能3.肺为“水之上源”的