3.2数据与结构（第2课时）课件-2021-2022学年高中信息技术教科版（2019）必修1（15张PPT）

(共15张PPT)
3.2 数据与结构
（第二课时）
框架完整·扁平化呈现·绝对专业·超级吸睛
同学们对于四大名著之一的《红楼梦》并不陌生，里面主要讲述了四大家族的兴衰历程。在《红楼梦》中，主要的故事情节都是以贾家作为主线贯穿的。贾家的人物关系也是错综复杂。
但是，如果用我们所学的知识，将贾家的家谱稍作整理，立马变得清晰明确……
PROJECT PEOFILE
活动1 家谱中“隐藏”的数据结构
温故知新：线性数据结构
结构类型 数据节点之间的关系 生活中相应结构应用举例
栈（线性） 一对一 一摞书、一摞盘子
队列（线性） 一对一 排队（做核酸、过马路、上车、付款）、医院排队就诊、银行叫号
思考.
《红楼梦》中贾家的人物关系显然不能用线性结构来表示，那这是一种什么数据结构呢？它具备什么特点？
知识点1：树结构
树结构是一种具有层次关系的非线性结构。
树是由n个节点组成的有限集合。n=0为空树。
知识点1：树结构
任何一个非空树均满足以下两个条件：
1.仅有一个称为根的节点；
2.当n>0时，其余节点可分为m个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。
树结构中，数据元素之间是一对多的关系。
知识点1：树结构
节点A为根节点；BCD为A的子树的根节点；EFG是B子树的根节点；B是EFG的父节点。
PROJECT PEOFILE
活动2 清明节旅游路线规划
清明节假期临近，小明想利用其中一天假期去几个景点旅游，由于景点分布于不同位置，为了节约时间，减少在路上时间浪费，请你帮他规划一下最优旅游路线。
活动2 清明节旅游路线规划
丽正园
家
嗡嗡乐园
古 城
浮来山
右图是各景点的分布位置图，如果小明从家里出发，选择哪条路线是最佳旅游路线呢？
知识点2：图结构
图结构是由一组节点（称为顶点）和一组节点间的连线（称为边）构成的一种数据结构。
图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。
标号是1的顶点与两条边相连，顶点4与2,8,9相连。
想一想
如何选择最优路径？
我们从起点出发，把当前可以到达的下一个位置列举出来，再从列举出的新位置出发，继续列举下一步可以到达的位置，以此类推，直到返回起点。用树的形式列举。
丽正园
家
嗡嗡乐园
古 城
浮来山
思考.
三种数据结构有什么区别和联系呢？
比一比：数据结构的比较
结构类型 数据节点之间的关系 生活中相应结构应用举例
队列
（线性） 一对一 排队（过马路、上车、付款）
医院排队就诊、银行叫号
树 一对多 行政区划
书的章节目录
磁盘存储结构
域名
图 多对多 全国铁路运输图
高速公路网
电话网、互联网
上机练习
人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊、一捆白菜，来到一条河边。河边只有一条小船，人每次过河最多只能带一样，如果人不在现场，狼就要吃羊，羊就要吃菜。他应该怎样安排过河？请完成下面的树结构分析图，帮他找到可行的过河方案。
提示：约定对象在左岸用0表示，在右岸用1表示。
课堂小结
1.树：非线性结构，包括根节点，孩子节点。一对多的关系。
2.图：包括顶点和边。表示多对多的关系。
3.寻找最优路径：遍历图展开成树，可以找到最优解。