第14课 线性表（课件）-七年级信息技术下册同步精品课堂（浙教版2020）

第14课 线性表 ” 1 线性表的概念 我们常常自然地将年份与这些数据联系起来，形成一张数据表。 线性结构是最基本、最简单，也是最常用的一种数据结构。而线性表是一种最基础的线性结构。反映现实世界的数据常具有特定的逻辑结构。 某校2010-2019年七年级招生人数可以用如下一组数据表示： （653，669，670，688，669，650，655，667，689，680） 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 653 669 670 688 669 650 655 667 689 680 2 线性表的概念 线性表是由n（n≥0）个元素组成的有限序列。当n=0时，表示线性表中没有元素，为空表。 653 669 670 688 669 650 655 667 689 680 a0 a1 …… ai-1 ai ai+1 …… an-1 有且仅有一个首节点， 无前驱节点。 ai-1是ai的前驱，ai是ai+1的前驱； ai+1是ai的后继，ai是ai-1的后继； 除a0和an-1外，每个元素都有唯一的前驱和后继。 有且仅有一个尾节点， 无后继节点。 3 线性表的存储结构 每个小黄人都有自己的凳子，她们按次序坐在自己的位置上。 1 2 3 4 5 1 2 3 4 5 4 线性表的存储结构 顺序存储结构（顺序表）：数据按照一定的顺序存储在连续的整个物理空间中，即逻辑上相邻的两个数据在物理存储上也相邻。 1 2 3 4 5 1 2 3 4 5 每个小黄人都有自己的凳子，她们按次序坐在自己的位置上。 5 线性表的存储结构 减少一个凳子，5个小黄人沿着凳子顺时针走，当信号或者音乐停止时，小黄人坐到位置上，没有抢到凳子的人被淘汰。 1 2 3 4 1 2 3 4 5 6 线性表的存储结构 1 2 3 4 1 2 3 4 5 链式存储结构（链表）：数据分散地存储在物理空间中，在表示数据之间的逻辑关系时，每一个元素不仅需要存储数据信息而且还需要存储其后继数据元素的位置信息。 快乐都是你们的，我什么也没有。 7 线性结构中的数组列表 1 2 3 4 5 1 2 3 4 5 2号小黄人请假时，插入点后所有元素向前移，5号凳子空着。 8 线性结构中的数组列表 若在数组中，删除下标为3的数组空间中的元素a3即D，则插入点后所有元素向前移，结果为A-B-C-E-F-H，a6地址单元中元素为空。 A B C D E F G 0 1 2 3 4 5 6 数据元素 数组下标 A B C E F G 0 1 2 3 4 5 6 9 线性结构中的数组列表 接着，在a4空间中插入元素H，则插入点后所有元素全部都要向后移，结果为A-B-C-E-H-F-G。 A B C E F G 0 1 2 3 4 5 6 数据元素 数组下标 A B C E H F G 0 1 2 3 4 5 6 10 顺序结构VS链式结构 顺序结构 1、顺序存储结构的内存地址一定是连续的。 2、顺序存储结构删除和插入需要移动大量数据元素，适用于频繁查询时使用。 链式结构 1、链式存储结构的内存地址不一定是连续的。 2、链式存储适用于在较频繁地插入、删除、更新元素。 11 巩固练习 1、下面关于线性表的描述中，错误的是哪一个？（ ） A、线性表采用顺序存储，必须占用一片连续的存储单元 B、线性表采用顺序存储，便于进行插入和删除操作 C、线性表采用链表存储，不必占用一片连续的存储单元 D、线性表采用链表存储，便于插入和删除操作 B 2、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。 A、110 B、108 C、100 D、120 B 顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 12 巩固练习 3、线性表L=(a1，a2,……an)，下列说法正确的是（ ）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 D 4、线性表是_________（ ）。 A、一个有限序列，可以为空 B、一个有限序列，不可以为空 C、一个无限序列，可以为空 D、一个无限序列，不可以为空 A 13 感谢您的聆听与指导 ” 14 $