1、3.2 数据与结构,必修一 数据与计算博山区实验中学电教中心,各种类型的数据被编码表示成二进制数据，存储到计算机中。在利用计算机解决问题的过程中，这些数据将是最基本的元素。但是，零散孤立的数据是很难被有效利用的。根据所要解决的问题的不同，我们还需要依据数据关系建立合适的结构。采用这些结构将数据组织起来，才能有利于操作和管理，进而更高效地解决实际问题。本节我们将学习表、队列、树、图等数据结构，了 解结构中数据间的关系，在一定的结构上完成算法设计;学会在生活中根据实际问题，建立合适的数据结构，进而运用所学的知识解决问题。,学习目标,熟悉队列结构的概念和特点，能够使用Python语言对队列进行操作。
2、了解树、图结构的基本概念及特点。能够比较不同数据结构的特点，会选用合适的数据结构组织数据解决简单问题。,任务一探究网购订单处理,数据经过采集和数字化后存储在计算机中，是为了便于应用和解决问题。本节我们将围绕“网络购物”项目展开学习，通过项目活动，认识相关数据的组织方法，了解数据之间的关系，理解几种典型的数据结构，为利用数据、实现数据的价值做准备。本项目主要包含“探究网购订单处理”和“探究快递配送过程”两个任务。活动1 了解订单数据 在网上购物时，在我们提交订单后，网页上就会显示订单数据。,利用计算机解决问题的过程，就是将问题中的已知数据输入计算机进行计算，然后输出结果数据的过程。比如，当我们利
3、用网络购买商品时，计算机解决问题的过程就是对订单数据、商品数据等相关数据进行计算的过程。为了方便对数据进行处理，我们可以选择合适的软件工具，根据问题的需要为数据抽象出合适的数据类型，然后对数据进行组织和计算。,数据类型,数据类型用来定义一系列值及应用于这些值的一-系列操作。比如，在Python语言中，有整数、浮点数、字符串、布尔等数据类型。整数类型的范围几乎仅受内存限制，能够进行加、减、乘、除等多种计算操作。大多数程序设计语言都定义了两类数据类型:简单数据类型和复合数据类型。简单数据类型不能分解成更小的数据类型，复合数据类型则由简单数据类型或者复合数据类型组成。在Python语言中，整数、浮点
4、数、字符串、布尔属于简单数据类型，列表、字典等属于复合数据类型。订单数据中的商品名称可以抽象为字符串类型的数据，是一个基本数据项，商品数量可以抽象为整数类型的数据，也是-一个 基本数据项。每个订单数据包括商品名称、单价、数量、金额、收货地址等基本数据项，所以订单数据需要抽象为复合数据类型。如图3.2.1(a)所示的订单数据用Python的列表存储，列表名称为OrderList。OrderList=2374761814130XXX,语文:生命的，文学的，美学的，34.66 列表中前两个数据是字符串类型，最后-项是浮 点数类型。我们还可以把很多订单数据排列在一起，形成订单表，用更复杂的列表存储。,
5、活动2编制订单数据处理程序,网店接受了大量的订单，如何安排发货呢?实际上，网店在处理订单时，一般采取“先下单，先发货”的原则。因此，所有的订单将按照下单的时间顺序放进一个列表中，先放进去的先发货，所有订单排列在一起，像是一群人在排队。下面的Python程序可以实现以下功能:提供“添加订单”“发货”“查看订单列表”“退出”四个操作选项。当我们选择“1”后输入订单数据，程序将订单数据添加到订单数据表中;选择“2”后，程序将当前订单列表中最早进入的数据删除(表示已安排发货处理);选择“3”可以显示当前订单列表中所有的订单数据;选择“4”将结束运行。请你完善下列Python程序，模拟添加订单和发货的过
6、程，了解订单列表的操作过程。,listque=#定义列表listque存储订单x=0while(x!=4):#当x=!4时，执行循环 print(1.添加订单)print(2.发货)print(3.查看订单列表)print(4.退出)x=int(input(输入你的选择:)#输入选择项 if x=1:y=input(输入订单编号:)#输入订单编号 listque.append(y)#在列表listque中添加订单号 elif x=2:if len(listque)=0:#如果订单列表为空 print(订单列表为空)else:print(发货单号:+listque.pop(0)elif x=3:
7、print(等待发货:,listque)#查询列表listque中的订单号 print()input(运行完毕，请按回车键退出.),数据结构与线性数据结构,数据结构是存在特定关系的数据元素的集合。在解决有些问题时，一些相关联的数据将集中在-起，形成一个数据的集合，这种集合能够单独或作为-一个整体被访问和处理。线性数据结构又称为线性表。在线性数据结构中，除首元素没有前趋元素、尾元素没有后继元素外，其他元素都只有一个前趋元素和-一个后继元素，如图3.2.2所示。线性表中数据元素之间是一-对一-的关系。,队列,队列是一种有限制的线性结构，它的数据元素只能在一端依次添加(进队)，在另一端依次删除(出队
8、)。典型的例子如超市里排队付款的队伍。许多程序设计语言定义了复杂数据类型，以实现对数据结构更高层级的抽象。复杂数据类型可以封装并隐藏数据结构中的操作细节，让程序设计者更多地关注数据结构能做什么，便于利用数据结构解决问题。Python中的列表数据类型，可以实现线性结构组织的数据元素的存储和操作。列表的使用者只需要知道列表上有哪些可用的操作，而不需要知道这些操作是如何进行的。比如在上述代码中，listque是列表类型的数据，存放了一组字符串类型的数据，表示订单编号。我们可以通过对应的方法对列表进行操作:pop(0)方法可以删除列表的首元素，append方法可以在列表尾部添加一个数据元素。利用列表，
9、我们可以模拟队列中数据元素进队和出队的操作。,任务二 探究快递配送过程,活动1了 解快递派送线路 每个快递员只负责固定的派送范围，他们从快件派送点领取快件后，分别送往各自负责的快件领取点(比如小区门卫处、单位门卫处)或者具体用户。学校的快递由快递员送件上门后，收发室老师将快件按工作人员部门、学生班级分类摆放，由各班级指定专人取件。现将派送点、学校收发室和收件人用点表示，派送的线路用线段表示，请你尝试在下面框中画出多个快件从派送点到不同收件人所经过的线路。,树结构,树结构是一-种具有层次关系的非线性结构。树是由n(n0)个节点组成的有限集合。若n=0，则称为空树。任何一个非空树均满足以下两个条件
10、:(1)仅有一个称为根的节点;(2)当n0时，其余节点可分为m(m0)个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。在图3.2.3中，节点A为根节点，B、C、D为A的子树的根节点。同理，E、F、G是B的子树的根节点，B是E、F、G的父节点。在树结构中，数据元素之间是一-对多的关系。,快递到达目的地城市后，物流图的结构呈树状,活动2 了解物流网络,图结构,结构是由-组节点(称为顶点)和-组节点间的连线(称为边或弧)构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。图3.2.6表示的是商品从供货点到收货点的派送过程的图结构。图3.2
11、.7也是-个图结构，其中，标为(4“1”的顶点与两条边相连，顶点“4”与“2”“8”“9”相连。在物流网络中，分拨中心、配送中心、货物需求点等可以抽象为图的顶点，城市道路、各级铁路等可以抽象为图的边，如城市以及城市之间的运输道路就是图结构。利用图结构，我们还可以解决物流中的许多问题，如道路网络分析、车辆运营安排等。,活动3 规划取快递最快路线,某同学网购的书已经到达家附近的快递门店，需要他自己去取。不巧的是，这次购买的三本书是三个不同的物流公司派送的。,def dfs(v,vis):global min,s,r,minr vis.add(v)r=r+-+v if vis=set(HABC):s
12、=s+GvH r=r+-+H print(线路+r1:+用时:+str(s)if smin:min=s minr=r s=s-GvH r=r:-2 else:for u in Gv:if u not in vis:s=s+Gvu dfs(u,vis)vis.remove(u)s=s-Gvu r=r:-2 return minG=H:A:2,B:5,C:10,A:H:2,B:4,C:6,B:H:5,A:4,C:4,C:H:10,A:6,B:4min=999s=0r=minr=print(最短用时:+str(dfs(H,set()print(最短用时线路有:+minr1:)print()input
13、(运行完毕，请按回车键退出.),我们可以将该同学家和快递门店的位置抽象成顶点，两个位置间的不行线路抽象成边，边上的值表示步行时间。,从起点出发，把当前可以到达的下一个位置列举出来，再从列举出的新位置出发，继续列举下一步可以到达的位置，以此类推，直到返回起点。我们把所有可能的做法用图形描述，如图3.2.10所示，图下方圆圈中的数值是该走法的总用时。我们发现，分析过程的图形是树结构,树中的节点表示当前所在的位置，边表示选择的线路。利用树结构，我;们能够更清晰地实现不重复、不遗漏地列举所有做法，更利于通过比较得到最优解。,拓展练习数据结构的比较,Thank you goodbye,博山实验中学电教中心制作,
