新教科版高中信息技术 必修1课件 3.2 数据与结构（第二课时） PPT课件.pptx

3.2数据与结构第3 单元第二课时学习目标★了解树、图结构的基本概念及其特点。★根据数据结构的特点，会选用合适的数据结构组织数据解决简单的问题。【教学重点】数据结构中的树结构和图结构。【教学难点】数据结构中的树结构和图结构。数据结构数据结构是存在特定关系的数据元素的集合。在解决有些问题时，些相关联的数据将集中在一起，形成一个数据的集合，这种集合能够单独或作为一个整休被访问和处理。线性数据结构线性数据结构又称为线性表。在线性数据结构中，除首元素没有前趋元素、尾元素没有后继元素外，其他元素都只有个后继元素。队列队列是一种有限制的线性结构，它的数据元素只能在一端一次添加（进队），在另一端依次删除（出队）。HACEFBDGalphabat = [A，B，C，D，E，F，G，H]我们可以通过对应的方法对列表进行操作：pop(0)方法可以删除列表的首元素，append方法可以在列表尾部添加一个数据;例如：结尾添加字母“I”：alphabat.append(“I”)；删除首字母“A”：alphabat.pop(0)活动1 了解快递派送线路每个快递员只负责固定的派送范围，他们从快件派送点领取快件后，分别送往各自负责的快件领取点（比如小区门卫处、单位门卫处）或者具体用户。树结构树结构是一种具有层次关系的非线性结构。 树是由n(n≥0)个节点组成的有限集合。若n = 0, 则称为空树。任何一个非空树均满足以下两个条件：（1）仅有一个称为根的节点；（2）当n0时，其余节点可分为m(m≥0)个互不相交的有限集合，其中每个集合又是一棵树， 并称为根的子树。1.A是B，C，D的根节点，B，C，D是A的子树；2.B是E，F，G的根节点，E，F，G是B的子树；树结构的特点树根结点（简称“根结点”):每一个非空树都有且只有一个被称为根的结点。右下图中，结点A就是整棵树的根结点。树根的判断依据为:如果一个结点没有父结点，那么这个结点就是整棵树的根结点。叶子结点:如果结点没有任何子结点，那么此结点称为叶子结点（叶结点）。例如下右图中，结点K、L、F、G、M、I、J都是这棵树的叶子结点。如何创建图结构的数据？练一练创建图结构的数据：ACBDlist=[“A”] ……………………………………………list=[(“B”,“C”,“D”)] …………JEFGHIlist=[(“E”.“F”），(“G”),(“H”,“I”,“J”)]LKM打印字母“G”怎么办？Print（list[1][0]）活动1 了解物流网络由于需要综合考虑运营成本，商品在城市间运输的路线是需要计算和规划的。 请你查看图3.2.5中的物流过程，尝试用圆圈表示城市，用线段表示城市之间的送达关系，将图3.2.6补充完整，了解商品配送 的路线特点。泰州长沙南京图结构图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连， 图结构中数据元素之间是多对多的关系。标为“ 1” 的顶点与两条边相连， 顶点“4”与2“，”8“ ，9相连。图结构的应用场景在物流网络中， 分拨中心、配送中心、货物需求点等可以抽象为图的顶点， 城市道路、各级铁路等可以抽象为图的边， 如城市以及城市之间的运输道路就是图结构。 利用图结构， 我们还可以解决物流中的许多问题， 如道路网络分析、车辆运营安排等。活动3 规划取快递最快路线某同学网购的书已经到达家附近的快递门店，需要他自己去取。不巧的是， 这次购买的三本书是三个不同的物流公司派送的，他家与各快递门店的位置如右图所示。该同学估算了在这些地点之间步行需要的时间， 详见表3.2.2 。活动3 规划取快递最快路线请你帮他规划最省时的路线， 然后设计算法解决问题并在下框中描述你的算法。从起点出发，把当前可以到达的下一个位置列举出来，再从列举出的新位置出发，继续列举下一步可以到达的位置，以此类推，直到返回 起点。 Python中的复合数据类型我们发现分析过程的图形是树结构，树中的节点表示当前所在的位置， 边表示选择的线路。利用树结构，我们能够更清晰地实现不重复、不遗漏地列举所有做法，更利千通过比较得到最优解。请分析队列、树、 图三种结构的区别， 并将结果填在表中结构类型数据（节点）之间的关系生活中相应结构应用举例队列（线性）一对一排队树一对多行政区划、书的目录结构图多对多全国航运图、铁路运输等课堂小结集合结构线性结构（队列）数据结构树结构图结构数据与结构线性结构：排队数据结构举例树结构：行政区划图结构：交通运输