数据结构（Java语言版）全套课件

第1章绪论入门即上路，本章引导上路。要求掌握数据结构和算法概念；理解算法分析方法。铁锅里掺适量水烧开，放入秋葵，两根筷子架起放了鳕鱼和香料的盘子，转微火盖锅盖蒸。好香！10分钟内要回来，这之前发个说说：处处皆结构，处处皆算法！哦原来，锅里架构是数据结构，烹饪步骤是算法。提纲1.1数据结构1.2算法概念1.3算法分析1.4绪论总结1.1

数据结构1.1.1基本概念概念数据（Data）：能够被计算机程序识别、存储、加工和处理的描述客观事物的符号集合的总称。数据是信息的载体，数据赋予含义成为信息。数据项（DataItem）：又称为字段或域，是数据元素的组成部分，具有不可分割性和独立含义。数据元素（DataElement）：又称为元素，是数据的基本单位，是一个数据整体的基本表示。数据对象（DataObject）：又称为数据元素类，是性质相同的数据元素的集合。数据元素是数据对象的实例。数据结构（DataStructure）：相互之间存在着一种或多种关系的数据元素的集合。抽象数据类型（AbstractDataType，ADT）：从数学模型角度抽象出来的逻辑数据结构以及其上的运算，不考虑具体存储结构和实现细节；它反映的是定义与实现相分离的设计哲学，包含数据对象、数据关系和基本运算。1.1.1基本概念比如定义复数抽象数据类型Complex：ADTComplex{数据对象：D={e1，e2|e1，e2均为实数}数据关系：R={<e1，e2>|e1是复数的实部，e2是复数的虚部}基本运算：AssignComplex(&z，v1，v2)：构造复数Z。GetReal(z，&real)：返回复数z的实部值。GetImag(z，&Imag)：返回复数z的虚部值。Add(z1，z2，&sum)：返回两个复数z1、z2的和。}ADTComplex1.1.1基本概念举例地球是装人的容器，人是数据对象，张三是数据元素，人的某个属性如肤色是数据项，人与人之间存在的关系与人一道在地球上构成了数据结构，而地球上有人，人与人之间有直接或间接关系发生，就是抽象数据类型的表示。1.1.2逻辑结构数据的逻辑结构分为集合、线性结构、树状结构、图形结构4类。集合具有相同性质元素构成集合。集合中元素的关系极为松散，关系为“属于同一个集合”。举例：这之前，我们都不认识，是数据结构这门课程让我们有缘走到了一起，来到这间教室学习。教室看作集合，教室里的人看作元素，有些同学一学期也不说话交流（没有关系），但他们归属于同一个教室。1.1.2逻辑结构线性结构数据元素之间是线性关系的数据结构。特点是元素之间为“一对一”关系。举例1：甲用暗号1联系乙，乙用暗号2联系丙，丙用暗号3联系丁。保密工作只能单线联系。甲乙丙丁这些元素之间的关系是单一的、一个对一个的。举例2：教室里坐了n个同学，按照学号顺序依次回答问题：什么是数据结构？n个学生数据元素这种依次关系，就是一对一的关系。1.1.2逻辑结构树状结构数据元素之间是层次关系的数据结构。特点是元素之间可以为“一对多”关系。举例1：旧楼房的楼梯间，有线电视同轴电缆从1楼到顶楼通过分支器连接和分户，使得家家有电视看。这种分支器输入为1个通道输出为n个通道，构成了一对多关系；层层分支整个线路构成了树状结构。举例2：单位的组织结构，是典型的层次树状结构！倒立的树状结构！1.1.2逻辑结构图形结构数据元素之间的关系更复杂，可以包含一对一、一对多、多对一，多对多的关系。特点是元素之间可以为“多对多”关系。举例：新同学找进校门找不到路，没有老同学在身边带没关系，打开手机校园地图，房屋线路一目了然吧；打开百度地图、高德地图看城市交通雷同。从宿舍到教室有多条路，从教室到食堂有多条路，从食堂回宿舍还是有很多条路啊！在这个例子中，体现了元素之间多对多的关系。1.1.2逻辑结构1.1.3存储结构顺序存储结构顺序存储结构是在连续的存储单元中存放数据元素，元素的物理存储次序与逻辑次序一致，即物理位置相邻的元素在逻辑上也是相邻的。举例：大学英语四六级考试考场座位编号，是按照准考证号的顺序连续编号的。在这个例子中，相邻准考证号在物理座位上也是相邻的。1.1.3存储结构链式存储结构链式存储结构使用地址分散的存储单元存放数据元素，即物理上相邻的数据元素逻辑上不一定相邻，数据元素之间的逻辑关系通常用指针表示，记录前驱和后继的存储地址。举例：大学教室里，同学们来上课可以随便坐，不一定学号相邻的同学坐在一起。当老师让学生按照学号从小到大举手/站立报号考勤时，这种乱坐现象并不影响考勤。在这个例子中，虽然学号连续，但是学生可以分散坐，体现了链式存储结构。1.1.3存储结构索引存储结构索引存储结构时在存储数据元素的基础上增加了索引表，可以用它来实现快速查找数据元素。举例：班干部名单，叫到某个班干部如“2组组长张三”，其职责和管理对象也就呼之而出！这个例子中，班干部名单可以看作索引表。1.1.3存储结构散列存储结构散列存储结构又叫哈希存储结构，数据元素的存储地址是由该数据元素关键字散列函数计算出来。举例：学生照毕业照，按照个子高矮站位，中间站高个子两边站矮个子；若有相同身高则站另一边，依此类推。在这个例子中，散列函数就是对身高求值，从而决定所站位置（存储地址）。1.1.3存储结构1.2算法概念1.2.1算法定义算法是对问题求解的步骤描述。算法处处皆在，读者思想驰骋，能否信手拈来？举例1：同学们跨进大学校门报到，从健康码检查、x处注册缴费、y处安排住宿、z处集合领书等流程是合理的，不能是住宿费学费还没有缴就可以住宿、领书和上课了，也不能说没有检查健康码就进学校了，这些原则上是不允许的。在这个例子中，学生的执行流程体现了算法的执行步骤。举例2：作者要完成这本书的编写，首先要市场调研：目前流行的教材特点和高校开设这门课程的教学情况，主要是发现存在的问题；然后构思如何编写一本通俗易懂而实用的教材以及如何在课堂教学中实施；接下来就是写出目录框架；再接下来就是查阅和搜集众多参考文献和素材；最后才是花大量时间和精力去撰写内容，并反复检查、打磨和优化，以及责编辛勤校验、排版。倘若作者不了解市场而盲目出书，则不会写出读者欢迎的书。在这个例子中，作者怀揣情怀编写一本付出心血的教材体现了算法的执行步骤。1.2.2算法特性算法具有以下5个特性。有穷性算法是由若干条指令组成的有穷序列，而非永不停止。在算法1.1中，while(true)是“永动机”，循环永远跳不出来导致后面的语句无法执行（事实上打开注释，报错“语句不可达”），注释掉之后，该算法具有有穷性。确定性算法的每一条语句有特定的含义，无歧义。可行性算法在当前环境条件下可以通过有限次运算实现。输入性算法有零个或多个输入。算法1.1的algorithm1_1方法有2个输入参数，在设计算法时也可以没有输入参数或更多输入参数。输出性算法有一个或多个输出。一般地，算法都有输出；若输出是多个，则在程序设计时可以把多个输出放到集合中再逐个输出。1.2.2算法特性【算法1.1】理解算法5个特性。

