第15课 数据结构与算法（课件）-七年级信息技术下册同步精品课堂（浙教版2020）

第15课 数据结构与算法 ” 1 知识回顾 算法是解决问题的方法和步骤。 数据结构指数据的组织形式。 算法的表示 算法的三种基本控制结构 自然语言（常表述不清） 流程图（图形使用正确、逻辑正确） …… 数组 栈 队列 链表 按照先后顺序存储数据，通过数组名和下标进行数据的访问和更新 后进先出 先进先出 2 发现问题 编号 名称 …… …… 2000129 酸奶 2003572 花生油 2001987 钢笔 2002876 矿泉水 …… …… 名称 类别 …… …… 酸奶 食品 花生油 食品 钢笔 日用品 矿泉水 食品 …… …… 编号 数量 …… …… 2000129 1048 2003572 238 2001987 2145 2002876 598 …… …… 开动脑筋：三张表格间是否存在联系？你能否更好地表示数据之间的关系？ 共同的“名称”列 共同的“编号”列 3 发现问题 编号 名称 …… …… 2000129 酸奶 2003572 花生油 2001987 钢笔 2002876 矿泉水 …… …… 名称 类别 …… …… 酸奶 食品 花生油 食品 钢笔 日用品 矿泉水 食品 …… …… 编号 数量 …… …… 2000129 1048 2003572 238 2001987 2145 2002876 598 …… …… 编号 名称 数量 类别 …… …… …… …… 2000129 酸奶 1048 食品 2003572 花生油 238 食品 2001987 钢笔 2145 日用品 2002876 矿泉水 598 食品 …… …… …… …… 解决数据冗余问题 4 数据结构与算法 采用数组的方式存储，可通过元素下标来直接访问数组中某个元素。若a47存储的是钢笔的销售数据，可直接用a47表示，访问1次。 236 …… 1048 238 2145 598 …… 1154 0 45 46 47 48 11023 如果要查看钢笔的销售数据，请问需要访问几次？ 5 数据结构与算法 采用链表的方式存储，数据分散地存储在物理空间中，访问任意一个元素必须从第一个节点（或最后一个节点）开始进行按序访问，直到找到指定元素。 如果要查看钢笔的销售数据，请问需要访问几次？ 236 1048 238 2145 598 1154 a0 a45 a46 a47 a48 a11023 “a0→a1→……a46→a47”相当于访问48次 6 插入某个元素 如何将元素“2145”插入到元素“598”的前面？ 236 数组存储 1048 238 598 1154 2145 ① ② ③ ④ 链表存储 236 1048 238 598 1154 2145 head null 就删除、插入元素而言，链表存储更高效。 7 算法效率 算法效率 时间效率 储存量需求 执行时间短的算法效率高 存储量需求低的算法效率高 8 课堂小结 数组 链表 内存地址 连续的内存空间 非连续的内存空间 数据长度 长度固定，一般不可动态扩展 长度可动态变化 增删效率 低，需移动被修改元素之后的所有元素 高，只需修改指针指向 查询效率 高，通过数组名和下标直接访问 低，逐一遍历查找 数据访问方式 随机访问 顺序访问 9 巩固练习 1、下列叙述中正确的是 ( ) A、线性链表中的各元素在存储空间中的位置必须是连续的 B、线性链表中的表头元素一定存储在其他元素的前面 C、线性链表中的各元素在存储空间中的位置不一定是连续的，但表头元素一定存储在其他元素的前面 D、线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的 D 10 巩固练习 2、下列叙述正确的是 ( ) A.算法的执行效率与数据的存储结构无关 B、算法的空间复杂度是指算法程序中指令 (或语句) 的条数 C、算法的有穷性是指算法必须能在执行有限个步骤之后终止 D、算法的时间复杂度是指执行算法程序所需要的时间 C 3、用链表表示线性表的优点是（ ）。 A、便于随机存取 B、花费的存储空间比顺序表少 C、数据元素的物理顺序与逻辑顺序相同 D、便于插入与删除 D 11 感谢您的聆听与指导 ” 12 $