浙教版 (2020)七年级下册第15课 数据结构与算法教案

这是一份浙教版 (2020)七年级下册第15课 数据结构与算法教案，共6页。教案主要包含了数据组织与算法，算法效率等内容，欢迎下载使用。


课题
数据结构与算法
单元
第二单元
学科
信息技术
年级
七年级
学习
目标
知识目标：了解数据结构与算法的关系。
技能目标：理解数据组织方式对算法的影响。
重点
了解数据结构与算法的关系；理解数据组织方式对算法的影响。
难点
理解数据组织方式对算法的影响。
教学过程
教学环节
教师活动
学生活动
设计意图
导入新课
生活中我们会遇到到图书馆去借阅、归还图书，通过电脑扫描能准确的知道图书的所在位置；学校学籍管理员通过电脑可准确查询每个学生的学籍信息。我们知道这些数据处理需要数据结构，但是如果我们改变不同的数据结构来处理相同问题，处理效果是否有变化呢？
思考
激发学生学习兴趣并快速进入学习状态
讲授新课
算法是解决问题的方法和步骤，而数据结构是算法中所用数据的组织结构。
因此，解决某个问题的算法会根据被处理对象的数据结构不同而发生变化。
一、数据组织与算法
在现实中表示一批序列数据，常采用线性表的数据结构来组织与存储。
对线性表的常用操作有访问元素、插入元素、删除元素等。
针对某种操作，其对应的算法根据数据组织方式的不同而存在差异。
以访问元素为例，若要查看超市中某个商品的销售数据，在设计数据结构时，可以将超市中万余种商品的销售数据采用数组或链表来组织，如图所示。
数组形式存储
链表形式存储
若采用数组的方式来组织与存储，数据按照一定的顺序存储在连续的物理空间中。
可以通过元素下标来直接访问数组中的某个元素
例如要查看钢笔的销售数据，若a47存储的是钢笔的销售数据， 则可直接用a47来表示， 相当于访问1次即完成操作。
若采用链表的方式来组织与存储，数据分散地存储在物理空间中。
链表中，访问任意一个元素都必须从第一个节点(或最后一个节点)开始进行按序访问，直到找到指定元素
例如仍然查看钢笔的销售数据，可以按照“a➜a1…a46➜a47”的次序访问，即相当于访问48次，操作完成。
如果数据的组织与存储方式不同，那么相同的操作对应的算法一般也不同。
开动脑筋
在数组或链表中插入某个元素，分别采用怎样的算法?
二、算法效率
解决同一个问题可能会有不同的算法，就如同“一题多解”。
有的算法效率高一些，有的算法效率低一些。
通常，算法效率与时间效率和存储量需求有关。
时间效率指的是算法的执行时间。
对于同一个问题，如果有多个解决问题的算法，那么执行时间短的算法效率高，反之执行时间长的算法效率低。
例如，需要对100000种商品按销售量进行排序处理
用较慢的排序算法(如冒泡排序算法)和较快的算法(如快速排序算法)在同一台计算机上进行处理，时间上要相差几千倍。
可见，不同的算法时间效率存在明显的差异。
存储量需求指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时占用的内存或外部硬盘存储空间。
对于解决同一个问题的多个算法，存储量需求低的算法效率高，存储量需求高的算法效率低。
开动脑筋
设计两个不同的算法，实现在数组或链表中删除某个元素，并比较这两个算法的效率。
例如，超市购物付款时，当收银员扫描一件商品的条形码时，计算机需要在几万种商品中寻找这件商品，然后显示相应的商品名称和价格。
能否设计出高效率的查找算法，取决于这些商品数据的组织及存储方式。
最简单的方式是将这些数据按序存储在计算机中。
查找时从头开始依次查找商品名称，直到找出正确的商品名称或是找遍整个表均没有找到为止。
这种查找算法，对于一个商品种类不多的超市或许是可行的，但对一个有成千上万种商品的大型超市就不适用了。
若这些数据是按商品类别排列的，则可另构建一张商品类别表，采用如图所示的存储结构。
类别表
数据存储结构
查找时，首先在类别表中查找类别
然后根据类别表中的地址到商品登记表中核查商品名称，这样在查找商品登记表时就无须查找其他商品的名称了。
与前一种算法相比，基于这种数据结构的查找算法的时间效率更为高效，但存储类别表则需要额外的存储空间。
知识链接
查找
查找(Search) 又称检索， 计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。
算法的设计，依赖于数据结构。
因此，针对同一个问题，采用不同的数据结构，往往会影响算法的选择和效率。
知识拓展
算法复杂度
算法复杂度是指算法在编写成可执行程序后，运行时所消耗的资源代价，包括时间资源和内存资源。
同一问题可用不同算法解决，而一个算法的优劣将影响到算法乃至程序的效率。
对算法的评价主要从时间复杂度和空间复杂度两个方面来考虑。
一、时间复杂度
算法的时间复杂度一般是指算法的运行时间。
一个算法执行所耗费的时间，理论上是不能算出来的，但是可以基于语句的执行次数进行估算，如果每条语句的执行时间单元相同，那么算法花费的时间与算法中语句的执行次数成正比。
算法的时间复杂度通常用函数O()来描述(简称为大0记法)。
在如图所示的算法中，有一重循环，语句总的执行次数约为2n+3次，则算法中语句的执行次数与问题规模n呈线性增长关系，时间复杂度记为O(n)。
这种时间复杂度一般称为线性时间复杂度。
除了线性时间复杂度，还有常数时间复杂度O(1)、指数时间复杂度O(2")对数时间复杂度O(lg 2n) 等。
二、空间复杂度
与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。
算法执行期间所需要的存储空间包括3个部分：
程序所占的空间；
输入的初始数据所占的存储空间；
算法执行过程中所需要的额外空间。
在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。
算法的复杂度主要由时间和空间复杂度决定，对于同一个算法，当输入量n增加时，程序的运行时间一般也会相应增加。
一般来说，同一个问题的不同解决算法，其中运行时间越短、速度越快的算法，它的时间效率就越高，算法性能也越优异。
算法在运行过程中占用和消耗的存储空间越少，算法的空间性能就越高。
随堂练习
1.举例说明什么是查找。
2.举例说明算法效率与哪些要素有关。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。
学生小组间讨论，共同完成任务，并分组汇报。
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
通过小组合作，加强学生组内团结、共同完成任务
培养学生独立完成练习的能力。
课堂小结
分小组总结归纳，教师补充。
各组汇报总结，其他小组成员做补充。
锻炼学生的总结能力，逻辑思维、语言表达能力。
布置作业
1、举例说明数据结构与算法的关系。
板书
一、数据组织与算法
二、算法效率