1、上课啦THE POWERPOINT TEMPALTE模块1 概述什么是数据结构1相关概念和术语2研究内容3数据类型与抽象数据类型4算法及其性能分析5学习目的与要求重点：理解数据结构的各种基本概念和术语理解线性结构、层次结构和网状结构的结构特点理解数据的逻辑结构、存储结构及运算三方面的概念及相互关系难点：掌握算法性能（时间和空间）的分析方法。1.1 什么是数据结构程序设计的过程，一般遵循以下解决步骤：程序设计的过程，一般遵循以下解决步骤：数值问题 数学方程式非数值问题 设计合理的数据结构（表、树、图等）分析问题分析问题建立数学模型建立数学模型设计算法设计算法编写代码编写代码数据结构数据结构是一门
2、研究非数值计算程序设计问题中的操作对象，以及是一门研究非数值计算程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。它们之间的关系和操作等相关问题的学科。数据结构的3种基本结构-线性结构 线性结构线性结构实例：学生信息管理系统数据结构的3种基本结构-树结构 树结构树结构实例：八皇后问题数据结构的3种基本结构-图结构 图结构图结构实例：田径赛的时间安排问题1.2 数据结构的相关概念和术语 数据（数据（Data）数据是计算机可以操作的对象，是能被计算机识别并处理的描述客观事物的符号集合。数据不仅仅包括整数、实数等数值类型，也包括字符、文字、图形图像、视频、声音等非数值类型。数据元素
3、（数据元素（Data Element）数据元素是组成数据的基本单位,是计算机程序加工处理的基本单位，在计算机中通常作为一个整体进行考虑和处理。数据项（数据项（Data Item）数据项（Data Item）是有独立含义的最小单位。一个数据元素可由一个或多个数据项组成，此时的数据元素通常称为记录（Record）。数据对象（数据对象（Data Object）数据对象是性质相同的数据元素的集合，是数据的一个子集。数据的三个层次数据的三个层次例如：表例如：表1.1所示，学生信息表是所示，学生信息表是数据数据，一行表示一个学生的记录，每一条记录就是一个，一行表示一个学生的记录，每一条记录就是一个数据数据
4、元素元素，每一个数据元素都是由学号、姓名、性别、出生日期、政治面貌，每一个数据元素都是由学号、姓名、性别、出生日期、政治面貌5个个数据项数据项组成。组成。1.3 数据结构的研究内容 逻辑结构:数据元素之间的逻辑关系。存储结构:数据元素及其关系在计算机存储器内的表示。数据的运算:即对数据施加的操作。1.3 数据结构的研究内容-逻辑结构 四种基本数据结构关系图四种基本数据结构关系图1.3 数据结构的研究内容-存储结构数据的存储结构顺序存储：逻辑上相邻的结点存储在物理位置上相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现.借助于语言的数组来实现。链式存储：不要求逻辑上相邻的结点物理上也相
5、邻，结点间的逻辑关系是由附加的指针字段表示的，在java中使用“对象引用”来实现指针。1.3 数据结构的研究内容-存储结构顺序存储结构链式存储结构1.3 数据结构的研究内容-存储结构1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346 链式存储链式存储 h1.4 数据类型与抽象数据类型数据类型（Data Type）数据类
6、型是指一组性质相同的值的集合以及在此集合上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。数据类型是按照值的不同进行划分的。在高级语言中，每个变量、常量和表达式都有各自的取值范围。类型就用来说明变量或表达式的取值范围和所能进行的操作。按“值”是否可分解，可将数据类型划分为两类：（1）原子类型：其值不可分解。通常是由语言直接提供。如JAVA语言的整型、实型、字符型等基本类型；（2）结构类型：其值可分解为若干个成分（或称为分量）。是用户借助于语言提供的描述机制自己定义的，它通常是由标准类型派生的，故它也是一种导出类型。如JAVA语言的数组。1.4 数据类型与抽象数据类型
7、抽象数据类型（抽象数据类型（Abstract Data Type简称简称ADT）抽象数据类型是指一个数学模型及定义在该模型上的一组操作。抽象数据类型可以看作是数据的逻辑结构及其在逻辑结构上定义的操作，而与其在计算机内部如何表示和实现无关。抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。在JAVA中，我们可以用类的说明来表示ADT，用类的实现来实现ADT。因此，JAVA中实现的类相当于是数据的存储结构及其在存储结构上实现的对数据的操作。ADT和类的概念实际上反映了程序或软件
8、设计的两层抽象：ADT相当于是在概念层（或称为抽象层）上描述问题，而类相当于是在实现层上描述问题。此外，JAVA中的类只是一个由用户定义的普通类型，可用它来定义变量（称为对象或类的实例）。因此，在JAVA中，最终是通过操作对象来解决实际问题的，所以我们可将该层次看作是应用层。例如，main程序就可看作是用户的应用程序。1.5 算法与性能分析-算法的特性算法的特性（1）有穷性：有限步骤之内正常结束，不能形成无穷循环，并且每一步骤在可接受的时间内完成。这里的有穷的概念并不是纯数学意义的，而是在实际应用当中合理的、可以接受的“有边界”。（2）确定性：算法中的每一个步骤必须有确定含义，无二义性。（3）
9、输入：有多个或0个输入。（4）输出：至少有一个或多个输出。（5）可行性：算法的每一步操作可通过已经实现的基本运算执行有限次而完成。1.5 算法与性能分析-算法的设计要求算法的设计要求1.正确性 程序中不含语法错误、算法的执行结果应当满足预先规定的功能和性能要求。2.可读性 一个好的算法首先应该便于人们理解和相互交流，其次才是机器可执行。可读性好的算法有助于人对算法的理解，难懂的算法易于隐藏错误且难于调试和修改。3.健壮性 一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。4.高效率和低存储量 最后，好的算法还应该具备时间效率高和存储量低
10、的特点。时间效率指的是算法的执行时间，对于一个具体的问题的解决通常可以有多个算法，对于执行时间短的算法其效率就高。存储量需求指的是算法在执行过程中所需要的最大存储空间。这两者都与问题的规模有关。1.5 算法与性能分析-算法的性能分析时间复杂度程序中所有语句的频度（该语句重复执行的次数）之和构成即是由嵌套最深层次的语句频度决定的。假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n)的增长率相同，则可记作：T(n)=O(f(n)称T(n)为算法的(渐近)时间复杂度。1.5 算法与性能分析-算法的性能分析和算法执行时间相关的因素：算法选用的策略问题的规模编写程序的语言编译程序产生的机器代
11、码的质量计算机执行指令的速度1.5 算法与性能分析-算法的性能分析【例例1.5】求求1+2+3+100的三种算法分析的三种算法分析算法1的时间复杂度为O(n)，我们称之为线性阶。算法2的时间复杂度为O(1)，我们称之为常量阶。算法3的时间复杂度为O(n2)，我们称之为平方阶。1.5 算法与性能分析-算法的性能分析空间复杂度算法的空间复杂度是指执行算法时所需的内存空间如果算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地空间，空间复杂度为o(1)。输入数据所占空间程序本身所占空间辅助变量所占空间算法的存储量1.6 小结 数据结构数据结构是指数据及数据之间的联系和这种联系在计算
12、机中的存储表示，包括数据的逻辑结构和存储结构。数据的逻辑结构逻辑结构是指各数据元素之间的逻辑关系，是用户按需要建立起来的，并呈现在用户面前的数据元素的结构形式。数据的存储结构存储结构是指数据在计算机内实际的存储形式。算法的设计算法的设计取决于数据的逻辑结构，算法的实现算法的实现依赖于采用的存储结构。算法算法是求解问题的步骤，它是指令的有限序列，其中一条指令表示一个或者多个操作。具有有穷性、确定性、可行性、有零个或多个输入和有一个或多个输出等特性。一个“好的”算法应达到正确性、易读性、健壮性和高效率与低存储量需求等目标。衡量一个算法的效率用时间复杂度来实现。THANKS上课啦THE POWERP
13、OINT TEMPALTE模块2线性表实例引入1逻辑结构2顺序存储结构3链式存储结构4应用举例5学习目的与要求重点：掌握顺序表和链表的逻辑描述和存储实现难点：顺序表和单链表的实现和应用线性结构线性结构的特点：线性结构的特点：在数据元素的非空有限集中，数据元素是有序的，排在某个数据元素b之前的数据元素a称为b的直接前驱直接前驱，而数据元素b称为a的直接后继直接后继。且具有如下特点：（1）存在唯一的一个被称为“第一个”的数据元素。（2）存在唯一的一个被称为“最后一个”的数据元素。（3）除第一个之外，集合中的每个数据元素均只有一个直接前驱。（4）除最后一个之外，集合中的每个数据元素均只有一个直接后继
14、。2.1 实例引入 【实例【实例1】银行办理业务时顾客的队列、26个英文字母表、班级同学的点名册、12生肖列表等都是线性结构。【实例【实例2】某学校成立了移动互联社团，今天招募社团人员，假设我们是社团负责记录报名信息的人员，我们需要做什么呢？2.2 线性表的逻辑结构定义：定义：具有相同数据类型的具有相同数据类型的 n n（0 0）个数据元素的有限序（个数据元素的有限序（次序次序）列。）列。记作记作（a1,a2,ai-1,ai,ai+1,an）其中其中,ai 是表中数据元素，是表中数据元素，n 是表长度是表长度，i为数据元素为数据元素ai 在线性表中的位序。在线性表中的位序。【例2.1】某班前五
15、名学生语文成绩（99，98，97，95，90）是线性表，表中每个数字是一个结点。【例2.2】一年四季（春，夏，秋，冬）是一个线性表，表中的结点是一个字符。2.2 线性表的逻辑结构【例2.3】学生成绩表是一个线性表，表中每一行（一条记录）是一个结点。一条记录是由学号、姓名、性别、数学成绩和语文成绩5个数据项组成。线性表的特点线性表的特点:n同一线性表中元素具有相同特性。同一线性表中元素具有相同特性。在在Java中，可以用类定义数据元素的数据类型。中，可以用类定义数据元素的数据类型。n相邻数据元素之间存在顺序关系。相邻数据元素之间存在顺序关系。n除第一个元素外，其他每一个元素有且仅有一个直接前趋。
16、除第一个元素外，其他每一个元素有且仅有一个直接前趋。n除最后一个元素外，其他每一个元素有且仅有一个直接后继。除最后一个元素外，其他每一个元素有且仅有一个直接后继。线性表的逻辑结构是线性结构线性表的逻辑结构是线性结构2.2.2 线性表的基本运算（1）初始化initList（L）：构造一个空的线性表L，即表的初始化。（2）求表长listLength（L）：求线性表L中的结点个数。（3）取值getNode（L,i）：取线性表L中的第i个结点（1iListLength（L）。（4）定位locateNode（L,e）：在线性表L中查找值为e的结点，并返回该结点在线性表L中的位序。若线性表L中有多个结点的
17、值和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分
18、别由两个线性表LA和LB表示，要求将LB中存在但在LA中不存在的数据元素插入到表LA中。算法思想：（1）依次从LB中取出一个数据元素；/使用getNode（L,i）（2）判断该数据元素在LA中是否存在；/使用locateNode（L,e）（3）若不存在，则插入到LA中。/使用insert（L,e，i）算法实现：上述归并算法是利用基本操作完成的，那么每一种基本操作如何实现？这上述归并算法是利用基本操作完成的，那么每一种基本操作如何实现？这要涉及存储结构，只有确定了存储结构才能实现基本算法。要涉及存储结构，只有确定了存储结构才能实现基本算法。2.3 线性表的顺序存储结构及运算实现【学习任务学习任务
19、】理解线性表在顺序存储结构下的特点，掌握顺序表的表示、相关算法及程序实现定义：定义：线性表的顺序存储是指把线性表的各个结点按逻辑次序依次存储在一组地址连续的存储单元里。用这种方法存储的线性表简称为顺序表。结点的存储地址：结点的存储地址：假设线性表中所有结点的类型相同，设表中每个结点占用L个存储单元，并以所占的第一个单元的存储地址作为该结点的存储地址。则线性表中第i+1个结点的存储地址LOC（ai+1）和第i个结点的存储地址LOC（ai）之间满足下列关系：LOC（ai+1）=LOC（ai）+L 一般来说，线性表的第i个数据元素ai的存储地址为：LOC（ai）=LOC（a1）+（i-1）*L 式中
20、LOC（a1）是线性表第一个结点的存储地址，通常称作线性表的起始地址或基地址。2.3.1 顺序表的定义顺序表的特点：顺序表的特点：以元素在计算机中的物理位置相邻来表示线性表中数据元素之间的逻辑关系，如图2.2所示。在顺序表中，每个结点a i 的存储地址是该结点在表中的位置i的线性函数。只要知道基地址和每个结点的大小，就可在相同时间内求出任一结点的存储地址，从而实现对顺序表中数据元素的随机存取。注意：顺序存储结构通常利用高级程序设计语言中的一维数组来表示。注意：顺序存储结构通常利用高级程序设计语言中的一维数组来表示。2.3.1 顺序表的定义顺序表的类定义如下：顺序表的类定义如下：说明：该类定义的
21、是整型数组，在实际应用中，可根据具体情况而定。说明：该类定义的是整型数组，在实际应用中，可根据具体情况而定。2.3.2 顺序表的基本运算实现顺序表的基本操作顺序表的基本操作：初始化、求表长、取值、查找、插入、删除等。1插入操作及程序实现插入操作及程序实现（1）插入运算的逻辑描述）插入运算的逻辑描述 线性表的插入运算是指在表的第i（1in+1）个位置上，插入一个新结点e，使长度为n的线性表：（a1，a2，ai，ai+1，an）。变成长度为n+1的线性表：（a1，a2，ai，e，ai+1，an）。（2）顺序表插入操作过程）顺序表插入操作过程 在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，
22、因此必须将表中位置为n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点e。仅当插入位置i=n+1时，才无须移动结点，直接将e插入表的末尾。如图2.3所示。2.3.2 顺序表的基本运算实现注意：由于数组空间大小在声明时确定，当L.lengthdata.length时，表空间已满，不可再做插入操作。当插入位置i的值L.length+1或i1时为非法位置，不可做正常插入操作。2.3.2 顺序表的基本运算实现（3）在整型顺序表的某位置上插入一个值为）在整型顺序表的某位置上插入一个值为 e 的整型元素。具体算法描述如下的整型元素。具体算法描述如下publ
23、ic class LineList public boolean insert(int i,int e)int j;if(length=data.length)/表空间已经满,不能插入 System.out.println(The table is overflow.);return false;if(i length+1)/插入位置是否正确 System.out.println(The position is mistake.);return false;for(j=length-1;j=i;j-)dataj+1=dataj;datai=e;length+;return true;2.3.2
24、 顺序表的基本运算实现（4）算法时间复杂度）算法时间复杂度 算法的时间主要花费在for循环中的结点后移语句上，该语句的执行次数是n-i+1。当i=n+1：移动结点次数为0，即算法在最好情况下时间复杂度是O(1)。当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是O(n)。假设pi表示在表中第i个位置上插入一个结点的平均概率，则在长度为n的线性表中插入一个元素时需移动元素次数的平均值为：不失一般性，假设在表中任何合法位置（1in+1）上的插入结点的机会是均等的，则Pi=1/(n+1)因此，在等概率插入的情况下，即在顺序表上进行插入运算，平均要移动一半结点，平均时间复杂度是O(n)。2.3
25、.2 顺序表的基本运算实现顺序表的基本操作顺序表的基本操作：初始化、求表长、取值、查找、插入、删除等。2删除操作及程序实现删除操作及程序实现（1）删除运算的逻辑描述）删除运算的逻辑描述线性表的删除运算是指将表的第i（1in）个结点删去，使长度为n的线性表 （a1，ai-1，ai，ai+1，an）变成长度为n-1的线性表 （a1，ai-1，ai+1，an）（2）顺序表插入操作过程）顺序表插入操作过程 在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点e。仅当插入位置i=n
26、+1时，才无须移动结点，直接将e插入表的末尾。如图2.3所示。2.3.2 顺序表的基本运算实现注意：当L.length0时，表为空，不可做删除操作。当要删除元素的位置i不在表长范围（即i1或iL.length）时，为非法位置，不能做正常的删除操作。2.3.2 顺序表的基本运算实现（3）在整型顺序表中删除某位置上的元素。具体算法描述如下：）在整型顺序表中删除某位置上的元素。具体算法描述如下：public class LineList public boolean delete(int i)int j;if(length0)/表为空,不能删除 System.out.println(The tabl
27、e is null);return false;if(ilength)/检查删除位置是否存在 System.out.println(The position is mistake.);return false;for(j=i;jlength;j+)dataj=dataj+1;length-;return true;2.3.2 顺序表的基本运算实现（4）算法时间复杂度）算法时间复杂度 算法的时间主要花费在for循环中的结点前移语句上，该语句的执行次数是n-i。i=n时，结点的移动次数为0，即为O(1)。i=1时，结点的移动次数为n-1，算法时间复杂度分别是O(n)。假设pi表示在表中第i个位置上
28、删除一个结点的平均概率，则在长度为n的线性表中删除一个元素时需移动元素次数的平均值为：不失一般性，假设在表中任何合法位置（1in）上的删除结点的机会是均等的，则Pi=1/n因此，在等概率插入的情况下，即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。2.3.3 顺序表在Java类库中的实现1Java类库中的java.util.ArrayList类实现了顺序表的功能，顺序表的基本运算都可以通过该类提供的成员方法实现，具体如下：1)构造方法构造方法public ArrayList()/默认的构造方法，构造一个初始容量为10的空列表 public ArrayList(i
29、nt initialCapacity)/构造一个具有指定初始容量的空列表2)常用成员方法常用成员方法public boolean add(Object obj)/将指定的元素添加到此列表的尾部public void add(int index,Object obj)/将指定元素插入到此列表中的指定位置。此时，index位置开始处的所有元素逐个向右移动一个位置public boolean remove(Object obj)/删除此列表中首次出现的指定元素，如果此列表包含指定的元素，则返回truepublic Object remove(int index)/删除指定位置的元素，向左移动所有后续
30、元素（将其索引减1）2.3.3 顺序表在Java类库中的实现2public void removeRange(int fromIndex，int toIndex)/删除列表中索引在fromIndex（包括）和toIndex（不包括）之间的所有元素public void clear()/删除此列表中的所有元素public int size()/返回此列表中的元素个数public boolean isEmpty()/如果此列表中没有元素，则返回truepublic boolean contains(Object obj)/如果列表中包含指定的元素，则返回truepublic int indexOf
31、(Object obj)/返回此列表中第一次出现的指定元素的索引，如果列表不包含该元素，则返回-1public int lastIndexOf(Object obj)/返回此列表中最后出现的指定元素的索引，如果列表不包含该元素，则返回-1public Object get(int index)/获取指定位置的元素public Object set(int index，Object obj)/用指定的元素替代此列表中指定位置上的元素public Object toArray()/把此列表中的元素复制到一个新的数组中2.4 线性表的链式存储结构及运算实现【学习任务】理解线性表在链式存储结构下的特点
32、，掌握链表的表示、相关算法及程序实现 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表的数据元素。用链式存储的线性表简称为链表（Linked List）。根据链表结点的不同结构，链表分为单链表、循环链表和双链表 链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此，可以随机地、快速地存取表中任一元素。然而，顺序存储结构在插入和删除运算中可能需要大量移动元素，而且在程序编译前就规定好数组元素的多少(即数组长度)，事先难估计，多了造成浪费存储空间，少了
33、不够用。为了解决顺序表遇到的这些困难，本节将讨论线性表的另外一种存储结构链式存储结构。2.4.1 单链表单链表的存储结构单链表的存储结构单链表的结点结构如图所示。data域存放结点值的数据域。next域存放结点的直接后继的地址（位置）的指针域（链域）。单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。终端结点无后继，故指针域为空，用或null表示。2.4.1 单链表单链表的类定义如下：单链表的类定义如下：public class LinkedList private int data;/数据域，可根据实际情况修改 private Li
34、nkedList next;/指针域，存放当前元素直接后继元素的地址 private LinkedList head;/链表头指针 public LinkedList()/构造方法 /成员方法 public int getData()return data;public void setData(int data)this.data=data;public LinkedList getNext()return next;public void setNext(LinkedList next)this.next=next;2.4.1 单链表【例【例2.5】线性表（】线性表（a1，a2，a3，a4
35、，a5，a6）的单链表存储结构示意图）的单链表存储结构示意图2.4.1 单链表 由于我们常常只注重结点间的逻辑顺序，不关心每个结点的实际位置，可以用箭头来表示链域中的指针，线性表（a1，a2，a3，a4，a5，a6）的单链表就可以表示为图2.7形式。不同的程序设计语言实现指针的方法不同，在Java中，使用“对象引用”来实现指针，同时，Java语言提出了利用java.util.LinkedList的类库提供的链表类供编程者使用，用户可以通过该类库简单地实现指针操作。2.4.1 单链表单链表的基本运算单链表的基本运算（1）插入运算 算法分析 插入运算是将值为e的新结点插入到表的第i个位置上，即插入
36、到ai-1与ai之间。具体操作如图所示。2.4.1 单链表具体步骤：具体步骤：找到ai-1存储位置p创建一个新结点对象s将值e赋值给新结点s的数据域新结点s的指针域指向结点ai修改结点ai-1的指针域,使其指向新结点s2.4.1 单链表算法实现算法实现：public class LinkedList boolean insert(LinkedList newNode,int i)/在带头结点链表第 i 个结点处插入新元素 newNode LinkedList p=head;int k=0;while(p!=null&k i-1 )/找第 i-1个结点 p=p.next;k+;if(p=null
37、)System.out.println(无效的插入位置!n);/终止插入 return false;newNode.next=p.next;p.next=newNode;return true;2.4.1 单链表（2）删除运算）删除运算 算法分析算法分析 删除运算是将表的第i个结点删去。具体操作如图2.9所示。具体步骤：具体步骤：找到ai-1的存储位置p令p.next指向ai的直接后继结点2.4.1 单链表算法实现算法实现：public class LinkedList boolean delete(int i)/在 带头结点链表中删除第 i 个结点 LinkedList p,q;p=head
38、;int k=0;while(p!=null&k i-1)p=p.next;k+;/找第 i-1个结点 if(p=null|p.next=null)/i值不合理 System.out.println(无效的删除位置!n);return false;else /删除元素 q=p.next;p.next=q.next;return true;2.4.2 双向链表1双向链表的存储结构双向链表的存储结构 在单链表中，从任何一个结点可以找到它的后继结点，但是寻找它的前趋结点，就需要从表头开始顺序查找。我们可用双向链表来克服单链表的这种缺点，在双向链表中，每一个结点除了数据域外，还包含两个指针域，一个指针
39、（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。双向链表结点结构及一般表示法如下图所示。2.4.2 双向链表双链表的类定义如下：public class DbLinkedList private int data;/数据域，可根据实际情况修改 private DbLinkedList prior;/指针域，存放当前元素直接前驱元素的地址 private DbLinkedList next;/指针域，存放当前元素直接后继元素的地址 private DbLinkedList head;/链表头指针 public DbLinkedList()/构造方法 /成员方法 pub
40、lic int getData()return data;public void setData(int data)this.data=data;public DbLinkedList getPrior()return prior;public void setPrior(DbLinkedList prior)this.prior=prior;public DbLinkedList getNext()return next;public void setNext(DbLinkedList next)this.next=next;2.4.2 双向链表双向链表的基本运算双向链表的基本运算2.4.2
41、 双向链表（1）插入运算算法实现）插入运算算法实现public class DbLinkedList boolean insert(DbLinkedList newNode,int i)/在带头结点的双链表第 i 个结点处插入新元素 newNode DbLinkedList p=head;int k=0;while(p!=null&k i-1 )/找第 i-1个结点 p=p.next;k+;if(p=null)System.out.println(无效的插入位置!n);/终止插入 return false;newNode.next=p.next;newNode.prior=p;p.next.p
42、rior=newNode;p.next=newNode;return true;2.4.2 双向链表（2）删除运算算法实现）删除运算算法实现public class DbLinkedList boolean delete(int i)/删除带头结点的双链表head上的第i个结点 DbLinkedList p;p=head;int k=0;while(p!=null&k i)p=p.next;k+;/找第 i个结点 if(p=null|p.next=null)/i值不合理 System.out.println(无效的删除位置!n);return false;else /删除元素 p.next.p
43、rior=p.prior;p.prior.next=p.next;return true;2.4.3 循环链表1单循环链表单循环链表 在单链表中，将终端结点的指针域null改为指向表头结点或开始结点，使得链表头尾结点相连，就构成了单循环链表，如下图所示。注意：判断空链表的条件是head=head.next;2.4.3 循环链表【例2.6】对两个单循环链表L1（a1，a2，an）和L2（b1，b2，bn）进行合并。分析：若在单链表或头指针表示的单循环表上做这种链接操作，都需要遍历第一个链表，找到结点an，然后将结点b1链到an的后面，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需
44、修改指针，无须遍历，其执行时间是O(1)。链接操作如图2.15所示。2.4.3 循环链表 与单循环链表类似，对双链表也可以利用头、尾结点的前驱、后继指针域链接成头尾相接的形式，称为双循环链表双循环链表。如图2.16所示。2.4.4 链表在Java类库中的实现 Java类库中的java.util.LinkedList类实现了链表的功能，链表的基本运算都可以用该类的成员方法实现，具体如下：1）构造方法public LinkedList()/用来创建一个单链表对象2）常用成员方法public boolean add(Object obj)/在表尾添加一个元素public boolean add(in
45、t index,Object obj)/在此列表中指定的位置插入指定的元素public boolean addFirst(Object obj)/在表头添加一个元素public boolean addLast(Object obj)/在表尾添加一个元素public boolean remove(Object obj)/从此列表中删除首次出现的指定元素 public Object removeFisrt()/删除并返回表头元素2.4.4 链表在Java类库中的实现 public Object removeLast()/删除并返回表尾元素public Object remove(int index
46、)/删除此列表中指定位置处的元素public int size()/获取此列表中元素个数public Object get(int index)/获取指定位置的元素public Object getFirst()/获取表头元素public Object getLast()/获取表尾元素public Object set(int index，Object obj)/将此列表中指定位置的元素替换为指定的元素public boolean contains(Object obj)/如果列表中包含指定的元素，则返回truepublic void clear()/删除此列表中的所有元素public int
47、 indexOf(Object obj)/获取某个元素的位置public int lastIndexOf(Object obj)/返回此列表中最后出现的指定元素的索引，如果列表不包含该元素，则返回-12.5 应用举例2.5.1 使用顺序表实现使用顺序表实现 教师电话管理系统教师电话管理系统【问题描述】编程实现对教师电话信息的管理，要求可以对教师电话信息记录进行添加、删除、查询、浏览等操作，并采用顺序存储结构存储数据。【算法思想】教师电话信息表是一个线性表，应建立一个顺序表存储教师电话信息，使用数组来实现。数据元素是一条记录，不是整数、实数等基本数据类型，因此，应定义一个类，表示数据元素类型。2
48、.5 应用举例2.5.2 使用链表实现使用链表实现 教师电话管理系统教师电话管理系统【问题描述】编程实现对教师电话信息的管理，要求可以对教师电话信息记录进行添加、删除、查询、浏览等操作，并采用链式存储结构存储数据。【算法思想】教师电话信息表是一个线性表，如果采用链式存储结构存储数据，就要建立一个链表，链表中的结点是教师电话信息记录。数据元素是一条记录，不是整数、实数等基本数据类型，因此，应定义一个类，表示数据元素类型。2.6 小结本模块介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序表和链表。通过对它们的讨论可知顺序存储有三个优点：（1）方法简单，各种高级语言中都有数组，容易实现。
49、（2）不用为表示结点间的逻辑关系而增加额外的存储开销。（3）顺序表具有按元素序号随机访问的特点。但它也有两个缺点：（1）在顺序表中做插入删除操作时，平均移动大约表中一般的元素，因此对n较大的顺序表效率低。（2）需要预先分派足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反链表的优缺点恰好与顺序表相反2.6 小结本模块介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序表和链表。通过对它们的讨论可知顺序存储有三个优点：（1）方法简单，各种高级语言中都有数组，容易实现。（2）不用为表示结点间的逻辑关系而增加额外的存储开销。（3
50、）顺序表具有按元素序号随机访问的特点。但它也有两个缺点：（1）在顺序表中做插入删除操作时，平均移动大约表中一般的元素，因此对n较大的顺序表效率低。（2）需要预先分派足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反链表的优缺点恰好与顺序表相反THANKS上课啦THE POWERPOINT TEMPALTE模块3栈和队列实例引入1栈2队列3应用举例4小结5学习目的与要求重点：栈和队列的特点栈和队列的进出运算循环队列的特点及基本运算难点：栈和队列的相关运算使用栈和队列解决实际应用问题3.1 实例引入【实例【实例1】栈的实例】栈的实例
