第2章 线性表电子课件

第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）将