第15课《数据结构与算法》课件 2021—2022学年浙教版（2020）初中信息技术七年级下册

数据结构与算法 浙教版(2020) 信息技术 七下 1 回顾导入 在辞典/字典中查找一个单词，在电话号码簿中查找一个电话号码，这类操作在生活中经常碰到，一般需要考虑查找效率问题，目标是以较少的步骤或在较短的时间内找到所需的对象。其对应的算法根据数据组织方式的不同而存在差异。 2 回顾导入 算法是解决问题的方法和步骤，而数据结构是算法中所用数据的组织结构。 因此，解决某个问题的算法会根据被处理对象的数据结构不同而发生变化。 3 新知讲解 01 数据组织与算法 在现实中表示一批序列数据，常采用线性表的数据结构来组织与存储。 对线性表的常用操作有访问元素、插入元素、删除元素等。 针对某种操作，其对应的算法根据数据组织方式的不同而存在差异。 4 新知讲解 数组形式存储 以访问元素为例，若要查看超市中某个商品的销售数据，在设计数据结构时，可以将超市中万余种商品的销售数据采用数组或链表来组织，如上图所示。 5 新知讲解 链表形式存储 6 新知讲解 数据结构 数组 链表 组织与存储 访问方式 举例 若采用数组的方式来组织与存储，数据按照一定的顺序存储在连续的物理空间中。 可以通过元素下标来直接访问数组中的某个元素。 例如要查看钢笔的销售数据，若a47存储的是钢笔的销售数据， 则可直接用a47来表示， 相当于访问1次即完成操作。 若采用链表的方式来组织与存储，数据分散地存储在物理空间中。 链表中，访问任意一个元素都必须从第一个节点(或最后一个节点)开始进行按序访问，直到找到指定元素。 例如仍然查看钢笔的销售数据，可以按照“ao➜a1…a46➜a47”的次序访问，即相当于访问48次，操作完成。 如果数据的组织与存储方式不同，那么相同的操作对应的算法一般也不同。 7 开动脑筋 在数组或链表中插入某个元素，分别采用怎样的算法？ 数组 链表 演示 8 新知讲解 02 算法效率 算法效率 时间效率 空间效率 (存储量需求) 时间效率指的是算法的执行时间。(举例) 空间效率(存储量需求) 指的是算法在执行过程中需要的最大存储空间，主要指算法程序运行时占用的内存或外部硬盘存储空间。 9 新知讲解 可见，不同的算法时间效率存在明显的差异。 10 开动脑筋 设计两个不同的算法，实现在数组或链表中删除某个元素，并比较这两个算法的效率。 11 新知讲解 例如：超市购物付款时，当收银员扫描一件商品的条形码时，计算机需要在几万种商品中寻找这件商品，然后显示相应的商品名称和价格。 最简单的方式是将这些数据按序存储在计算机中。 能否设计出高效率的查找算法，取决于这些商品数据的组织及存储方式。 查找时从头开始依次查找商品名称，直到找出正确的商品名称或是找遍整个表均没有找到为止。 这种查找算法，对于一个商品种类不多的超市或许是可行的，但对一个有成千上万种商品的大型超市就不适用了。 12 新知讲解 若这些数据是按商品类别排列的，则可另构建一张商品类别表，采用如图所示的存储结构。 类别 地址 食品 日用品 … 类别 名称 数量 食品 酸奶 1048 … … … 食品 矿泉水 598 日用品 钢笔 2145 … … … 日用品 水杯 622 类别表 数据存储结构 13 新知讲解 查找时，首先在类别表中查找类别 然后根据类别表中的地址到商品登记表中核查商品名称，这样在查找商品登记表时就无须查找其他商品的名称了。 与前一种算法相比，基于这种数据结构的查找算法的时间效率更为高效，但存储类别表则需要额外的存储空间。 14 知识链接 查找(Search) 又称检索， 计算机根据所给条件查找出满足条件的对象，即在存储的一批数据内寻找出一个特定的数据，或者确定在该批数据内是否存在这样的数据。 15 开动脑筋 请例举生活中应用实例？并阐述它的优点？ 16 课堂小结 数据组织与算法 算法效率 数据组织(数据结构)用于解决数据的存储问题，而算法用于处理和分析数据 算法效率分析分为两种:第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间。在计算机发展的早期，计算机的存储容量很小，所以很在乎空间复杂度。但是计算机经过迅速的发展之后，计算机的存储容量已经达到了很高的程度。所以如今已经不需要再关注一个算法的空间复杂度。 17 随堂练习 1.举例说明什么是查找。 2.举例说明算法效率与哪些要素有关。 3.举例说明数据结构与算法的关系。 18 感谢同学们聆听 2022.5 19 新知导入 生活中