《第15课 数据结构与算法》精品课件.pptxVIP

信息技术七下第十五课数据结构与算法

数据结构与算法

程序=算法+数据结构

算法是解决问题方法和步骤，而数据结构是算法中所用数据的组织结构。因此，解决某个问题的算法会根据处理对象的数据结构不同而发生变化。新知导入

编号名称数量类别…………2000129酸奶1048食品2003572花生油238食品2001987钢笔2145日用品2002876矿泉水598食品…………新知讲解

在现实中表示一批序列数据,常采用线性表的数据结构来组织与存储。对线性表的常用操作有访问元素、插人元素、删除元素等。针对某种操作，其对应的算法根据数据组织方式的不同而存在差异。以访问元素为例，若要查看超市中某个商品的销售数据，在设计数据结构时，可以将超市中万余种商品的销售数据采用数组或链表来组织。236……10482382145598……115404546474811023新知讲解

若采用数组的方式来组织与存储，数据按照一定的顺序存储在连续的物理空间中。可以通过元素下标来直接访问数组中的某个元素，例如要查看钢笔的销售数据，若a47存储的是钢笔的销售数据，则可直接用a47来表示,相当于访问1次即完成操作。236……10482382145598……115404546474811023head?2361048?238?2145?5981154Null……新知讲解

若采用链表的方式来组织与存储,数据分散地存储在物理空间中。链表中,访问任意一个元素都必须从第一个节点（或最后一个节点）开始进行按序访问，直到找到指定元素，例如仍然查看钢笔的销售数据，可以按照“a0→a1…a46→a47”的次序访问，即相当于访问48次,操作完成。如果数据的组织与存储方式不同,那么相同的操作对应的算法一般也不同。236……10482382145598……115404546474811023head?2361048?238?2145?5981154Null……新知讲解

算法效率是指算法执行的时间。对于同一个问题，如果有多个解决问题的算法，那么执行时间短的算法效率高，反之执行时间长的算法效率低。新知导入

例如：超市购物付款，当收银员扫描一件商品的条形码时，计算机需要在几万种商品寻找这件商品，然后显示相应的商品名称和价格。新知讲解

在计算机科学中定义为：在一些（有序的/无序的）数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素，又称检索。新知讲解

能否设计出高效率的查找算法，取决于这些商品数据的组织及存储方式。最简单的方式是将这些数据按序存储在计算机中。查找时从头开始依次查找商品名称，直到找出正确的商品名称或是找遍整个表均没有找到为止。这种查找算法，对于一个商品种类不多的超市或许是可行的,但对一个有成千上万种商品的大型超市就不适用了。如何根据问题设计适合的查找算法？新知讲解

若这些数据是按商品类别排列的,则可另构建一张商品类别表，采用如图所示的存储结构。查找时，首先在类别表中查找类别,然后根据类别表中的地址到商品登记表中核查商品名称，这样在查找商品登记表时就无须查找其他商品的名称了。与前一种算法相比,基于这种数据结构的查找算法的时间效率更为高效,但存储类别表则需要额外的存储空间。新知讲解

常用的查找算法顺序查找：在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。原始数据：int[]a={4,6,2,8,1,9,0,3};要查找数字：8知识拓展

常用的查找算法二分法查找：二分查找又称折半查找，它是一种效率较高的查找方法。

【二分查找要求】1.必须采用顺序存储结构2.必须按关键字大小有序排列。知识拓展

巩固小结