1、信息技术备课组3.2 数据与结构数据与结构本节课学习目标本节课学习目标u熟悉队列结构的概念和特点，能使用python语言对队列进行操作u了解树、图结构的基本概念及特点u能够比较不同数据结构的特点，选用合适的数据结构组织数据解决简单问题信息技术备课组3.2 数据与结构数据与结构n活动活动1（探究网购订单处理）了解订单数据。在网上购物时，我们提交订单后，网页上就会显示订单数据。请根据你自己的购物订单数据填写下表网站名称订单中的数据Python中对应的数据类型商品名称字符串单价浮点型数量整型姓名字符串是否团员布尔型出生日期日期型信息技术备课组3.2 数据与结构数据与结构n数据类型数据类型 用来定义一
2、系列值及应用于这些值的一系列操作。在Python中，有整数、浮点数、字符串、布尔、日期等数据类型。这些都是简单数据类型简单数据类型。还有一种叫复合数据类型复合数据类型，它是由简单数据类型或者复合数据类型组成的，如列表、字典等都属于复合数据类型。如：orderList=”2374761814130”,”语文：生命的，文学的，美学的”,34.66 列表名为orderList，前2项是字符串类型，最后一项是浮点数类型。信息技术备课组3.2 数据与结构数据与结构n数据结构数据结构 是存在特定关系的数据元素的结合。在解决有些问题时，一些相关联的数据将集中在一起，形成一个数据的集合，这种集合能够单独或作为
3、一个整体被访问和处理。常见的数据结构有：栈、队列、树、图等。线性数据结构线性数据结构又称为线性表。在线性数据结构中，除了首元素没有前驱元素、尾元素没有后继元素外，其他元素都只有一个前驱元素和一个后继元素。元素之间是一对一一对一的关系。信息技术备课组3.2 数据与结构数据与结构n队列队列 是一种有限制的线性结构，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队）。类似于在超市里排队付款的队伍。在在pythonpython中的列表数据类型，可以实现线性结构组织的数据元中的列表数据类型，可以实现线性结构组织的数据元素的存储和操作。用列表的素的存储和操作。用列表的pop(0)pop(0)
4、方法可以删除列表的首元素，方法可以删除列表的首元素，appendappend方法可以在列表尾部添加一个数据元素。利用列表模拟队列方法可以在列表尾部添加一个数据元素。利用列表模拟队列中数据元素的进队和出队操作。中数据元素的进队和出队操作。信息技术备课组3.2 数据与结构数据与结构n活动活动2（了解快递派送路线）每个快递员只负责固定的派送范围，他们从快件派送点领取快件后，分别送往各自负责的快件领取点。现将派送点、学校收发室和收件人用点表示，派送的线路用线段表示，请你尝试在下框中画出多个快件从派送点到不同收件人所经过的路线。信息技术备课组3.2 数据与结构数据与结构n树树 树结构是一种具有层次关系的
5、非线性结构。树是由n个节点组成的有限集合。N=0为空树。任何一个非空树均满足以下两个条件：1.仅有一个称为根的节点；2.当n0时，其余节点可分为m个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。树结构中，数据元素之间是一对多一对多的关系。节点A为根节点根节点；BCD为A的子树的根节点；EFG是B子树的根节点；B是EFG的父节点。信息技术备课组3.2 数据与结构数据与结构快递到达目的地城市后，物流图的结构呈树状。信息技术备课组3.2 数据与结构数据与结构n活动活动3（了解物流网络）由于需要综合考虑运营成本，商品在城市间运输的路线是需要计算和规划的。请尝试用圆圈表示城市，用线段表示城
6、市之间的送达关系，将图补充完整。信息技术备课组3.2 数据与结构数据与结构n图图 图结构是由一组节点（称为顶点顶点）和一组节点间的连线（称为边边）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多多对多的关系。标号是1的顶点与两条边相连，顶点4与2,8,9相连。信息技术备课组3.2 数据与结构数据与结构n活动活动4（规划最优路线）某同学网购的书已经到达家附近的快递点，需要他自己去取。这次购买的三本书是3个不同的物流公司，他家与快递点的位置如下。到个快递点需要的时间如表所示。信息技术备课组3.2 数据与结构数据与结构n活动活动4 请你帮他规划最省时间的路
7、线。我们可以将同学家和快递点抽象成顶点，步行路线抽象为边，边上的值表示步行时间。构成图。我们从起点出发，把当前可以到达的下一个位置列举出来，再从列举出的新位置出发，继续列举下一步可以到达的位置，以此类推，直到返回起点。用树的形式列举。信息技术备课组3.2 数据与结构数据与结构n活动活动4 利用树的结构可以实现不重复、不遗漏的列举所有做法，更利于通过比较得到最优解。信息技术备课组3.2 数据与结构数据与结构请分析队列、树、图三种结构的区别。结构类型数据节点之间的关系生活中相应结构应用举例队列（线性）一对一排队（过马路、上车、付款）医院排队就诊、银行叫号树一对多行政区划书的章节目录磁盘存储结构域名
8、图多对多全国铁路运输图高速公路网电话网、互联网信息技术备课组3.2 数据与结构数据与结构 人、狼、羊、菜过河问题：有一个人带着一只狼、一只羊、一捆白菜，来到一条河边。河边只有一条小船，人每次过河最多只能带一样，如果人不在现场，狼就要吃羊，羊就要吃菜。他应该怎样安排过河？请完成下面的树结构分析图，帮他找到可行的过河方案。提示：约定对象在左岸用0表示，在右岸用1表示。信息技术备课组3.2 数据与结构数据与结构n数据结构：是存在特定关系的数据元素的集合。n线性结构：有前驱元素和后继元素，一对一的关系。n队列：一种特殊的线性结构，只能在一端添加数据叫进队，在另一端删除数据叫出队。n树：非线性结构，包括根节点，孩子节点。一对多的关系。n图：包括顶点和边。表示多对多的关系。n寻找最优路径：遍历图展开成树，可以找到最优解。
