上课啦THE POWERPOINT TEMPALTE模块2线性表54123顺序存储结构逻辑结构实例引入应用举例链式存储结构学习目的与要求重点：掌握顺序表和链表的逻辑描述和存储实现难点：顺序表和单链表的实现和应用线性结构线性结构的特点： 在数据元素的非空有限集中，数据元素是有序的，排在某个数据元素b之前的数据元素a称为b的直接前驱，而数据元素b称为a的直接后继。且具有如下特点：(1)存在唯一的一个被称为“第一个”的数据元素。(2)存在唯一的一个被称为“最后一个”的数据元素。(3)除第一个之外，集合中的每个数据元素均只有一个直接前驱。(4)除最后一个之外，集合中的每个数据元素均只有一个直接后继。2.1 实例引入 【实例1】银行办理业务时顾客的队列、26个英文字母表、班级同学的点名册、12生肖列表等都是线性结构。【实例2】某学校成立了移动互联社团，今天招募社团人员，假设我们是社团负责记录报名信息的人员，我们需要做什么呢？2.2 线性表的逻辑结构定义： 具有相同数据类型的 n(≥0)个数据元素的有限序(次序)列。 记作(a1, a2 , …ai-1, ai, ai+1,…, an) 其中, ai 是表中数据元素，n 是表长度， i为数据元素ai 在线性表中的位序。【例2.1】某班前五名学生语文成绩(99，98，97，95，90)是线性表，表中每个数字是一个结点。【例2.2】一年四季(春，夏，秋，冬)是一个线性表，表中的结点是一个字符。2.2 线性表的逻辑结构【例2.3】学生成绩表是一个线性表，表中每一行(一条记录)是一个结点。一条记录是由学号、姓名、性别、数学成绩和语文成绩5个数据项组成。线性表的特点: 同一线性表中元素具有相同特性。在Java中，可以用类定义数据元素的数据类型。相邻数据元素之间存在顺序关系。除第一个元素外，其他每一个元素有且仅有一个直接前趋。除最后一个元素外，其他每一个元素有且仅有一个直接后继。 线性表的逻辑结构是线性结构2.2.2 线性表的基本运算(1)初始化initList(L)：构造一个空的线性表L，即表的初始化。(2)求表长listLength(L)：求线性表L中的结点个数。(3)取值getNode(L, i)：取线性表L中的第i个结点(1≤i≤ListLength(L))。(4)定位locateNode(L, e)：在线性表L中查找值为e的结点，并返回该结点在线性表L中的位序。若线性表L中有多个结点的值和e 相同，则返回首次找到的结点的位序；若线性表L中没有结点的值为e ，则返回0，表示查找失败。(5)插入insert(L, e，i)：在线性表L的第i个元素之前插入新的元素e，线性表L的长度增1。(6)删除delete(L, i)： 删除线性表L的第i个结点，表L的长度减1。 对于实际问题中涉及的其它更为复杂的运算，可以用基本运算的组合来实现。在Java中，可以用接口或抽象类来定义线性表的操作集合。 2.2.2 线性表的基本运算【例2.4】写出两个集合的归并算法。 分析：设两个集合A和B分别由两个线性表LA和LB表示，要求将LB中存在但在LA中不存在的数据元素插入到表LA中。算法思想：(1)依次从LB中取出一个数据元素；// 使用getNode(L, i)(2)判断该数据元素在LA中是否存在；// 使用locateNode(L, e)(3)若不存在，则插入到LA中。// 使用insert(L, e，i)算法实现： 上述归并算法是利用基本操作完成的，那么每一种基本操作如何实现？这要涉及存储结构，只有确定了存储结构才能实现基本算法。2.3 线性表的顺序存储结构及运算实现【学习任务】理解线性表在顺序存储结构下的特点，掌握顺序表的表示、相关算法及程序实现定义：线性表的顺序存储是指把线性表的各个结点按逻辑次序依次存储在一组地址连续的存储单元里。用这种方法存储的线性表简称为顺序表。结点的存储地址：假设线性表中所有结点的类型相同，设表中每个结点占用L个存储单元，并以所占的第一个单元的存储地址作为该结点的存储地址。则线性表中第i+1个结点的存储地址LOC(ai+1)和第i个结点的存储地址LOC(ai)之间满足下列关系： LOC(ai+1)= LOC(ai)+L 一般来说，线性表的第i个数据元素ai的存储地址为： LOC(ai)= LOC(a1)+(i-1)*L 式中LOC(a1)是线性表第一个结点的存储地址，通常称作线性表的起始地址或基地址。2.3.1 顺序表的定义顺序表的特点：以元素在计算机中的物理位置相邻来表示线性表中数据元素之间的逻辑关系，如图2.2所示。在顺序表中，每个结点a i 的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址，从而实现