2021学年第15课 数据结构与算法优秀教学课件ppt

这是一份2021学年第15课 数据结构与算法优秀教学课件ppt，文件包含第十五课数据结构与算法ppt、第十五课数据结构与算法教学设计doc等2份课件配套教学资源，其中PPT共19页， 欢迎下载使用。

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