数据与结构(第3课时) ppt课件完整版.pptx

3.2 数据与结构,新疆生产建设兵团第二中学|技术教研组,（第3课时）,授课人：徐国道,一、树结构,树是由n（n0）个节点组成的有限集合。若n=0，则称为空树。任何一个非空树均满足以下两个条件：（1）仅有一个称为根的节点。（2）当n0时，其余节点可分为m（m0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。,节点、根（节点）、叶子节点、父节点、子节点、空树、子树等概念。,子树,叶子节点,回顾上节课内容：,二、图结构,图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。,回顾上节课内容：,二、图结构,活动3：规划取快递最快路线,某同学网购的书已经到达家附近的快递门店，需要他自己去取。不巧的是，这次购买的三本书是三个不同的物流公司派送的，他家与各快递门店的位置如图3.2.8所示。该同学估算了在这些地点之间步行需要的时间，详见表3.2.2。,活动3：规划取快递最快路线 代码,走进情境,小徐同学学习效率很高，每个周末总是有时间玩上两个小时的电脑游戏。这一天，小徐同学在玩三国游戏时发现了一个问题，对自己手上大将安排出场次序不同，其战斗力也不同，不同的布阵会直接影响到最后的输赢。如果只有关羽、张飞、赵云三员大将的话，小徐同学很快就算出来有6种布阵方案，他自然能选择出一种最优方案。但他发现他手里的大将最多的时候有十几位，他就不知道有哪些方案了。现在他请你帮他在确定大将名字和总数后，计算并输出每一种布阵方案。,关羽、张飞、赵云三员大将的6种方案为：1、关羽 张飞 赵云 2、关羽 赵云 张飞3、张飞 关羽 赵云4、张飞 赵云 关羽5、赵云 关羽 张飞6、赵云 张飞 关羽,抽象与建模,关羽、张飞、赵云三员大将的6种方案为：1、关羽 张飞 赵云 2、关羽 赵云 张飞3、张飞 关羽 赵云4、张飞 赵云 关羽5、赵云 关羽 张飞6、赵云 张飞 关羽,把游戏中的大将进行编号，比如关羽、张飞、赵云三员大将的编号为1、2、3，则原问题转化为给定数字n求1n的全排列问题。,1 2 31 3 22 1 32 3 13 1 23 2 1,如何求1n的全排列？,问题分析与解答树,全排列问题就是把n个数放在n个位置上如何放的问题。我们可以把位置按1n编号，枚举每个位置上可以放的数。从第1个位置开始放数，放完一个位置再放下一个位置，直到n个位置都放完就可以输出一种方案了。每个位置上可以放数有1n共n个数，但前面位置上已经放过的数就不能再放在当前位置，所以要对放过的数做标记，标记它是否已经放过了。,1,2,3,4,1,2,3,4,算法描述：if 当前位置x总数n：输出一种方案else:枚举当前位置x可以放的所有数if 数i没有在前面的位置用过:标记这个数i把数i记在x位置到下一个位置x+1位置放数把数字i的标记去掉，以便后面的位置可以用这个数,问题分析与解答树,代码实现,回到现实问题,如何为游戏中的大将输出所有可能的方案呢？,还记得给大将编号吗？,如何在Python代码把人名和编号关联起来呢？,列表list的下标和值是不是一种对应关系？,代码实现,思考：,1、如果改为对字母的全排列，你能修改吗？,2、现实问题：你爸爸想买体育彩票超级大乐透，他已经知道了几个数出的概率很高，这几个数他必选，其他数字随机选，你能帮他做出可能的排列方案吗？,End,