第14课线性表 课件(共22张PPT) 2022—2023学年浙教版（2020）初中信息技术七年级下册

(课件网) 第14课线性表 第15课数据结构与算法 数据结构：数据之间的相互关系及数据的组织方式。 复习巩固 先进后出 先进先出 队列 数组 栈 线性结构 特殊的线性表 复习巩固 打印机打印文件 浏览网页 线性结构是最基本、最简单，也是最常用的一种数据结构。（一对一） 线性表是一种最基础的线性结构，是由n个相同类型元素组成的有限序列。 （n=0时为空表） 1 线性表的概念 线性表有且仅有一个开始结点和一个终端结点。 线性表所有结点都最多只有一个前驱节点和一个后继节点。 a0 a1 …… ai-1 ai ai+1 …… an-1 A B C D E F …… Z 首节点 尾节点 无前驱节点 无后继节点 学号 姓名 语文 数学 英语 1 小明 95 100 98 2 小张 96 98 95 3 小林 92 95 100 4 小王 88 90 97 5 小赵 89 85 95 …… 是线性表吗？ 春 夏 秋 冬 数据的存储方式(物理结构） 数据自身的逻辑关系(结构） 线性表的存储方式一般有顺序存储结构和链式存储结构两种。 链式存储方式 顺序表 顺序存储结构 链表 A B C D E F G A B C D E F G 二、线性表的存储结构 顺序表 顺序存储结构 小明 小张 小林 小王 小赵 二、线性表的存储结构 学号 姓名 语文 数学 英语 1 小明 95 100 98 2 小张 96 98 95 3 小林 92 95 100 4 小王 88 90 97 5 小赵 89 85 95 …… 逻辑上相邻的两个数据在物理上也相邻 链表 链式存储方式 二、线性表的存储结构 学号 姓名 语文 数学 英语 1 小明 95 100 98 2 小张 96 98 95 3 小林 92 95 100 4 小王 88 90 97 5 小赵 89 85 95 …… 数据分散地存储在物理空间中 小明 小张 小林 小王 小赵 需要存储两个部分： 数据信息和后继元素的位置信息（指针） 三、数据组织与算法 线性表的常用操作： 学号 姓名 语文 数学 英语 1 小明 95 100 98 2 小张 96 98 95 3 小林 92 95 100 4 小王 88 90 97 5 小赵 89 85 95 …… 访问元素 插入元素 删除元素 查找学生 增加学生 删除学生 访问元素 a0 … a45 a46 a47 a48 … a900 小明 ….. 小林 小王 小赵 小军 ….. 小刘 顺序表常用数组的方法来实现 数据元素 数组下标 小明 … … 小张 小林8 小王 小赵 1154 a0 a45 a46 a47 a48 a900 a47 小明 ….. 小林 小王 小赵 小刘 小军 a0 … a45 a46 a47 a48 … a900 数据组织与算法在数组或链表中插入某个元素，分别采用怎样的算法？小明小张小林小王小赵head小明小张小林小王小赵null将元素“小海”插入到元素“小王”的前面小海小海小海设计两个不同的算法，在数组或链表中删除某个元素，比较两种算法的效率。小明小张小林小王小赵head小明小张小林小王小军null删除数组或链表中的元素“小张”小军小赵（ ） 方法一：…… 方法二：…… 方法三：…… 算法效率 时间效率 储存量需求 空间效率 算法的执行时间 算法在执行过程中 需要的最大存储空间 四、算法效率 队列 数组 栈 线性表 线性结构 （一对一） 非线性结构 图（多对多） 树（一对多） 数据结构 逻辑结构 存储结构（物理结构） 链式存储方式 顺序存储结构 1.线性表是一个_____。 A. 有限序列，可以为空 B. 有限序列，不能为空 C. 无限序列，可以为空 D. 无限序列，不能为空 A 2.下面关于线性表的叙述中，错误的是 _____。 A. 线性表采用顺序存储，必须占用一片连续的存储单元 B. 线性表采用顺序存储，便于进行插入和删除操作 C. 线性表采用链接存储，不必占用一片连续的存储单元 D. 线性表采用链接存储，便于进行插入和删除操作 B 3.用链式存储方式来存储线性表的优点是_____。 （A）便于随机读取 （B）花费的存储空间较顺序存储少 （C）便于插入和删除 （D）数据元素的物理顺序与逻辑顺序相同 C 21 24 36 57 77 87 99 14 a 4.若长度为8的一维数组 ... ...