初中信息技术浙教版（2020）七年级下册第14课 线性表试讲课教学ppt课件

这是一份初中信息技术浙教版（2020）七年级下册第14课 线性表试讲课教学ppt课件，文件包含第十四课线性表ppt、第十四课线性表教学设计doc等2份课件配套教学资源，其中PPT共22页， 欢迎下载使用。
1、三张图分别是哪类数据结构？2、有什么共同点？数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。 
线性结构简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点： 1、线性结构是非空集。 2、线性结构有且仅有一个开始结点和一个终端结点。 3、线性结构所有结点都最多只有一个直接前趋结点和一个直接后继结点。 线性表就是典型的线性结构，还有栈、队列和串等都属于线性结构。 
非线性结构简单地说，非线性结构就是表中各个结点之间具有多个对应关系。如果从数据结构的语言来描述，非线性结构应该包括如下几点：1、非线性结构是非空集。  2、非线性结构的一个结点可能有多个直接前趋结点和多个直接后继结点。 在实际应用中，数组、广义表、树结构和图结构等数据结构都属于非线性结构。
利用计算机程序解决问题时，与问题有关的数据往往不仅数量庞大，而且存在错综复杂的关系。为了使计算机更加高效地处理数据，需要对数据进行有效的组织和管理，并以一定的形式加以存储和表示。
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) 的存储结构：
依次存储，地址连续——中间没有空出存储单元。
是一个典型的线形表顺序存储结构。存储结构：
地址不连续——中间存在空的存储单元。
不是一个线形表顺序存储结构。
顺序存储结构将数据按照一定的顺序存储在连续的整个物理空间中，即逻辑上相邻的两个数据在物理存储上也相邻，这种存储方式称为顺序存储结构,简称顺序表。
用一组物理位置任意的存储单元来存放线性表的数据元素。这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中元素的逻辑次序和物理次序不一定相同。
链式存储结构数据分散地存储在物理空间中，在表示数据之间的逻辑关系时，每一个元素不仅需要存储数据信息而且还需要存储其后继数据元素的位置信息,这种存储结构称为链式存储结构，简称链表。
03 线性表结构中 的数组列表
数据结构的线性表，顾名思义，是呈线性的，但是在数据结构的存储方面又将线性表分为了数组，和链表。数组元素的存储方式，是在内存里面开了一段空间并且元素之间的地址位置是连续的。而链表是爱存哪儿存哪儿，我们只需要在存的元素中标出下一个元素的地理位置，顺藤摸瓜，反正也是一条线的，也是把数据存储下来了。这就是数组和线性表之间的本质区别。
0 1 2 3 4 5 6
数组就是一个用来存储数值的突器。一般用（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.1 顺序存储结构：一段连续的内存空间。 优点：随机访问 缺点：插入删除效率低，大小固定2.2 链式存储结构：不连续的内存空间 优点：大小动态扩展，插入删除效率高 缺点：不能随机访问。
数据结构的物理结构：2.3 索引存储结构：为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。优点：对顺序查找的一种改进，查找效率高缺点：需额外空间存储索引2.4 散列存储结构：选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲。优点：查找基于数据本身即可找到，查找效率高，存取效率高。缺点：存取随机，不便于顺序查找。