初中浙教版 (2020)第14课 线性表优质课件ppt

导入新课

前面我们认识了一些数据结构，图片中的结构是什么结构？今天我们一块来学习表示数据的一种结构——线性表

欣赏视频

思考

 激发学生学习兴趣并快速进入学习状态

讲授新课

线性结构是最基本、最简单，也是最常用的一种数据结构。

而线性表是一种最基础的线性结构。

一、线性表的概念

反映现实世界的数据常具有特定的逻辑关系。

例如，某校2010——2019年七年级的招生人数可以用如下一组数据表示：

(653，669，670，688，669，650，655，667，689，680)

当看到这组数据时，会很自然地将年份与这些数据联系起来，得到以下数据表：

此时，(653，669，670，688，669，650，655，667，689，680)就是线性表的一种表示方式。

线性表是由n(n≥0)个元素组成的有限序列。

当n=0时，表示线性表中没有元素，为空表。

线性表一般的表示方法为：

a0，a1，...，ai-1，ai，ai+1，...，an-1)

表中数据元素从a0开始到an-1结束，则可以称a0为首节点， an-1为尾节点。

表中相邻两个元素之间存在顺序关系，如ai-1先于ai， ai又先于ai+1，则称ai-1是ai的前驱， ai+1是ai的后继。

也就是说，在这个集合中，除a0和an-1外，每个元素都有唯一的前驱和后继，如图所示。

线性表

日积月累

在线性结构中，有且仅有一个开始节点，即ao，该节点只有后继节点，没有前驱节点；

有且仅有一个结束节点，即an-1，该节点只有前驱节点，没有后继节点。

线性表结构特点

1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素（直接后继）。

二、线性表的存储结构

线性表的存储结构一般有两种方式：顺序存储结构和链式存储结构。

先来看一个生活中的例子

如图所示的五个球分别标记为1号、2号、3号、4号、5号

在需要将这五个球放入收纳架(如图所示)

那么可以如何收纳呢?

在收纳架中，一个位置只能摆放一个球。

球的摆放方式有以下两种：

一种是按照每一个球的编号分别按一定的顺序放入收纳架中，如图所示；

还有一种是随意摆放，如图所示。

按照球的收纳方式的不同，球的摆放方式又称为顺序存放和非顺序存放。

这种非顺序存放又可以称为链式存放。

如果将1一5号球想象成计算机中的数据，那么它们的存储方式就有两种，如图所示。

(1)顺序存储结构

(2)链式存储结构

从图中可以看出，根据数据的存储方式的不同，线性表的存储结构可以分为顺序存储结构和链式存储结构。

(1)顺序存储结构

如图所示，将数据按照一定的顺序存储在连续的整个物理空间中，即逻辑上相邻的两个数据在物理存储上也相邻，这种存储方式称为顺序存储结构，简称顺序表。

(2)链式存储结构

如图所示，数据分散地存储在物理空间中，在表示数据之间的逻辑关系时，每一个元素不仅需要存储数据信息而且还需要存储其后继数据元素的位置信息，这种存储结构称为链式存储结构，简称链表。

知识链接

链表

链表是一种链式存储结构，节点既存储数据元素本身的信息，又需要存储数据元素之间的链接信息，即地址域，也叫指针域。

三、线性结构中的数组列表

线性结构在生活中的应用非常广泛，比如经常用到的搜索引擎，对字符串的各种查找、索引的算法等。

数组就是一个用来存储数值的容器，如前面提及的篮球架。

一般用（a0，a1，...，ai-1，ai，ai+1，...，an-1)来表示含有n个元素的数组a。

其中，a0的下标是0。下标即是用来表示数组元素所在的位置。

如图所示，开辟七个空间来存放A-G七个字母，a0是数组a的第一个元素，即是A，a6的数据是G。

数据元素

数组下标

若在数组中，删除下标为3的数组空间中的元素a3即D，则插入点后的所有元素都要向前移，结果为A-B-C-E-F-G，如图所示。

由于数组空间的长度是固定的，所以a6地址单元中元素为空。

接着，在a4空间中插入元素H，则插入点后的所有元素全部都要向后移，结果为A-B-C-E-H-F-G，如图所示。

开动脑筋

如果在一个顺序表中，后面没有多余的空间了，那么执行插入操作后会产生怎样的结果呢?

线性表的推广

时间有序表、排序表、和频率有序表都可以看做是线性表的推广。

如果按照结点到达结构的时间先后，作为确定结点之间关系的，这样一种线性结构称之为时间有序表。

例如，在红灯前停下的一长串汽车，最先到达的为首结点，最后到达的为尾结点；在离开时最先到达的汽车将最先离开，最后到达的将最后离开。

这些汽车构成理一个队列，实际上就是一个时间有序表。

随堂练习

若有以下顺序表，在执行将33插入后，需要几个移动步骤?

通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。

通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。

通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。

通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。

通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。

通过教师的讲解，以小组合作的方式，开展探讨交流，完成任务。

学生小组间讨论，共同完成任务，并分组汇报。

通过小组合作，加强学生组内团结、共同完成任务

通过小组合作，加强学生组内团结、共同完成任务

通过小组合作，加强学生组内团结、共同完成任务

通过小组合作，加强学生组内团结、共同完成任务

通过小组合作，加强学生组内团结、共同完成任务

通过小组合作，加强学生组内团结、共同完成任务

培养学生独立完成练习的能力。

课堂小结

分小组总结归纳，教师补充。

各组汇报总结，其他小组成员做补充。

锻炼学生的总结能力，逻辑思维、语言表达能力。

布置作业

     1.什么是线性表?按照存储方式的不同，线性表分成哪两大类?量出1毫升的水?请写出算法。

板书

一、线性表的概念

二、线性表的存储结构

三、线性结构中的数组列表