(共20张PPT)
第十五课
数据结构与算法
信息技术
七下
数据结构与算法
程序=算法+数据结构
新知导入
算法是解决问题方法和步骤，而数据结构是算法中所用数据的组织结构。因此，解决某个问题的算法会根据处理对象的数据结构不同而发生变化。
新知讲解
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
知识拓展
常用的查找算法：
二分法查找：
二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构2.必须按关键字大小有序排列。
巩固小结
谢谢
21世纪教育网（www.21cnjy.com)
中小学教育资源网站
有大把高质量资料？一线教师？一线教研员？
欢迎加入21世纪教育网教师合作团队！！月薪过万不是梦！！
详情请看：
https://www.21cnjy.com/help/help_extract.php中小学教育资源及组卷应用平台
第十五课
数据结构与算法
教学设计
1教学目标
1.初步了解数据结构与算法的关系。
2.掌握顺序表和链表的查找方法。
3.通过对日常生活中具体问题的分析，理解数据组织方式对算法的影响，培养学生的计算思维能力。
2重点难点
教学重点:顺序表和链表的查找方法。
教学难点:不同的数据结构对算法的选择和效率影响。
3教学过程
1、
复习引入这节课内容
算法：解决问题的方法和步骤。
数据结构：是算法中所有数据的组织结构。
程序=算法+数据结构
算法是解决问题方法和步骤，而数据结构是算法中所用数据的组织结构。因此，解决某个问题的算法会根据处理对象的数据结构不同而发生变化。
2、新课讲授
01数据组织与算法
在现实中表示一批序列数据,常采用线性表的数据结构来组织与存储。对线性表的常用操作有访问元素、插人元素、删除元素等。针对某种操作，其对应的算法根据数据组织方式的不同而存在差异。以访问元素为例，若要查看超市中某个商品的销售数据，在设计数据结构时，可以将超市中万余种商品的销售数据采用数组或链表来组织。
在现实中表示一批序列数据,常采用线性表的数据结构来组织与存储。对线性表的常用操作有访问元素、插人元素、删除元素等。针对某种操作，其对应的算法根据数据组织方式的不同而存在差异。以访问元素为例，若要查看超市中某个商品的销售数据，在设计数据结构时，可以将超市中万余种商品的销售数据采用数组或链表来组织。
若采用链表的方式来组织与存储,数据分散地存储在物理空间中。链表中,访问任意一个元素都必须从第一个节点（或最后一个节点）开始进行按序访问，直到找到指定元素，例如仍然查看钢笔的销售数据，可以按照“a0→a1…"a46→a47”的次序访问，即相当于访问48次,操作完成。
如果数据的组织与存储方式不同,那么相同的操作对应的算法一般也不同。
02
算法效率
算法效率是指算法执行的时间。对于同一个问题，如果有多个解决问题的算法，那么执行时间短的算法效率高，反之执行时间长的算法效率低。
例如：超市购物付款，当收银员扫描一件商品的条形码时，计算机需要在几万种商品寻找这件商品，然后显示相应的商品名称和价格。
查找
在计算机科学中定义为：在一些（有序的/无序的）数据元素
(?https:?/??/?baike.?/?item?/?%E6%95%B0%E6%8D%AE%E5%85%83%E7%B4%A0?/?715313?)中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找。也就是根据给定的某个值，在查找表
(?https:?/??/?baike.?/?item?/?%E6%9F%A5%E6%89%BE%E8%A1%A8?/?2968924?)中确定一个关键字
(?https:?/??/?baike.?/?item?/?%E5%85%B3%E9%94%AE%E5%AD%97?/?7105697?)等于给定值的记录或数据元素，又称检索。
如何根据问题设计适合的查找算法？
能否设计出高效率的查找算法，取决于这些商品数据的组织及存储方式。最简单的方式是将这些数据按序存储在计算机中。查找时从头开始依次查找商品名称，直到找出正确的商品名称或是找遍整个表均没有找到为止。这种查找算法，对于一个商品种类不多的超市或许是可行的,但对一个有成千上万种商品的大型超市就不适用了。
2、
知识拓展
常用的查找算法：
顺序查找：
在一组数据中，从第一个数据开始，按照这组数据的排列顺序将每个数据逐个与给定的值进行比较。若某个数据与给定值相等，则查找成功，找到所查数据的位置;反之查找不成功。
原始数据：int[]a={4,6,2,8,1,9,0,3};
要查找数字：8
二分法查找：
二分查找又称折半查找，它是一种效率较高的查找方法。
【二分查找要求】：1.必须采用顺序存储结构
(?https:?/??/?baike.?/?item?/?%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84?)2.必须按关键字
(?https:?/??/?baike.?/?item?/?%E5%85%B3%E9%94%AE%E5%AD%97?)大小有序排列。
21世纪教育网
www.21cnjy.com
精品试卷·第
2
页
（共
2
页）
HYPERLINK
"http://21世纪教育网(www.21cnjy.com)
"
21世纪教育网(www.21cnjy.com)
