数据结构-资源试题库及解析《数据结构》期末考试试卷E卷-简答题4-配套说课稿.docx

大数据技术与应用专业教学资源库 《数据结构》课程说课稿 《数据结构》期末考试试卷E卷-简答题4 主讲：章万静  序号 PPT 说课稿 幻灯片 1 大家好。我是《数据结构》课程的主讲教师——章老师。 下面我们开始重点分析试卷E中的题目。 幻灯片 2 我们来看一下简答题。 幻灯片 3 简答题的第4题。 请写出下面有向图的邻接表。这道题5分。 我们来看看这个有向图，有向图有5个顶点，8条有向边。 幻灯片 4 在使用邻接表存储有向图的时候，要注意以下两点： 1、使用一个一维数组按顺序存放全部顶点vi的信息。 2、每个顶点vi后面链接着邻接于vi的所有顶点链接成的一个单链表。 下面，我们来用邻接表存储有向图。 第一步，有向图的5个顶点， 按顺序存储在一个一维数组中。顶点A存储在数组下标为0的空间里，顶点B存储在数组下标为1的空间里，顶点C存储在数组下标为2的空间里，顶点D存储在数组下标为3的空间里，顶点E存储在数组下标为4的空间里。 第二步，有向图有8条有向边。 以顶点A为始点的边有2条：A到B一条边，B存储在数组的下标为1，以下标1构建一个新的链结点；A到E一条边，E存储在数组的下标为4，以下标4构建一个新的链结点；这2个链结点构建一个单链表，直接链接在顶点A的后面。 以顶点B为始点的边没有，顶点B的后面没有链接一个单链表。 以顶点C为始点的边有4条：C到A一条边，A存储在数组的下标为0，以下标0构建一个新的链结点；C到B一条边，B存储在数组的下标为1，以下标1构建一个新的链结点； C到D一条边，D存储在数组的下标为3，以下标3构建一个新的链结点；C到E一条边，E存储在数组的下标为4，以下标4构建一个新的链结点；这4个链结点构建一个单链表，直接链接在顶点C的后面。 以顶点D为始点的边有1条：D到C一条边，C存储在数组的下标为2，以下标2构建一个新的链结点；这1个链结点构建一个单链表，直接链接在顶点D的后面。 以顶点E为始点的边有1条：E到D一条边，D存储在数组的下标为3，以下标3构建一个新的链结点；这1个链结点构建一个单链表，直接链接在顶点E的后面。 注意，每条单链表后面一定要存储一个空指针，表示单链表到此结束，后面没有其他的链结点了。 这样，有向图，5个顶点，8条有向边，采用邻接表表示如图所示。 幻灯片 5 本次微课就介绍到这里，希望大家好好理解与掌握。谢谢观看。