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

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