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

第14课线性表 第15课数据结构与算法 1 数据结构：数据之间的相互关系及数据的组织方式。 复习巩固 先进后出 先进先出 队列 数组 栈 线性结构 特殊的线性表 复习巩固 打印机打印文件 浏览网页 线性结构是最基本、最简单，也是最常用的一种数据结构。（一对一） 线性表是一种最基础的线性结构，是由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 数据组织与算法 11 在数组或链表中插入某个元素，分别采用怎样的算法？ 小明 小张 小林 小王 小赵 head 小明 小张 小林 小王 小赵 null 将元素“小海”插入到元素“小王”的前面 小海 小海 小海 12 设计两个不同的算法，在数组或链表中删除某个元素，比较两种算法的效率。 小明 小张 小林 小王 小赵 head 小明 小张 小林 小王 小军 null 删除数组或链表中的元素“小张” 小军 小赵 （ ） 方法一：…… 方法二：…… 方法三：…… 算法效率 时间效率 储存量需求 空间效率 算法的执行时间 算法在执行过程中 需要的最大存储空间 四、算法效率 队列 数组 栈 线性表 线性结构 （一对一） 非线性结构 图（多对多） 树（一对多） 数据结构 逻辑结构 存储结构（物理结构） 链式存储方式 顺序存储结构 1.线性表是一个__________。      A. 有限序列，可以为空             B. 有限序列，不能为空  C. 无限序列，可以为空             D. 无限序列，不能为空     A  2.下面关于线性表的叙述中，错误的是 _________。    A. 线性表采用顺序存储，必须占用一片连续的存储单元  B. 线性表采用顺序存储，便于进行插入和删除操作  C. 线性表采用链接存储，不必占用一片连续的存储单元  D. 线性表采用链接存储，便于进行插入和删除操作 B 3.