初中信息技术浙教版 (2020)七年级下册第15课 数据结构与算法教学ppt课件

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