1、第十四课 线性表 信息技术 七下 新知导入新知导入 根据图片回答问题根据图片回答问题 1、三张图分别是哪类数据结构？ 2、有什么共同点？ 数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结 构和非线性结构两类。 新知导入新知导入 线性结构 简单地说，线性结构就是表中各个结点具有线性关系。如果从数 据结构的语言来描述，线性结构应该包括如下几点： 1、线性结构是非空集。 2、线性结构有且仅有一个开始结点和一个终端结点。 3、线性结构所有结点都最多只有一个直接前趋结点和一个直接 后继结点。 线性表就是典型的线性结构，还有栈、队列和串等都属于线性结 构。 新知导入新知导入 非
2、线性结构 简单地说，非线性结构就是表中各个结点之间具有多个对应 关系。如果从数据结构的语言来描述，非线性结构应该包括 如下几点： 1、非线性结构是非空集。 2、非线性结构的一个结点可能有多个直接前趋结点和多个 直接后继结点。 在实际应用中，数组、广义表、树结构和图结构等数据结构 都属于非线性结构。 新知讲解新知讲解 01 线性表的概念 新知导入新知导入 利用计算机程序解决问题时，与问题有关的数据 往往不仅数量庞大，而且存在错综复杂的关系。 为了使计算机更加高效地处理数据，需要对数据 进行有效的组织和管理，并以一定的形式加以存 储和表示。 新知讲解新知讲解 1、有且仅有一个开始结点 a1，它没有
3、直接前趋，而仅有一个 直接后继 a2， a1叫表头元素； 2、有且仅有一个终端结点 an，它没有直接后继，而仅有一个 直接前趋 an-1 ,an 叫表尾元素； 3、其余的内部结点 ai (2 i n -1) 都有且仅有一个直接前 趋 ai-1 和一个直接后继 ai+1 。 某一元素的左侧相邻元素称为“直接前驱”，位于此元素 左侧的所有元素都统称为“前驱元素” 某一元素的右侧相邻元素称为“直接后继”，位于此元素 右侧的所有元素都统称为“后继元素” 新知讲解新知讲解 02 线性表的存储结构 新知导入新知导入 线性表的存储结构一般有两种方式：顺 序存储结构和链式存储结构。 新知讲解新知讲解 根据穿针
4、引线的方式，又称为顺序存放和非顺 序存放。 顺序存放是顺序存储结构， 非顺序存放称为链式存储方式。 新知讲解新知讲解 例如：线性表 (5, 2, 1, 7, 4, 9) 的存储结构： 依次存储，地址连续中间 没有空出存储单元。 是一个典型的线形表顺序存储结构。 存储结构： 地址不连续中间存在空的 存储单元。 不是一个线形表顺序存储结构。 顺序存储结构 将数据按照一定的顺序存储在连续的整个物理 空间中，即逻辑上相邻的两个数据在物理存储 上也相邻，这种存储方式称为顺序存储结构,简 称顺序表。 用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是 连续的，也可以是不连续的，甚至是
5、零散分布在内存中的任意位置上的。因此，链表中元 素的逻辑次序和物理次序不一定相同。 链式存储结构 链式存储结构 数据分散地存储在物理空间中，在表示数据之间的 逻辑关系时，每一个元素不仅需要存储数据信息而 且还需要存储其后继数据元素的位置信息,这种存储结构 称为链式存储结构，简称链表。 新知讲解新知讲解 顺序存储结构链式存储结构 优点 存储密度大，存储空间利用率高，可随 机存取。 插入或删除元素时很方便 ，使用灵活，结点空间可 以动态申请和释放。 缺点插入或删除元素时不方便 存储密度小，存储空间利 用率低，非随机存取。 新知讲解新知讲解 03 线性表结构中 的数组列表 新知讲解新知讲解 数据结构
6、的线性表，顾名思义，是呈线性的，但是在数据结构的存储方面又将线性 表分为了数组，和链表。 数组元素的存储方式，是在内存里面开了一段空间并且元素之间的地址位置是连续 的。 而链表是爱存哪儿存哪儿，我们只需要在存的元素中标出下一个元素的地理位置， 顺藤摸瓜，反正也是一条线的，也是把数据存储下来了。 这就是数组和线性表之间的本质区别。 ABCDEFG 012345 6 数据元素 数组下标 新知讲解新知讲解 数组就是一个用来存储数值的突器。一般用（a0，a1,ai-1,ai,ai+1,an-1)事示 含有n个元素的数组a。其中，a0的下标是0。下标即是用来表示数组元素所在的位置 。开辟七个空间来存放A
7、G七个字母，a0是数组的第一个元素，即是A，a6的数据是 G。 ABCDEFG 012345 6 数据元素 数组下标 新知讲解新知讲解 若在数组中，删除下标为3的数组空间中的元素a3即D，则插入点后的所有元素都要 向前移，结果为A-B-C-E-F-G，由于数组空间的长度是固定的,所以a6,地址单元中元 素为空。 ABCEFG 012345 6 删除元素 新知讲解新知讲解 在a4空间中插入元素H，则插人点后的所有元素全部都要向后移，结果 为A-B-C-E-H-F-G。 ABCDHFG 012345 6 插入元素 知识拓展知识拓展 数据结构的物理结构： 物理结构又叫存储结构，分为四种种，顺序存储结
8、构、链式 存储结构、索引结构、散列结构。 2.1 顺序存储结构：一段连续的内存空间。 优点：随机访问 缺点：插入删除效率低，大小固定 2.2 链式存储结构：不连续的内存空间 优点：大小动态扩展，插入删除效率高 缺点：不能随机访问。 知识拓展知识拓展 数据结构的物理结构： 2.3 索引存储结构：为了方便查找，整体无序，但索引块之间有序 ，需要额外空间，存储索引表。 优点：对顺序查找的一种改进，查找效率高 缺点：需额外空间存储索引 2.4 散列存储结构：选取某个函数，数据元素根据函数计算存储位 置可能存在多个数据元素存储在同一位置，引起地址冲。 优点：查找基于数据本身即可找到，查找效率高，存取效率
9、高。 缺点：存取随机，不便于顺序查找。 巩固小结巩固小结 第十四课第十四课 线性表线性表 教学设计教学设计 1 教学目标教学目标 1. 知道为什么存在数据结构。理解数据结构。理解常见的数据结构类型，能判断生活中数据结构的 应用。 2.在完成查找通讯录、排序音乐任务时，体会数据结构存在意义。在完成确定座位号任务、观看栈 与队列的图片、视频时，学会判断常见的数据结构类型。 3.通过了解数据结构存在的重要性，感受计算机解决问题的有效性，激发对信息技术学习 的欲望。 2 重点难点重点难点 教学重点：了解数据结构的概念及种类。 教学难点：各种数据结构在生活中的应用。 3 教学过程教学过程 1、回顾上节课
10、内容 （1）三张图分别是哪类数据结构？ (2)有什么共同点？ 数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性 结构两类。 线性结构 简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应 该包括如下几点： 1、线性结构是非空集。 2、线性结构有且仅有一个开始结点和一个终端结点。 3、线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。 线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。 非线性结构 简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语 言来描述，非线性结构应该包括
11、如下几点： 1、非线性结构是非空集。 2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。 在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。 2、新课讲授 01 线性表的概念 线性表：线性表是最基本、最简单、也是最常用的一种数据结构。 线性表（linear list）是数据结构的一种，一个线性表是 n 个具有相同特性的数据元素的有限序 列。 n (n0) 数据元素 a , a , , a （1）、有且仅有一个开始结点 a1，它没有直接前趋，而仅有一个直接后继 a2， a1叫表头元 素； （2）、有且仅有一个终端结点 an，它没有直接后继，而仅有一个直接前趋
12、an-1 ,an 叫表尾元 素； （3）、其余的内部结点 ai (2 i n -1) 都有且仅有一个直接前趋 ai-1 和一个直接后继 ai+1 。 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素” 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素” 02 线性表的存储结构 线性表的存储结构一般有两种方式：顺序存储结构和链式存储结构。 根据穿针引线的方式，又称为顺序存放和非顺序存放。 顺序存放是顺序存储结构， 非顺序存放称为链式存储方式。 顺序存储结构 将数据按照一定的顺序存储在连续的整个物理空间中，即逻辑上相邻的两个数据在
13、物理存储上 也相邻，这种存储方式称为顺序存储结构,简称顺序表。 链式存储结构链式存储结构 数据分散地存储在物理空间中，在表示数据之间的 逻辑关系时，每一个元素不仅需要存储数据信息而且还需要存储其后继数据元素的位置信息,这 种存储结构称为链式存储结构，简称链表。 03 线性表结构中的数组列表 数组就是一个用来存储数值的突器。一般用（a0，a1,ai-1,ai,ai+1,an-1)事示含有 n 个元素的数 组 a。其中，a0的下标是 0。下标即是用来表示数组元素所在的位置。开辟七个空间来存放 A G 七个字母，a0是数组的第一个元素，即是 A，a6的数据是 G。 删除元素 若在数组中，删除下标为
14、3 的数组空间中的元素 a3即 D，则插入点后的所有元素都要向前移， 结果为 A-B-C-E-F-G，由于数组空间的长度是固定的,所以 a6,地址单元中元素为空。 插入元素 在 a4空间中插入元素 H，则插人点后的所有元素全部都要向后移，结果为 A-B-C-E-H-F-G。 2、知识拓展知识拓展 数据结构的物理结构： 物理结构又叫存储结构，分为四种种，顺序存储结构、链式存储结构、索引结构、散列结构。 2.1 顺序存储结构：一段连续的内存空间。 优点：随机访问 缺点：插入删除效率低，大小固定 2.2 链式存储结构：不连续的内存空间 优点：大小动态扩展，插入删除效率高 2.3 索引存储结构：为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。 优点：对顺序查找的一种改进，查找效率高 缺点：需额外空间存储索引 2.4 散列存储结构：选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在 同一位置，引起地址冲。 优点：查找基于数据本身即可找到，查找效率高，存取效率高。 缺点：存取随机，不便于顺序查找。 缺点：不能随机访问。
