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