2020—2021学年浙教版（2020）七年级下册 课件-第14课 线性表

第十四课 线性表 信息技术 七下 新知导入 根据图片回答问题 1、三张图分别是哪类数据结构？ 2、有什么共同点？ 数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。  新知导入 线性结构 简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：  1、线性结构是非空集。  2、线性结构有且仅有一个开始结点和一个终端结点。  3、线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。  线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。  新知导入 非线性结构 简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点： 1、非线性结构是非空集。   2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。  在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。 新知讲解 01 线性表的概念 新知导入 利用计算机程序解决问题时，与问题有关的数据往往不仅数量庞大，而且存在错综复杂的关系。为了使计算机更加高效地处理数据，需要对数据进行有效的组织和管理，并以一定的形式加以存储和表示。 新知讲解 1、有且仅有一个开始结点 a1，它没有直接前趋，而仅有一个直接后继 a2， a1叫表头元素； 2、有且仅有一个终端结点 an，它没有直接后继，而仅有一个直接前趋 an-1 ,an 叫表尾元素； 3、其余的内部结点 ai (2  i  n -1) 都有且仅有一个直接前趋 ai-1 和一个直接后继 ai+1 。 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素” 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素” 新知讲解 02 线性表的存储结构 新知导入 线性表的存储结构一般有两种方式：顺序存储结构和链式存储结构。 新知讲解 根据穿针引线的方式，又称为顺序存放和非顺序存放。 顺序存放是顺序存储结构， 非顺序存放称为链式存储方式。 新知讲解 例如：线性表 (5, 2, 1, 7, 4, 9) 的存储结构： 依次存储，地址连续——中间没有空出存储单元。 是一个典型的线形表顺序存储结构。 存储结构： 地址不连续——中间