2021学年2.1 线性表结构及其实现教案

课 题

2.1线性表结构及其实现

课时安排

1

课型

素

养

目

标

课程标准要求：理解线性表的概念和特征。掌握线性表抽象数据类型的定义。

掌握线性表的两种实现方法。理解数组和链表的概念及其特点。

信息意识：能够根据解决问题的需要，自觉、主动地寻求恰当方式获取信息与处理信息；在合作解决问题的过程中，愿意与团队成员共享信息，实现信息的更大价值。

计算思维：能够正对限定条件的实际问题进行数据抽象，运用线性表结构合理组织、存储数据，选择合适的算法编程实现、解决问题

数字化学习与创新：学生在解决困难时能有意识地运用数字化环境中的信息与学习资源展开自主学习。

教学重点

1. 理解线性表的概念和特征。
2. 掌握线性表抽象数据类型的定义。

教学难点

1. 掌握线性表抽象数据类型的定义。
2. 理解数组和链表的概念及其特点。

教学方法

讲授法，演示法，问题情境教学法

学习方法

自主探究法，讨论学习法

教学过程

个别化教案

一、考勤

二、课前3分钟：植树节3.12

三、课前小测评：

四、导入：图书是人类文明传承的重要方式。图书馆是知识的宝库，存放了 大量的图书。为方便借阅和管理，图书馆把图书有顺序地放置在书架 上。借阅和归还图书后，要整理图书，让书架上的图书仍然有顺序。

新课内容：

 本节国绕“整理图书”项目展开学习，通过项目活动认识生活中 的线性表，学习定义线性表抽象数据类型，并编写代码实现线性表的 基本操作。本节主要包含“手工整理图书”和“编程整理图书”两个 任务。

 任务一：手工整理图书 ※活动1认识线性排列

 请仔细观察图2.1.1，回答下面的问题：

(1)从左数第1本书的书名是                 ， 紧挨着它的后一本是                            。

线性表 (linear list)：按线性结构组织数据元素。在线性表中，数据 元素之间存在前后的顺序关系。每个数据元素都有一个顺序号，顺序号 是连续的整数。通过顺序号可以访问数据元素。线性表中的数据元素可 以是一个数或一个字符，也可以是一个对象。

线性表的特征： 在线性表中插入或删除数据元素，该元素之后的数据元素顺序号都 将改变。

线性表抽象数据类型： 从以上活动可以看出，线性表的基本操作主要包括追加、删除、插 入、查询等操作。为了便于在程序中使用线性表解决问题，需要定义线 性表抽象数据类型(ADT LinearList),接口如下。

 ADT LinearList:

·LinearList:创建空线性表。 appendItem(item):将数据元素item追加到线性表。

·removeltem(pos):从线性表中删除pos位置的数据元素。

·getItem(pos):取得pos位置的数据元素。 、

·setltem(pos,item):设置线性表pos位置的数据为item.

·sizeO:获得线性表中数据元素的个数。

·isEmpty():判断线性表是否为空。

·insertltem(item,pos):将item插人表中pos位置。

顺序表和数组

  线性表的顺序存储用一组连续的存储单元依次存储线性表的数据元 素。利用这种存储方式实现的线性表叫作顺序表。

  如果顺序表中各数据元素占用的存储空间大小相同（比如是同一种 类型的数据)，这样的顺序表叫数组。各个数据元素叫数组元素，数据 元素的序号叫数组下标。如果知道数组的起始存储位置及单个数组元素 占用空间大小，各个数组元素的存储位置可以通过计算得到，因而数组 具有随机访问的特点，存取数组元素的效率很高。

  顺序表的数据元素是连续排列的，插入和删除数据元素都需要移动 它后面的元素，这导致操作的代价很高。

链表：

   用链式存储实现的线性表叫链表。链表由一系列的节点通过链接串 连在一起。 在链表中，相邻节点的存储位置不一定相邻，节点之间的顺序由 链接关系决定。在插入和删除数据元素时，并不需要移动节点，所以效 率很高。但链表中每个节点都增加了引用信息，需要使用额外的存储空 间。另外，在访问数据元素时，要从头节点开始依次向后移动寻找，效 率不如顺序表高。

课堂小结：

   通过本节学习我们了解了理解线性表的概念和特征。掌握线性表抽象数据类型的定义。掌握线性表的两种实现方法。理解数组和链表的概念及其特点。

作

业

课

前

三

分

钟

植树节是按照法律规定宣传保护树木，并组织动员群众积极参加以植树造林为活动内容的节日。按时间长短可分为植树日、植树周和植树月，共称为国际植树节。提倡通过这种活动，激发人们爱林造林的热情、意识到环保的重要性。

中国的植树节由凌道扬和韩安、裴义理等林学家于1915年倡议设立，最初将时间确定在每年清明节。1928年，国民政府为纪念孙中山逝世三周年将植树节改为3月12日。新中国成立后的1979年，在邓小平提议下，第五届全国人大常委会第六次会议决定将每年的3月12日定为植树节。

板

书

设

计

线性表的概念和特征。

线性表抽象数据类型的定义。

数组。

链表。

教

学

反

思

教案查阅签字