第十四课 线性表 课件（23张ppt）+教学设计

中小学教育资源及组卷应用平台 第十四课 线性表 教学设计 1教学目标 1. 知道为什么存在数据结构。理解数据结构。理解常见的数据结构类型，能判断生活中数据结构的应用。 2.在完成查找通讯录、排序音乐任务时，体会数据结构存在意义。在完成确定座位号任务、观看栈与队列的图片、视频时，学会判断常见的数据结构类型。 3.通过了解数据结构存在的重要性，感受计算机解决问题的有效性，激发对信息技术学习 的欲望。 2重点难点 教学重点：了解数据结构的概念及种类。 教学难点：各种数据结构在生活中的应用。 3教学过程 1、 回顾上节课内容 （1）三张图分别是哪类数据结构？ (2)有什么共同点？ 数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。? 线性结构 简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点：? 1、线性结构是非空集。? 2、线性结构有且仅有一个开始结点和一个终端结点。? 3、线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。? 线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。? 非线性结构 简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点： 1、非线性结构是非空集。?? 2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。? 在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。 2、新课讲授 01 线性表的概念 线性表：线性表是最基本、最简单、也是最常用的一种数据结构。 线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。 n (n?0) 数据元素 a , a , …, a （1）、有且仅有一个开始结点 a1，它没有直接前趋，而仅有一个直接后继 a2， a1叫表头元素； （2）、有且仅有一个终端结点 an，它没有直接后继，而仅有一个直接前趋 an-1 ,an 叫表尾元素； （3）、其余的内部结点 ai (2 ? i ? n -1) 都有且仅有一个直接前趋 ai-1 和一个直接后继 ai+1 。 某一元素的左侧相邻元素称为“直接前驱”，位于此元素左侧的所有元素都统称为“前驱元素” 某一元素的右侧相邻元素称为“直接后继”，位于此元素右侧的所有元素都统称为“后继元素” 02 线性表的存储结构 线性表的存储结构一般有两种方式：顺序存储结构和链式存储结构。 根据穿针引线的方式，又称为顺序存放和非顺序存放。 顺序存放是顺序存储结构， 非顺序存放称为链式存储方式。 顺序存储结构 将数据按照一定的顺序存储在连续的整个物理空间中，即逻辑上相邻的两个数据在物理存储上也相邻，这种存储方式称为顺序存储结构,简称顺序表。 链式存储结构 数据分散地存储在物理空间中，在表示数据之间的 逻辑关系时，每一个元素不仅需要存储数据信息而且还需要存储其后继数据元素的位置信息,这种存储结构称为链式存储结构，简称链表。 03 线性表结构中的数组列表 数组就是一个用来存储数值的突器。一般用（a0，a1,……,ai-1,ai,ai+1,…,an-1)事示含有n个元素的数组a。其中，a0的下标是0。下标即是用来表示数组元素所在的位置。开辟七个空间来存放A—G七个字母，a0是数组的第一个元素，即是A，a6的数据是G。 删除元素 若在数组中，删除下标为3的数组空间中的元素a3即D，则插入点后的所有元素都要向前移，结果为A-B-C-E-F-G，由于数组空间的长度是固定的,所以a6,地址单元中元素为空。 插入元素 在a4空间中插入元素H，则插人点后的所有元素全部都要向后移，结果为A-B-C-E-H-F-G。 2、 知识拓展 数据结构的物理结构： 物理结构又叫存储结构，分为四种种，顺序存储结构、链式存储结 ... ...