1、第十五课 数据结构与算法 信息技术 七下 数据结构与算法数据结构与算法 程序程序 = =算法算法 + +数据结构数据结构 新知导入新知导入 算法是解决问题方法和步骤，而数据结构是算法中 所用数据的组织结构。因此，解决某个问题的算法 会根据处理对象的数据结构不同而发生变化。 新知讲解新知讲解 01 数据组织与算法 新知讲解新知讲解 编号编号名称名称数量数量类别类别 2000129酸奶1048食品 2003572花生油238食品 2001987钢笔2145日用品 2002876矿泉水598食品 新知讲解新知讲解 在现实中表示一批序列数据,常采用线性表的数据结构来组织与存储。对线性表的常用 操作有访
2、问元素、插人元素、删除元素等。针对某种操作，其对应的算法根据数据组织方 式的不同而存在差异。以访问元素为例，若要查看超市中某个商品的销售数据，在设计数 据结构时，可以将超市中万余种商品的销售数据采用数组或链表来组织。 236104823821455981154 0 45 46 47 48 11023 新知讲解新知讲解 若采用数组的方式来组织与存储，数据按照一定的顺序存储在连续的物理空间中。可以通过元素下标来 直接访问数组中的某个元素，例如要查看钢笔的销售数据，若a47存储的是钢笔的销售数据，则可直接用a47来 表示,相当于访问1次即完成操作。 236104823821455981154 0 4
3、5 46 47 48 11023 head236104823821455981154Null 新知讲解新知讲解 若采用链表的方式来组织与存储,数据分散地存储在物理空间中。链表中,访问任意一个元素都必须从第 一个节点（或最后一个节点）开始进行按序访问，直到找到指定元素，例如仍然查看钢笔的销售数据，可以按 照“a0a1a46a47”的次序访问，即相当于访问48次,操作完成。 如果数据的组织与存储方式不同,那么相同的操作对应的算法一般也不同。 236104823821455981154 0 45 46 47 48 11023 head236104823821455981154Null 新知讲解新知讲
4、解 02 算法效率 新知导入新知导入 算法效率是指算法执行的时间。对于同一个问题， 如果有多个解决问题的算法，那么执行时间短的算 法效率高，反之执行时间长的算法效率低。 新知讲解新知讲解 例如：超市购物付款，当收银员 扫描一件商品的条形码时，计算 机需要在几万种商品寻找这件商 品，然后显示相应的商品名称和 价格。 新知讲解新知讲解 在计算机科学中定义为：在一些（有序的/无序的）数据元 素中，通过一定的方法找出与给定关键字相同的数据元素的 过程叫做查找。也就是根据给定的某个值，在查找表中确定 一个关键字等于给定值的记录或数据元素，又称检索。 新知讲解新知讲解 能否设计出高效率的查找算法，取决于这
5、些商品数据的组织及存储方式。最简单的方式是将这些 数据按序存储在计算机中。查找时从头开始依次查找商品名称，直到找出正确的商品名称或是找 遍整个表均没有找到为止。这种查找算法，对于一个商品种类不多的超市或许是可行的,但对一个 有成千上万种商品的大型超市就不适用了。 如何根据问题设计适合的查找算法？ 新知讲解新知讲解 若这些数据是按商品类别排列的,则可另构建一张商 品类别表，采用如图所示的存储结构。 查找时，首先在类别表中查找类别,然后根据类别表 中的地址到商品登记表中核查商品名称，这样在查 找商品登记表时就无须查找其他商品的名称了。 与前一种算法相比,基于这种数据结构的查找算法的 时间效率更为高
6、效,但存储类别表则需要额外的存储 空间。 知识拓展知识拓展 常用的查找算法： 顺序查找： 在一组数据中，从第一个数据开始，按照这组数据的 排列顺序将每个数据逐个与给定的值进行比较。若某 个数据与给定值相等，则查找成功，找到所查数据的 位置;反之查找不成功。 原始数据：inta=4,6,2,8,1,9,0,3; 要查找数字：8 知识拓展知识拓展 常用的查找算法： 二分法查找： 二分查找又称折半查找，它是一种效率较高的查找 方法。 【二分查找要求】：1.必须采用顺序存储结构2.必 须按关键字大小有序排列。 巩固小结巩固小结 第十五课第十五课 数据结构与算法数据结构与算法 教学设计教学设计 1 教学
7、目标教学目标 1.初步了解数据结构与算法的关系。 2.掌握顺序表和链表的查找方法。 3.通过对日常生活中具体问题的分析，理解数据组织方式对算法的影响，培养学生的计算思维能力。 2 重点难点重点难点 教学重点:顺序表和链表的查找方法。 教学难点:不同的数据结构对算法的选择和效率影响。 3 教学过程教学过程 1、复习引入这节课内容 算法：解决问题的方法和步骤。 数据结构：是算法中所有数据的组织结构。 程序=算法+数据结构 算法是解决问题方法和步骤，而数据结构是算法中所用数据的组织结构。因此，解决某个问题的算 法会根据处理对象的数据结构不同而发生变化。 2、新课讲授 01 数据组织与算法 在现实中表
8、示一批序列数据,常采用线性表的数据结构来组织与存储。对线性表的常用操作有访 问元素、插入元素、删除元素等。针对某种操作，其对应的算法根据数据组织方式的不同而存 在差异。以访问元素为例，若要查看超市中某个商品的销售数据，在设计数据结构时，可以将 超市中万余种商品的销售数据采用数组或链表来组织。 若采用链表的方式来组织与存储,数据分散地存储在物理空间中。链表中,访问任意一个元素都必 须从第一个节点（或最后一个节点）开始进行按序访问，直到找到指定元素，例如仍然查看钢 笔的销售数据，可以按照“a0a1a46a47”的次序访问，即相当于访问 48 次,操作完成。 如果数据的组织与存储方式不同,那么相同的
9、操作对应的算法一般也不同。 02 算法效率 算法效率是指算法执行的时间。对于同一个问题，如果有多个解决问题的算法，那么执行时间 短的算法效率高，反之执行时间长的算法效率低。 例如：超市购物付款，当收银员扫描一件商品的条形码时，计算机需要在几万种商品寻找这件 商品，然后显示相应的商品名称和价格。 查找查找 在计算机科学中定义为：在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关 键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字 等于给定值的记录或数据元素，又称检索。 如何根据问题设计适合的查找算法？ 能否设计出高效率的查找算法，取决于这些商品数据的组
10、织及存储方式。最简单的方式是将这 些数据按序存储在计算机中。查找时从头开始依次查找商品名称，直到找出正确的商品名称或 是找遍整个表均没有找到为止。这种查找算法，对于一个商品种类不多的超市或许是可行的,但 对一个有成千上万种商品的大型超市就不适用了。 2、知识拓展知识拓展 常用的查找算法： 顺序查找： 在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。 若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。 原始数据：inta=4,6,2,8,1,9,0,3; 要查找数字：8 二分法查找： 二分查找又称折半查找，它是一种效率较高的查找方法。 【二分查找要求】：1.必须采用顺序存储结构 2.必须按关键字大小有序排列。
