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