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