课程名称 数据结构14

《课程名称 数据结构14》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程名称数据结构14授课题目图有向图授课日期2003年11月26日授课班级生物医学工程授课时数4授课方式理论课授课重点、难点1.有向图及其表示方法：邻楼表，邻楼矩阵2.图的遍历，与树的遍历及线性3.掌握先深搜索与先广搜索授课内容、教具与时间分配授课内容、教具与时间分配第五章图51.1有向图及其表示方法(存储方法)(P127)图5.1有向图顶点的集合V={1,2,3,4},顶点表示对象弧的集合E={（1，2），（1，3），（2，4），（3，2），（4，3）}对象之间的关系图G=（V，E）有序对、相邻：一条弧：v→w，v为弧的尾，w为弧的头，是顶点v和w的有序对，w和v是相邻的。①→②≠②→①，

2、故而称为有向图。路经：顶点序列路径长途：弧的条数简单路径：简单环路：标号有向图：图5.2，顶点、弧附加信息无向图：若图中的边是顶点的无序对，则称此图为无向图。无向图中顶点间的联系不用→表示。5．1．2邻接矩阵P127一、邻接矩阵是有向图的一种表示方法（存储方法），是二维数组方法。二、图G=（V，E），V={1，2，3……n}用邻接矩阵表示有向图：ary〔i〕〔j〕行列有向图标号有向图i→j1a无0空格（布尔矩阵）0,1元素10对应图5.1对应图5.2三、函数adjmatrix建立图的邻接矩阵，返回图的顶点个数。9输入方法：v1v2weight=110=1210③④……=000输入结束四、函数

3、prmatrix打印邻接矩阵。5.1.3邻接表一、图的另一种表示方法(存储方法)，是链接方法二、对图中的任一顶点，由此顶点出发的全部相邻顶点用一个向前链表表示，向前链表的前后次序不影响图顶点之间的相互联系。向前链表的表头结点，构成一个数组list[]，表头结点有信息场和链场组成，信息场另作它用。图5.3p128。123两者等价132一、函数adjlist建立有向图邻接表，返回图的顶点个数。二、函数pradjlist打印邻接表。对p.128graph.h的说明1.#include"llist.h"p.392.adjmatrix(matrix)建立有向图(或无向图)邻接矩阵，返回顶点个数。实参是

4、MAX×MAX二维数组名。二维数组matrix[][MAX]是邻接矩阵。输入图的顶点个数。v1v2weight=110对矩阵的每个元素赋值INFIN(9999)。v1v2weight=1210用循环语句向矩阵输入数据，以下图为例：v1v2weight=13910v1v2weight=220①②......v1v2weight=0009输入完毕，循环结束。③④3.prmatrix(mat,n)打印邻接矩阵。实参是已生成的邻接矩阵二维数组的数组名，和图的顶点个数。printf((mat[i][j])==INFIN)?"t":"%d",mat[i][j])；printf("")；如果矩阵元素

5、是INFIN不打印否则打印矩阵元素值即weight4.adjlist(list)建立有向图的邻接表，返回图的顶点个数。实参是大小为MAX的结构体数组变量。list[]是结构体数组变量。输入图的顶点个数。list[]赋初值。数据场目前暂空，也可供某些操作存放一定的标志。顶点标号以p.127图5.1为例，用循环语句输入数据建立邻接表：数组下标v1v2=12或v1v2=131v1v2=13v1v2=122v1v2=243v1v2=324v1v2=43v1v2=00输入完毕，循环结束。5.pradjlist(list，n)打印邻接表数据场的值。实参是已生成的邻接表的表头结点所构成的数组的数组名，和图

6、的顶点个数。以p.127图5.1为例。6.参考p.30，补写push(arg)和pop()。参考p.40inser(arg)和delete()补写engqueue(arg)和dequeue()。NODE*front=NULL,*rear=NULL;enqueue(arg)intarg;{NODE*ptr;ptr=getnode(NODE);ptr->info=arg;ptr->link=NULL;if(front==NULL)front=ptr;elserear->link=ptr;rear=ptr;}dequeue(){NODE*ptr;intvar;if(front==NULL)retu

7、rn(-1);ptr=front;front=ptr->link;var=ptr->info;free(ptr);if(front==NULL)rear=NULL;return(var)}5.2有向图的遍历图遍历的定义：p130图的遍历比树的遍历要复杂，从树根到树中的每个结点只有一条路径，而从图的起始点到达图中的每个顶点可能存在着多条路径。当顺着图中的一条路径访问过某一个顶点后，可能还会顺着另一条路径回到该顶