publicStringalgorithm1_1(intx,inty){//输入性：2个

//while(true){}//无穷性：破坏了算法后续语法

for(inti=1;i<=10;i++){//有穷性：算法运行时间有限

System.out.println("先循环10次再说"+i);

}

intz=x+y; //确定性：语法没问题

StringoutPut=z+"";//确定性：语法没问题

returnoutPut; //输出性：1个

}//可行性：运行之后能实现

1.2.3算法目标算法设计目标，就是设计出好的算法。好的算法具有下列5个特性。正确性算法能够满足具体问题的需求，程序运行正常，通过测试能够达到预期目标。健壮性算法对非法数据和操作有处理机制。易读性算法遵循标识符命名规则，简洁易懂，适当注释，方便阅读和理解，也便于后期维护和扩展。高效性算法运行的时间短。低存储性算法所需的存储空间低。前3点是算法的基本要求，后2点是好算法的评判标准。1.2.4算法描述自然语言自然语言即接近口头描述。用自然语言描述算法简单易懂，但严谨性较差。程序语言程序语言如Java、C#、Python等。用某种具体的程序设计语言来描述算法较严谨，算法可直接在计算机上执行，但非专业人士难以理解。伪代码伪代码是介于自然语言和程序语言之间的描述方式。用伪代码描述算法可以忽略严格的语法规则，接近用户理解，且容易将其转换为程序语言执行。1.2.4算法描述例如：根据学号查找学生。（1）用自然语言描述：从学号列表第1个元素开始，与给定学号进行比较：若相等则查找成功；若不相等则比较下一个元素，直到最后一个元素比较完若前面都没有找到。这个过程要么查找成功，要么查找失败。（2）用程序语言描述：如算法1.2。【算法1.2】用程序语言描述算法。publicintalgorithm1_2(intkey){//key为给定学号

int[]studentNo={101,102,103,104,105};//学号列表for(inti=0;i<studentNo.length;i++)if(studentNo[i]==key)//比较

return1;//查找成功

return0; //查找失败}

（3）用伪代码描述key=100for(学号in学号列表){ if(学号==key)

查找成功，结束}查找失败，结束1.3算法分析算法分析主要是分析算法的执行时间和存储空间，它们是评判一个算法好与坏的重要指标。从执行时间上分析就是算法的时间复杂度；从存储空间上分析就是算法的空间复杂度。1.3.1算法时间复杂度

1.3.1算法时间复杂度

1.3.1算法时间复杂度1.3.1算法时间复杂度

