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