举例1：1个窗口，8个人排队做核酸。若做核酸1个人的平均时间为5秒，则大约需40秒；假设人数增加为800，则需4000秒。显然，问题规模n从8到800，时间随之增加。举例2：1000个窗口，不超过1000人做核酸。来一个做一个不用排队，同时来也无妨！显然只需1个人做核酸的时间：5秒。做1个人和做1000个人的核酸所花时间皆5秒，这种情形的时间复杂度与问题规模无关。1.3.1算法时间复杂度【算法1.4】疫情下做核酸检查所花时间与问题规模之间的关系，假设检查1个人需花5秒。publicvoidalgorithm1_4(intn,intwindows){//n为问题规模，windows为窗口数

inttotalTime=0;//所花总时间，初始值为0

if(windows==1)//只有1个窗口

while(n--!=0){totalTime+=5;//执行n次

} elseif(windows>=n)//窗口数不少于人数

totalTime=5; //执行1次 }

在算法1.4中，分析了算法时间复杂度与问题规模之间的关系，可能要取决于其他条件因素具有不确定性，这里为窗口数：当窗口数大于等于人数（问题规模）时，时间复杂度与问题规模无关；反之相关。之所以一个算法的时间复杂度可能不确定，是因为其有最好情况、最坏情况和平均情况。看一个算法好与坏，最坏情况是主要考虑因素。1.3.1算法时间复杂度【思考与练习1.1】举一些时间复杂度与问题规模无关的算法例子。答：例如“秒杀”系统，系统设置了只过滤5个名额，5千、5万、50万去抢都无关，执行时间不受影响。分析下面的算法，其时间复杂度与问题规模n是否相关，为什么？publicintthinkPad1_1(intn){//n为问题规模

intx=0,y=0;

while(x<n){

x++;

returny;

}

returnx;

}

答：无关。因为无论问题规模是多少，算法中核心语句只执行1次。1.3.1算法时间复杂度语句频度语句频度是指语句重复执行的次数。我们在计算时间复杂度时，不必将每条语句执行的次数相加，一般只考虑执行次数最多的语句，如循环最内层的语句对时间复杂度贡献最大，这样的语句我们称为关键语句。在算法1.3中，"俺在循环之内！"语句对算法时间复杂度贡献最大，故其执行次数可以代表该算法的时间复杂度。算法优化实现同一个功能，采用不同的算法往往时间复杂度不同。举例：毕业设计文档若干，包括论文和过程材料共11个；假设1个指导老师带了10个学生，师生共同打磨修改优化完成了所有文档之后，最后要求按照文档清单顺序装袋，装袋前师生在有些文档上须签字，每个袋子装1个学生的材料。如何高效完成装袋，不同算法思想其效率即时间复杂度是不一样的。1.3.1算法时间复杂度【思考与练习1.2】针对上面的举例，分析下面的算法1和算法2的时间复杂度，若是你，会选择哪一种算法，为什么？算法1：指导老师建11个文件夹，分别对应11种材料，如“任务书”、“开题报告”、“指导记录表”等等，按材料归类，完成打印、签字、装订、装袋。算法2：指导老师建10个文件夹，分别对应10个学生，如“888-张三”、“999-李四”等等，按学生归类，完成打印、签字、装订、装袋。1.3.1算法时间复杂度答：算法1描述：Step1.新建11个材料文件夹；Step2.10个学生的所有文档以材料文件夹归类；Step3.按照文档清单顺序装袋要求，依次打印“任务书”、“开题报告”、“指导记录表”等文件夹中所有文档；（这一步若按学生为单位打印，打印操作要跳转，繁琐）Step4.完成签字后将纸质文档整理归类为以学生为单位，装订并装袋。

算法2描述：Step1.新建10个学生文件夹；Step2.每个学生的所有文档放入其中；Step3.按照文档清单顺序装袋要求，在打印每个学生文件夹材料时按装袋顺序打印；Step4.完成签字后将纸质文档装订并装袋。显然，算法2没有繁琐的打印操作跳转或打印后人工整理归类工作，节省了时间。1.3.1算法时间复杂度从上面的例子不难看出，优化算法就是减少算法的时间复杂度，正如学生从宿舍到教室，在很多条道路中选择最优的一条道路一样。1.3.1算法时间复杂度

1.3.1算法时间复杂度

1.3.1算法时间复杂度

1.3.1算法时间复杂度

1.3.1算法时间复杂度

1.3.1算法时间复杂度

1.3.2算法空间复杂度

举例：期末高等数学考试需要草稿纸，倘若监考老师要求每一个交卷的学生带上草稿纸扔到门口边的一个垃圾桶

里，监考老师就节省了在桌上收草稿纸的时间，而只需收试卷，但增加了辅助空间：垃圾桶。在这个例子中，以增加空间换取时间，这是我们算法设计中常采用的思路。1.3.2算法空间复杂度算法空间复杂度注意2点：（1）算法空间复杂度主要是看算法所需的临时变量或辅助空间个数；（2）随着问题规模增加，所需的临时变量或辅助空间个数是否增加？若不增加则空间复杂度为O(1)；否则看其与问题规模关系，或为O(n)或为O(n2)等。1.3.2算法空间复杂度

1.3.2算法空间复杂度

1.3.2算法空间复杂度

1.3.2算法空间复杂度

1.4绪论总结

第2章线性表

本章讲解线性表。要求理解线性表概念、基本操作；掌握线性表的存储结构；掌握顺序表的基本操作；掌握链表的基本操作；灵活应用线性表。北京有冰糖葫芦，咱们成都有糖油果子。老远处看还真难以区分，在成都的北京人以为要吃到家乡的冰糖葫芦了；在北京的成都人以为要吃到家乡的糖油果子了。哈哈，原来它们尽管味道霄壤之别，却长得相像，皆是线性结构。提纲2.1线性表基本概念2.2顺序表2.3单链表2.4双链表2.5循环链表2.6线性表应用2.7线性表学习总结2.1线性表基本概念

2.1线性表基本概念如图2.1所示，太阳公公和小朋友们手拉手，他的直接前驱是2号小朋友，直接后继是4号小朋友；1号和5号小朋友分别是太阳公公的间接前驱和间接后继。2.1线性表基本概念线性表的抽象数据接口描述如下：publicinterfaceIList{

publicvoidclear(); //将线性表置成空表

publicbooleanisEmpty(); //判断线性表是否为空表

publicintlength(); //返回线性表的长度

publicObjectget(inti)throwsException;//获取第i个元素

publicvoidinsert(inti,Objectx)throwsException;//i位置插入x

publicvoidremove(inti)throwsException;//删除位置i的元素

publicintindexOf(Objectx); //返回元素x首次出现的位序号

publicvoiddisplay(); //输出线性表所有元素

}

根据存储结构不同，线性表分为顺序表和链表2大类。2.2顺序表以顺序存储结构进行存储的线性表称为顺序表。2.2.1顺序表存储结构顺序表存储结构采用顺序存储方式，逻辑上相邻的元素物理存储位置也相邻，元素存储都是连续的。由这种结构特点可知，顺序表可以随机访问快速定位某个元素，查找效率高，但删除和插入元素时，需要移动大量元素，效率低。举例：老师在教室里选择1列或1行无空位连续坐着n个学生的区域，假设有座位编号，老师可以迅速定位某个学生，如3号学生玩手机优先回答问题吧；若把3号学生请出教室后仍保持这个区域顺序存储，则4号坐到3号处，5号坐到4号处，依此类推n号坐到n-1号处；若3号学生在教室外呆了一会儿反省了，老师又让他坐回原来位置，则n-1号先坐回n号处。。。。。。此时的3号坐回4号处，原3号学生坐回3号处。在这个例子中，n个学生的区域是顺序表存储结构，对顺序表的查找较容易而对其删除和插入较麻烦。2.2.2顺序表基本操作顺序表类的描述如下：publicclassSeqListimplementsIList{

publicObject[]listItem;//顺序表用一维数组作为存储空间

publicintcurLen;//顺序表当前长度

publicintmaxSize;//最大分配空间

publicSeqList(intmaxSize){//构造存储空间为maxsize的顺序表

curLen=0;

maxSize=maxSize;

listItem=newObject[maxSize];

}

//顺序表基本操作（略）

}

2.2.2顺序表基本操作

2.2.2顺序表基本操作初始化创建初始化创建是为顺序表分配一段预定义大小的连续空间，用listItem记录首地址。初始化元素个数不超过最大分配空间即可，如算法2.1和图2.2所示。2.2.2顺序表基本操作

2.2.2顺序表基本操作

2.2.2顺序表基本操作查找顺序表查找元素是指在顺序表中查找与指定关键字key是否有相等的元素。如图2.3所示查找与关键字相同的元素8，若找到则返回其位置，否则返回最后的-1。倘若查找的是3则返回1，查找的是5则返回3。那么如何实现的呢？我们来看看算法2.2。2.2.2顺序表基本操作【算法2.2】在顺序表中查找首次出现的元素8，若找到则返回其位置；若没找到则返回-1。思路:（1）从第1个元素开始顺序查找，依次比较每一个元素值。（2）若相等则找到，可返回元素位置。

（3）若遍历完顺序表都没找到，则查找失败，可返回-1。代码见算法2_22.2.2顺序表基本操作

2.2.2顺序表基本操作【算法2.3】在顺序表的i=2处插入元素7。思路：（1）如果顺序表已满，抛出异常；

（2）如果插入的位置超出[0,curLen]范围，则抛出异常；

（3）如果i=curLen，则直接插入，否则执行（4）；

（4）从顺序表最后1个元素开始依次往后移动，直到位置i上的元素移动；

（5）将元素elem插入到位置i处；

（6）将curLen加1，插入成功返回ture，否则返回false。代码见算法2_32.2.2顺序表基本操作删除顺序表删除元素是指在顺序表中若找到要删除的元素elem则将其删除，若没找到则删除失败。如图2.5所示删除元素7前后的对比。若要删除元素7，又如何实现的呢？我们来看看算法2.4。2.2.2顺序表基本操作

2.3单链表由于链表的存储在物理上元素之间可以连续也可以不连续，体现元素之间的关联就需要附加1个指针域next，除了数据与data外。只有1个指针域指向其后继的链表叫单链表，如图2.6所示，其中指针域next也是单链表节点类型，这种结构称为递归结构定义；符号“∧”表示空。2.3.1单链表存储结构单链表存储结构采用链式存储方式，逻辑上相邻的元素物理存储位置不一定相邻，元素存储是离散的。由这种结构特点可知，单链表不能随机存取，查找效率低，但删除和插入元素时，不需要移动大量元素，效率高。举例：教室里的学生并没有按照学号顺序依次坐，中间空位也多，不必连续，这叫入座自由！老师考勤，让学生从小到大自报学号后2位，你看看“遍地开花”！为什么乱坐现象能够顺序点名？因为每个学生的学号（加1）可以看作指向下一个学生的指针，上一个学生找到了那么下一个学生也就找到了，与他们之间所坐的物理位置无关！在这个例子中，教室里的学生可以看作构成单链表的节点元素，所有学生构成单链表。2.3.2单链表基本操作单链表节点类Node描述单链表类LinkList描述2.3.2单链表基本操作1.初始化单链表初始化操作是指创建一个空表。空表往往只有头节点head，不存储数据，头节点的指针域为空，如下图所示。头节点的作用：（1）找到相应的单链表，好比穿衣服抓到衣领；（2）方便一些从头节点开始的操作如遍历查找。2.3.2单链表基本操作【算法2.5】单链表初始化。publicvoidalgorithm2_5(Objectelem)throwsException{

LinkList=newLinkList(); //创建单链表

System.out.println(linkList.head.data);//验证单链表头节点数据域空

System.out.println(linkList.head.next);//验证单链表头节点指针域空

}

算法2.5，用单链表类的不带参数的构造方法创建了只有头节点的单链表空表，且头节点不包含任何内容。2.3.2单链表基本操作2.插入单链表插入操作是指将节点s插入节点p的后面。如图2.8所示的插入过程又如何实现的呢？我们来看看算法2.6。2.3.2单链表基本操作【算法2.6】在带头节点的单链表中将节点s插入到节点p之后。思路：（1）从单链表头节点开始遍历，寻找节点p；（2）若遍历完之后没找到，则返回false，否则执行（3）；（3）若节点p是尾节点，则将p的next指向s，s的next置为null，返回true；（4）若节点p不是尾节点，则将节点s的next指向节点p原来的后继；将节点p的next指向节点s，返回true。代码见算法2_6（）2.3.2单链表基本操作【思考与练习2.1】在图2.8中，2个新增的指针（见①②），赋值的先后顺序可否改变，即s.next=p.next;与p.next=s;这2条语句可否交换顺序，为什么？答：不能！如果交换顺序，p.next=s;没问题，节点p指向了插入后的节点s，但s.next=p.next;就是s指向自己，因为此时的p指向的是s，而非原来的后继。所以只能按照顺序进行操作。2.3.2单链表基本操作3.整表创建单链表整表创建操作是指一次性创建并初始化单链表一些元素，它可由尾插法和头插法进行整表创建。顾名思义，尾插法是将插入元素始终在单链表的尾部插入；头插法是将插入元素始终在单链表的头部插入。举例：请1到5学号的同学依次上讲台来，从左到右的面向方向：1号上来，2号在1号后面，3号在2号后面，依次类推，最后排列的顺序与上来的顺序一样；再来一遍，上来的顺序不变，1号上来，2号在1号的前面，3号在2号的前面，依次类推，最后排列的顺序与上来的顺序相反。通过这个例子，显然我们得知：尾插法的结果是顺序/正序，头插法的结果是逆序/倒序。2.3.2单链表基本操作如图2.9所示，每产生1个新节点s，始终将其插入单链表的尾部或头部（头节点head之后）。那么又如何实现尾插法和头插法整体建表的呢？我们来看看算法2.7和算法2.8。2.3.2单链表基本操作【算法2.7】用尾插法创建单链表。思路：（1）移动指针t指向头节点head；（2）在t的后面插入单链表新节点s；（3）t移动到s；（4）重复执行（2）、（3），直到数组a遍历完；（5）置t的指针域为null。代码见算法2_7()2.3.2单链表基本操作【算法2.8】用头插法创建单链表。思路：（1）遍历数组a，每次产生1个单链表新节点s；（2）在单链表的头节点head之后插入s；（3）重复执行（1）、（2），直到数组a遍历完。代码见算法2_8()（备注：游戏视频演示细节有问题，请同学指出）2.3.2单链表基本操作【思考与练习2.2】可否利用算法2.6实现单链表的尾插法和头插法？答：可以的。在尾插法中，始终将节点p置为尾节点，遍历数组a时调用算法2.6进行插入；在头插法中，始终将节点p置为头节点head，遍历数组a时调用算法2.6进行插入。如thinkpad2_2算法。2.3.2单链表基本操作4.取值单链表取值操作是指取到第i个元素的值，将其值返回；若没取到则返回-1。举例：我要找到教室里学号为18的学生，我可以让学生从1号开始报号，直到报到18号。倘若要找学号为88的学生，报完了也找不到！因为超出取值范围了。2.3.2单链表基本操作如图2.10所示，要取到单链表中第i个元素的值ai，又如何实现的呢？我们来看看算法2.9。2.3.2单链表基本操作【算法2.9】单链表中取第i个元素的值。思路：（1）节点p设为从首节点开始遍历单链表的指针，计数变量j初值为1；（2）每遍历到1个节点时，判断j是否等于i：若相当则返回p指向节点的值；若不等则p继续移动，j加1；（3）重复（2），直到找到而返回，或遍历完而没找到返回-1。代码见算法2_9()2.3.2单链表基本操作5.查找单链表查找操作是指在单链表中查找与指定关键字key是否相同的元素。单链表不能像顺序表那样随机存取，所以查找过程是从头节点或首节点开始依次遍历比较的过程。如图2.11所示，查找单链表中是否有key=“FanFan”的节点，若找到第1个这样的节点则查找成功返回true；若没找到则返回false。又如何实现的呢？我们来看看算法2.10。2.3.2单链表基本操作【算法2.10】单链表中查找key=“FanFan”的第1个节点。思路：（1）节点p设为从首节点开始遍历单链表的指针；（2）取出p的数据域值，与指定关键字key比较：若相等则找到，返回true；若不相等则继续找下一个元素，执行（3）；（3）重复（2），直到找到而返回true，或遍历完而没找到返回false。代码见算法2_10()2.3.2单链表基本操作6.删除单链表删除操作是指将单链表中位置为i的节点从单链表中删除。单链表删除操作有点像“跳过”要删除的节点，好比a、b、c三人手拉手，ac牵手则b出去了，如图2.12所示，要删除i位置处的b节点，只需（i-1）位置处的a节点的指针域指向节点b的后继c即可。那么代码又如何实现的呢？我们来看看算法2.11。2.3.2单链表基本操作【算法2.11】单链表中删除位置为i的b节点。思路：（1）设置1个移动指针p，初始指向头节点head；（2）将p移动到（i-1）位置处；（3）将p指向的节点的指针域修改为该节点的后继的后继。代码见算法2_11()2.4双链表双链表双链表有2个指针域，顾名思义。比单链表在节点结构上多了1个指针域prior：指向前驱的指针域，它解决了单链表只能向后操作的问题。双链表的头节点也有2个指针域，如图2.13所示带头节点的双链表逻辑结构。2.4.1双链表存储结构双链表存储结构类同单链表，也是采用链式存储方式，也有与单链表共同的特性如增删节点高效。由于有2个指针域，所以双链表既可以利用next指针域向后操作，也可以利用prior指针域向前操作。这一特性又可以改变一些单链表算法思路。2.4.1双链表存储结构举例：请5个同学上讲台，从左到右1到5编号。（1）单链表游戏表演：5个同学向左转，双手搭在下一个同学肩膀上（最后1个同学除外）；从1号开始，双手使劲摇下2号肩膀，表示2号存活，2号再使劲去摇3号肩膀，3号存活，依此类推。其实我们要出局3号，2号一不小心摇了他，他又摇了4号，4号没有对3号的生死权，游戏只得从头再来。（2）双链表游戏表演：5个同学面向教室手拉手，1号摇摇左手，2号存活，2号摇摇左手3号存活，3号摇摇左手，4号存活；4号或者此时的观众想起来了，3号要出局！莫慌，4号懒得摇摇右手了，直接去牵2号的左手，3号出局！倘若到5号才想起3号要出局，5号摇摇右手，4号冰雪聪明：牵2号左手！2.4.2双链表基本操作双链表节点类DuLNode描述双链表类DuLinkList描述2.4.2双链表基本操作1.初始化双链表的初始化操作是指构建1个空表，建头节点而不存储数据，头节点的2个指针域皆为空，如图2.14所示。

2.4.2双链表基本操作【算法2.12】双链表初始化。publicvoidalgorithm2_12(Objectelem)throwsException{

DuLinkListduLinkList=newDuLinkList();//创建双链表

System.out.println(duLinkList.head.prior);//验证头节点前驱域为空

System.out.println(duLinkList.head.data);//验证头节点数据域为空

System.out.println(duLinkList.head.next);//验证头节点后继域为空

}

算法2.12，用双链表类的不带参数的构造方法创建了只有头节点的双链表空表，且头节点不包含任何内容。2.4.2双链表基本操作2.插入双链表插入操作同单链表插入操作，不同的是在插入过程中单链表改变的是2个指针，双链表改变的是4个指针，除非是尾部插入和不带头节点的头部插入。不妨仍将节点s插入节点p的后面，如图2.15所示的插入过程又如何实现的呢？我们来看看算法2.13。2.4.2双链表基本操作【算法2.13】在带头节点的双链表中将节点s插入到节点p之后。思路：（1）从双链表头节点开始遍历，寻找节点p；（2）若遍历完之后没找到，则返回false，否则执行（3）；（3）若节点p是尾节点，则将p的next指向s；将s的prior指向p；将s的next置为null，返回true；（4）若节点p不是尾节点，则将节点s的next指向节点p原来的后继；将节点p原来的后继的prior指向s；将节点s的prior指向p；将节点p的next指向s；返回true。代码见算法2.132.4.2双链表基本操作【思考与练习2.3】在双链表的插入操作中，若节点p是节点s的后继，能否实现插入，若不能为什么；若可以又如何实现？答：可以！如图2.16所示，从左到右4个指针分别执行①②④③，也可以是①③④②。如下面的算法：publicvoidthinkPad2_3()throwsException{

//双链表，由后继或者在当前节点处插入操作的主要代码：

/*

s.prior=p.prior;

p.prior.next=s;

s.next=p;

p.prior=s;

*/

}

在双链表的插入操作中，可以随便改变4个指针更新的顺序吗？答：不能！同单链表，见【思考与练习2.1】解答。2.4.2双链表基本操作3.整表创建双链表整表创建操作同单链表整表创建操作，也可由尾插法和头插法进行整表创建。不同的是，它更新的指针更多。那么又如何实现的呢？我们来看看算法2.14和2.15。【算法2.14】用尾插法创建双链表。思路：（1）移动指针t指向头节点head；（2）在t的后面插入双链表新节点s；（3）t移动到s；（4）重复执行（2）、（3），直到数组a遍历完；（5）置t的指针域为null。代码见算法2.142.4.2双链表基本操作【算法2.15】用头插法创建双链表。思路：（1）遍历数组a，每次产生1个双链表新节点s；（2）在双链表的头节点head之后插入s；（3）重复执行（1）、（2），直到数组a遍历完。代码见算法2.15同单链表整表创建一样，双链表整表创建也可以多次调用其“插入”函数高级编程实现。2.4.2双链表基本操作4.取值双链表取值操作同单链表取值操作，不同的是双链表取值可以从前开始，也可以从后开始取值，由于双链表双向操作特点。【算法2.16】双链表中取第i个元素的值。思路：（1）节点p设为从首节点开始遍历双链表的指针，计数变量j初值为1；（2）每遍历到1个节点时，判断j是否等于i：若相当则返回p指向节点的值；若不等则p继续移动，j加1；（3）重复（2），直到找到而返回，或遍历完而没找到返回-1。代码见算法2.162.4.2双链表基本操作【思考与练习2.4】在双链表的取值操作中，如果当前节点p为尾节点，取值节点的位置i靠近尾节点，显然这种情况从“尾”开始比从“头”开始好！那么如何实现从尾节点开始逆向遍历取到节点值呢？答：如下面的算法：publicObjectthinkPad2_4(inti)throwsException{

DuLinkListduLinkList=newDuLinkList();//创建空双链表

//假设双链表中初始化了一些元素（略）

intlength=0;//双链表长度

DuLNodep=duLinkList.head;//p为移动指针，初始指向头节点

while(p.next!=null){

length++;

p=p.next;

}//置p为尾节点，并计算出双链表长度

intj=length;

while(p!=null){//未遍历完单链表

if(j==i)//找到

returnp.data;

else{//还没找到

p=p.prior;//继续往前找

j--;//计数变量减1，逆向遍历

}

}

return-1;//没找到返回-1

}

2.4.2双链表基本操作留意：遍历链表时注意循环条件，如p.next！=null和p！=null两个条件，在最后遍历完链表后，当前指针p位置是不同的，前者最后指向尾节点，后者最后为null（指向尾节点之后）。2.4.2双链表基本操作5.查找双链表查找操作同单链表查找操作，不同的是双链表可以双向查找。如图2.17所示，查找双链表中是否有key=“Vivian”的元素，假设这个元素若存在则是唯一的，且在中间位置偏左一点；若找到则返回true，否则返回false。那么又如何实现的呢？我们来看看算法2.17。2.4.2双链表基本操作【算法2.17】双链表中查找中间位置偏左一点且key=“Vivian”的节点。思路：（1）准备1个带节点编号的双链表，并初始化一些数据；（2）假设当前指针p已经走到双链表的中间位置；（3）取出p的数据域值，与指定关键字key比较：若相等则找到，返回true；若不相等则向前移动1个位置，执行（4）；（4）重复（3），直到找到而返回true。代码见算法2.172.4.2双链表基本操作6.删除双链表删除操作同单链表同单链表删除操作，不同的是双链表删除操作可以从被删除节点的前驱进行，也可以从其后继进行。如图2.18所示通过被删除节点的前驱或后继p进行删除，那么代码又如何实现的呢？我们来看看算法2.18。2.4.2双链表基本操作【算法2.18】双链表中删除位置为i的b节点。思路：（1）设置1个移动指针p，初始指向头节点head；（2）将p移动到（i-1）或（i+1）位置处；（3）p为被删节点的前驱时：a.p后继的后继的prior指向p；b.p的next指向后继的后继。p为被删节点的后继时：a.p的前驱的前驱的next指向p；b.p的prior指向前驱的前驱。代码见算法2.182.4.2双链表基本操作【思考与练习2.5】在图2.18中，①和②的操作顺序是否可以交换，为什么？答：可以，因为指针域变化不受影响。不过建议先操作离当前节点p较远的操作，即遵循“远端优先操作”原则。如下面的算法：publicvoidthinkPad2_5()throwsException{

//p为被删节点前驱，①和②交换：

/*

p.next=p.next.next;//p的next指向后继的后继

p.next.next.prior=p;//p后继的后继的prior指向p

*/

//p为被删节点后继，①和②交换：

/*

p.prior=p.prior.prior;//p的prior指向前驱的前驱

p.prior.prior.next=p;//p的前驱的前驱的next指向p

*/

}2.5循环链表循环链表是在之前所讲的单链表、双链表的基础上改进而得的链表。由单链表改进得到循环单链表，由双链表改进得到循环双链表。它们的改进有个共同特点：首尾相连，形成环。为了更好区分这4种链表，见下面的例子。举例：请5个同学自告奋勇上台。第1个动作：站成一排，除最后1个同学外，其他同学的左手搭在左旁同学肩上。第2个动作：站成一排，手拉手吧！第3个动作：围成圈，左手搭在左旁同学肩上。第4个动作：围成圈，手拉手。通过这个例子我们可以很形象而生动地认识到，4个动作分别说的就是单链表、双链表、循环单链表、循环双链表，大概括啊！2.5循环链表循环单链表和循环双链表的存储结构与单链表和双链表的存储结构相同。2.5.1循环单链表循环单链表的尾节点的next不再为空，是指向头节点，这样使整个单链表形成环；若只有头节点的空表，头节点的next也指向头节点自身。如图2.19所示。2.5.1循环单链表循环单链表的节点类与单链表的节点类相同，链表类和基本操作相似，主要不同在于：循环单链表需通过head.next=head;语句置空表；判断尾节点时不再是单链表的p.next==null;而是p.next==head;语句。2.5.1循环单链表循环单链表类CLinkList的描述2.5.2循环双链表循环双链表的尾节点的next也指向头节点，头节点的prior不再为空，是指向尾节点，这样使整个双链表形成环；若只有头节点的空表，头节点的next和prior皆指向头节点自身。如图2.20所示。2.5.2循环双链表循环双链表与双链表的节点类相同，链表类和基本操作相似，主要不同在于：循环双链表需通过head.next=head;和head.prior=head;语句置空表；判断尾节点时不再是双链表的p.next==null;而是p.next==head;语句。，2.5.2循环双链表循环双链表类CDuLinkList的描述2.6线性表应用2.6.1顺序表应用【例2.1】将含有n个元素的有序顺序表S中的所有元素逆置。如S=（1,2,3,4,5），逆置后S=（5,4,3,2,1），并分析算法的时空复杂度。思路：（1）双指针设置：头指针i和尾指针j；（2）交换它们所指向的元素后；（3）i++且j--，若i<j则执行（2），否则结束。代码见例2.1算法2.6.1顺序表应用【进一步思考】请写出实现例2.1算法的其他思路。答：（1）逆序遍历思路（2）入栈和出栈思路。等等。2.6.1顺序表应用【例2.2】将含有n个整数元素的顺序表S中相邻重复元素删掉，只保留1个。如S=（1,3,3,4,1），删除后S=（1,3,4,1），并分析算法的时空复杂度。思路：（1）新建一个顺序表，将原顺序表第1个元素插入；（2）从原顺序表第2个元素开始遍历，比较新顺序表中尾元素：若相等则继续遍历，若不相等则将其插入到新表中；（3）直到原顺序表遍历完成。代码见例2.2算法2.6.1顺序表应用【进一步思考】请写出实现例2.2算法的其他思路。答：第1次遍历找到相邻相同的元素，第2次遍历相邻不相同的元素与之合并。等等。2.6.2单链表应用【例2.3】将含有n个元素的有序单链表L中的所有元素逆置。如L=（1,2,3,4,5），逆置后L=（5,4,3,2,1），并分析算法的时空复杂度。思路：（1）p指向单链表首节点；（2）置L为空单链表；（3）遍历L，将p插入到L的头部。代码见例2.3算法2.6.2单链表应用【进一步思考】请写出实现例2.3算法的其他思路。答：（1）头尾双指针交换，同例2.1算法思路(双链表而言)（2）顺序遍历入栈，再出栈尾插法成单链表思路。等等。2.6.2单链表应用【例2.4】将2个递增有序整数单链表A和B合并为C，C也是递增有序单链表，并分析算法的时空复杂度。思路：（1）采用二路归并和尾插法思想，在同时遍历A和B时，比较元素大小；（2）将较小元素尾插法到C；（3）重复执行（1）和（2），直到A或B遍历完；（4）若A或B还有没遍历完的元素，将其链接到C的后面，完毕。代码见例2.4算法2.6.2单链表应用【进一步思考】请写出实现例2.4算法的其他思路。答：小根堆思路：分别遍历A和B，完成建小根堆；再输出小根堆建单链表。等等。2.6.3双链表应用

2.6.3双链表应用【进一步思考】请写出实现例2.5算法的其他思路，可否得出找线性表中间节点的推论。答：正序或逆序遍历加计数器思路。等等。推论：通过例2.5算法，我们不难知道可以利用快慢指针找到线性表的中间节点，如快慢指针同时从初始位置移动，慢指针移动1步，快指针移动2步，当快指针后继的后继为空时，慢指针停留的位置便是中间节点位置。2.6.4循环链表应用故事：据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Joseph和他的朋友并不想遵从，Joseph要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。2.6.4循环链表应用

2.6.4循环链表应用【进一步思考】请写出实现例2.6算法的其他思路。答：（1）带模运算的一维数组思路（2）循环队列思路。等等。2.6.4循环链表应用【例2.7】用循环双链表判断所有元素是否对称。例如循环双链表CDL=(1,2,3,2,1)是对称的，返回true，否则返回false。思路：（1）新建循环双链表并初始化数据；（2）p指向首节点，q指向尾节点；（3）比较p和q指向元素的数据，若不等则返回false，否则执行（4）；（4）p往后移1位，q往前移1位，执行（3），直到p和q相遇或者p是q的前驱；（5）返回true。代码见例2.7算法2.6.4循环链表应用【进一步思考】请写出实现例2.7算法的其他思路。答：（1）入栈一半出栈比较思路（2）逆序之后与原序列比较是否一样的思路。等等。2.7线性表学习总结线性表的逻辑结构是1对1的关系。在链表中，head表示头节点，head.next表示首节点（第1个元素节点）。链表赋值等式两边的含义：p.next=q.next;左边表示指针域，右边表示节点。链表的插入和删除操作中，修改指针原则：先修改无指针标记的那一端。即“远端优先修改”原则。在单链表的插入和删除操作中，需找到前驱节点。在双链表的插入和删除操作中，可以通过被操作节点的前驱或后继节点完成，节点可以自我删除。循环双链表最大的优点是可以由头节点直接找到尾节点，而循环单链表不行。建立链表2种方式：头插法逆序建表和尾插法正序建表。链表的逆置、归并操作属于就地操作，不需要额外空间。快慢指针的应用较广泛，如求中间节点、倒数/正数第k个节点、判断链表是否有环、公共部分的起点等。第3章栈和队列本章讲解栈和队列。要求理解栈和队列概念；掌握栈和队列的存储结构；掌握栈和队列的基本操作；灵活应用栈和队列。重庆的麻辣烫，成都的串串香。串串香吃起美味，背后的付出却艰辛，要把菜品一个一个串到一根竹签上，吃货才能一个一个吃出来。一把一把接着下锅，先下锅的先吃到。串起来是进栈，吃出去是出栈；下锅是进队列，出锅是出队列。提纲3.1栈基本概念3.2顺序栈3.3链栈3.4栈应用3.5队列基本概念3.6顺序队列3.7链队列3.8循环队列和优先队列3.9队列应用3.10栈和队列学习总结3.1栈基本概念栈是特殊的线性表，它只允许在线性表的一端操作。如图3.1所示，装乒乓球、网球、羽毛球的盒子皆属于栈类型。能够操作的这一端叫栈顶，不能操作的另一端叫栈底。显然，栈有“先进后出”或“后进先出”的特点。3.1栈基本概念栈的抽象数据接口IStack3.2顺序栈以顺序存储结构进行存储的栈称为顺序栈。3.2.1顺序栈存储结构顺序栈存储结构采用顺序存储方式，同顺序表存储结构，故顺序栈也可以用一维数组存储如图3.2所示，栈顶设置1个指针top指向栈顶元素（有的参考书将top指向栈顶元素的下1个位置，不影响理解）。3.2.1顺序栈存储结构举例：1个经验丰富的探险队队长带领若干队员进入1个狭长的溶洞，要求后面队员手拉手紧跟着，不能单独走以免走散。队长最先进洞，一路做返回记号，出洞却最后出来。在这个例子中，溶洞看作栈，队长和队员看作元素，这是个顺序栈。3.2.2顺序栈基本操作顺序栈类SqStack3.2.2顺序栈基本操作长度为5的顺序栈的基本操作如图3.3所示。3.2.2顺序栈基本操作1.栈判空和栈判满顺序栈栈判空和栈判满操作就是判断栈是否为空和是否已满。出栈时要判断栈是否为空，入栈时要判断栈是否为满，否则操作无效，增加开销。那么又如何实现的呢？我们来看看算法3.1。3.2.2顺序栈基本操作【算法3.1】判断顺序栈是否为空和是否已满。思路:由图3.3的（1）和（3）易知，根据top的值可以判断栈空和栈满。代码见算法3.13.2.2顺序栈基本操作2.入栈顺序栈入栈操作是指向栈中添加元素，在栈没有满的情况下。那么又如何实现的呢？我们来看看算法3.2。3.2.2顺序栈基本操作【算法3.2】顺序栈入栈。思路:由图3.3的（2）易知，在栈未满的情况下先将top加1，再将入栈元素赋值给top处元素。代码见算法3.23.2.2顺序栈基本操作3.出栈顺序栈出栈操作是指栈顶元素出栈，在栈没有空的情况下。那么又如何实现的呢？我们来看看算法3.3。3.2.2顺序栈基本操作【算法3.3】顺序栈出栈。思路:由图3.3的（4）易知，先将出栈元素赋值给返回变量，再top减1。代码见算法3.33.2.2顺序栈基本操作4.取栈顶元素顺序栈取栈顶元素操作是指访问栈顶元素但栈顶元素不出栈，在栈没有空的情况下。那么又如何实现的呢？我们来看看算法3.4。3.2.2顺序栈基本操作【算法3.4】顺序栈取栈顶元素。思路:

由图3.3的易知，取栈顶元素只需访问top指针指向的元素，将其输出。代码见算法3.43.3链栈以链式存储结构进行存储的栈称为链栈。3.3.1链栈存储结构链栈存储结构采用链式存储方式，同链表存储结构。如图3.4所示，用带头节点的单链表表示链栈，链栈的栈顶指针top指向单链表的首节点，单链表的尾节点为栈底节点。3.3.2链栈基本操作链栈节点类LinkNode描述链栈类LinkStack描述3.3.2链栈基本操作1.栈判空链栈栈判空同顺序栈栈判空，而链栈同链表一样不存在溢出，除非内存耗尽。因此链栈出栈时要判断栈是否为空而入栈时不需要判断是否为满。3.3.2链栈基本操作【算法3.5】判断链栈是否为空。思路:由图3.4易知，链栈为空同链表为空，此时只有头节点，top指针也指向头节点。代码见算法3.53.3.2链栈基本操作2.入栈链栈入栈操作类似单链表插入节点操作，但只能在头节点之后即栈顶处插入。3.3.2链栈基本操作【算法3.6】链栈入栈。思路:由图3.4易知，插入的节点插入到头节点之后；top指针指向插入节点。代码见算法3.63.3.2链栈基本操作3.出栈链栈出栈操作类似单链表删除节点操作，在栈没有空的情况下，但只能删除首节点即栈顶节点。3.3.2链栈基本操作【算法3.7】链栈出栈。思路:由图3.4易知，若链栈非空则删除首节点；若删除后链栈为空则将top指针指向头节点，否则将其指向下一个节点；返回删除节点的data值。若链栈为空则返回空。代码见算法3.73.3.2链栈基本操作4.取栈顶元素链栈取栈顶元素操作同顺序栈取栈顶元素操作，在栈没有空的情况下。那么又如何实现的呢？我们来看看算法3.8。3.3.2链栈基本操作【算法3.8】链栈取栈顶元素。思路:若链栈不为空则返top指针指向的节点的data值，否则返回空。代码见算法3.83.4栈应用

3.4栈应用【进一步思考】若1个十进制数有小数，小数部分转换为二进制还需用到栈吗？答：不需要，因为小数部分产生的二进制数与产生顺序相同，产生1个输出1个即可。3.4栈应用【例3.2】利用栈进行括号匹配检查，对2个测试用例"{{}}()(hello){({world}{})}"和"{{}}()(hello){({world}(})}"进行测试，并分析算法的时空复杂度。思路：（1）从头遍历字符串，每个字符处理如下；（2）若遇左括号将其入栈；（3）若遇右括号：栈不为空时将其与栈顶元素比较：匹配则出栈，不匹配则返回false，栈为空时返回false；（4）字符指针移到下1位，重复（2）、（3），直到遍历完字符串；（5）若栈为空则返回true，否则返回false。代码见应用3.23.4栈应用【进一步思考】用递归算法可否实现括号匹配检查，为什么？答：可以，因为该问题可以把大规模问题分解为若干个相似小规模问题。3.4栈应用

3.4栈应用【进一步思考】汉诺塔问题可以用递归算法实现吗？答：可以，见后面递归章节内容。3.5队列基本概念队列也是特殊的线性表，它限制在一端插入，另一端删除。如图3.6所示，现实中的队列例子很多如排队购物、打饭、上公交、做核酸等皆属于队列类型。插入的那端叫队尾，删除的那端叫队头。显然，队列有“先进先出”或“后进后出”的特点。3.5队列基本概念队列的抽象数据接口IQueue描述3.6顺序队列以顺序存储结构进行存储的队列称为顺序队列。3.6.1顺序队列存储结构顺序队列存储结构采用顺序存储方式，同顺序表存储结构，故顺序队列也可以用一维数组存储。如图3.7所示，队头设置1个指针front指向队首元素，队尾设置1个指针rear指向队尾元素的下1个元素（有的参考书将front和rear指向向前的1个位置，不影响理解）。3.6.1顺序队列存储结构举例：2个老师带若干个小朋友出去旅游，无论走到哪里，为了保证安全，小朋友们排成队列，2个老师一前一后监管。在这个例子中，老师和小朋友组成的队列类似顺序队列，2个老师分别看作队头指针和队尾指针。3.6.2顺序队列基本操作顺序队列类SqQueue的描述3.6.2顺序队列基本操作长度为5的顺序队列的基本操作如图3.8所示。3.6.2顺序队列基本操作1.队列判空和队列判满顺序队列判空和判满操作就是判断队列是否为空和是否已满。出队时要判断队列是否为空，入队时要判断队列是否为满，否则操作无效，增加开销。3.6.2顺序队列基本操作【算法3.9】判断顺序队列是否为空和是否已满。思路:由图3.8的（1）和（4）易知，根据front和rear关系值可以判断队列空和队列满。代码见算法3.93.6.2顺序队列基本操作2.入队顺序队列入队操作是指向队列中插入元素，在队列没有满的情况下。3.6.2顺序队列基本操作【算法3.10】顺序队列入队。思路:由图3.8的（2）、（3）、（4）易知，在队列未满情况下入队时front指针不动，先赋值到rear处，再将rear指针向后移动1位。代码见算法3.103.6.2顺序队列基本操作3.出队顺序队列出队操作是指队头元素出队列，在队列没有空的情况下。3.6.2顺序队列基本操作【算法3.11】顺序队列出队。思路:由图3.8的（5）易知，在队列不空的情况下出队时front指针处元素保存，front指针向后移动1位，返回保存元素即出队元素。代码见算法3.113.6.2顺序队列基本操作4.取队头元素和取队尾元素顺序队列取队头元素操作是指访问队列的首元素，取队尾元素操作是指访问队列的尾元素。3.6.2顺序队列基本操作【算法3.12】顺序队列取队头元素和取队尾元素。思路:由图3.8易知，取队头元素可以访问front指针指向的元素；取队尾元素可以访问rear-1处的元素。代码见算法3.123.7链队列以链式存储结构进行存储的队列称为链队列。3.7.1链队列存储结构链队列存储结构采用链式存储方式，同链表存储结构。如图3.9所示，front指针指向队头节点，rear指针指向队尾节点。3.7.2链队列基本操作链队列类LinkQueue的描述3.7.2链队列基本操作长度为3的链队列的基本操作如图3.10所示。3.7.2链队列基本操作队列判空链队列判空操作就是判断队列是否为空。出队时要判断链队列是否为空，否则操作无效，增加开销。3.7.2