数据结构教程（C++语言描述）（第3版微课视频版）课件 第2章 线性表

第2章线性表2.1线性表的定义2.3线性表的链式存储结构2.2线性表的顺序存储结构2.4顺序表和链表的比较CONTENTS提纲2.5线性表的应用1/482.6STL中的线性表2.1线性表的定义2.1.1什么是线性表线性表是具有相同特性的数据元素的一个有限序列。所有数据元素类型相同。线性表是有限个数据元素构成的。线性表中数据元素与位置相关，即每个数据元素有唯一的序号。2/48线性表的逻辑结构表示（a0，a1，…，ai，ai+1，…，an-1）用图形表示的逻辑结构：a0a1aiai+1an-1……线性表中每个元素ai的唯一位置通过序号或者索引i表示，为了算法设计方便，将逻辑序号和存储序号统一，均假设从0开始，这样含n个元素的线性表的元素序号i满足0≤i≤n-1。说明3/482.1.2线性表的抽象数据类型描述4/48ADTList{

数据对象：

D={ai|0≤i≤n-1，n≥0}

数据关系：r={<ai，ai+1>|ai，ai+1∈D，i=0，…，n-2}

基本运算：CreateList(a)：由整数数组a中的全部元素建立线性表的相应存储结构。Add(e)：将元素e添加到线性表末尾。getlength()：求线性表的长度。GetElem(inti)：求线性表中序号为i的元素。SetElem(inti，Te)：设置线性表中序号i的元素值为e。GetNo(Te)：求线性表中第一个值为e的元素的序号。Insert(inti，Te)：在线性表中插入数据元素e作为第i个元素。Delete(inti)：在线性表中删除第i个数据元素。DispList()：输出线性表的所有元素。}2.2线性表的顺序存储结构2.2.1线性表的顺序存储结构—顺序表长度为n的线性表存放在顺序表中a0a1…ai-1ai…an-1…data数组数组下标01…i-1i…n-1capacity-15/48data数组存放线性表元素data数组的容量（存放最多的元素个数）为capacity。线性表中实际数据元素个数lengthconstintinitcap=5; //顺序表的初始容量（5）template<typenameT>classSqList{

//顺序表类模板public:T*data; //存放顺序表元素空间的指针intcapacity; //顺序表的容量intlength; //存放顺序表的长度//线性表的基本运算算法};6/482.2.2线性表基本运算算法在顺序表中的实现

在动态分配顺序表的空间时，初始容量设置为initcapacity，当添加或者插入元素可能需要扩大容量，在删除元素时可能需要减少容量。voidrecap(intnewcap){ //改变顺序表的容量为newcapif(newcap<=0)return;T*olddata=data;data=newT[newcap]; //分配新空间capacity=newcap; //更新容量for(inti=0;i<length;i++) //元素复制data[i]=olddata[i];delete[]olddata; //释放原空间}7/481.整体建立顺序表voidCreateList(Ta[],intn) { //由数组a中元素整体建立顺序表for(inti=0;i<n;i++){if(length==capacity) //容量不够时 recap(2*length); //扩大容量data[length]=a[i];length++; //添加后元素个数增加1}}

由含若干个元素的数组a的全部元素整体创建顺序表，即依次将a中的元素添加到data数组的末尾，当出现上溢出时按实际元素个数length的两倍扩大容量。8/482.顺序表基本运算算法（1）顺序表的初始化和销毁SqList(){

//构造函数data=newT[initcap]; //为data分配初始容量大小的空间capacity=initcap; //初始化容量length=0; //初始时置length为0}构造函数9/48SqList(constSqList<T>&s){ //初始化复制构造函数capacity=s.capacity; //复制容量length=s.length; //复制长度data=newT[capacity]; //为当前顺序表分配空间for(inti=0;i<length;i++) //元素复制data[i]=s.data[i];}初始化复制构造函数（拷贝构造函数）10/48~SqList(){

//析构函数delete[]data; //释放data指向的空间}析构函数11/48（2）将元素e添加的线性表末尾Add(e)voidAdd(Te){ //在线性表的末尾添加一个元素eif(length==capacity) //顺序表空间满时倍增容量

recap(2*length);data[length]=e; //添加元素elength++; //长度增1}时间复杂度是多少？12/48intGetlength(){

//求顺序表的长度returnlength;}（3）求线性表的长度getlength()13/48boolGetElem(inti,T&e){ //求序号i的元素值if(i<0||i>=length)returnfalse; //参数错误时返回falsee=data[i]; //取元素值returntrue; //成功找到元素时返回true}（4）求线性表中序号为i的元素GetElem(i,&e)14/48boolSetElem(inti,Te){ //设置序号i的元素值if(i<0||i>=length) //参数错误时返回falsereturnfalse;data[i]=e;returntrue;}（5）设置线性表中序号为i的元素SetElem(i，e)15/48intGetNo(Te) { //查找第一个为e的元素的序号inti=0;while(i<length&&data[i]!=e)i++; //查找元素eif(i>=length) //未找到时返回-1return-1;elsereturni; //找到后返回其序号}（6）求线性表中第一个值为e的元素的逻辑序号GetNo(e)16/48boolInsert(inti,Te){ //在线性表中序号i位置插入元素eif(i<0||i>length) //参数i错误返回falsereturnfalse;if(length==capacity) //满时倍增容量

recap(2*length);for(intj=length;j>i;j--) //data[i]及后元素后移一个位置data[j]=data[j-1];data[i]=e; //插入元素elength++; //长度增1returntrue;}（7）在线性表中插入e作为第i个元素Insert(i，e)a0a1…aiai+1…an-1…从an-1元素开始移动起17/48

主要时间花在元素移动上。有效插入位置i的取值是0～n，共有n+1个位置可以插入元素：当i=0时，移动次数为n，达到最大值。当i=n时，移动次数为0，达到最小值。其他情况，需要移动data[i..n-1]的元素，移动次数为(n-1)-i+1=n-i。a0a1…aiai+1…an-1…所需移动元素的平均次数为：插入算法的平均时间复杂度为O(n)。18/48扩容运算recap()在n次插入中仅仅调用一次，其平摊时间为O(1)，上述算法时间分析中可以忽略它。说明19/48boolDelete(inti){ //在线性表中删除序号i的元素if(i<0||i>=length) //参数i错误返回falsereturnfalse;for(intj=i;j<length-1;j++)data[j]=data[j+1]; //将data[i]之后元素前移一个位置length--; //长度减1if(capacity>initcap&&length<=capacity/4)

recap(capacity/2); //满足缩容条件则容量减半

returntrue;}（8）在线性表中删除第i个数据元素Delete(i)a0a1…aiai+1…an-1…从ai+1元素开始移动起20/48a0a1…aiai+1…an-1…

主要时间花在元素移动上。有效删除位置i的取值是0～n-1，共有n个位置可以删除元素：当i=0时，移动次数为n-1，达到最大值。当i=n-1时，移动次数为0，达到最小值。其他情况，需要移动data[i+1..n-1]的元素，移动次数为(n-1)-(i+1)+1=n-i-1。所需移动元素的平均次数为：删除算法的平均时间复杂度为O(n)。21/48voidDispList(){

//输出顺序表L中所有元素for(inti=0;i<length;i++) //遍历顺序表中各元素值cout<<data[i]<<"";cout<<endl;}（9）输出线性表所有元素DispList()22/48#include"SqList.cpp" //引用顺序表类

intmain(){inti,e;SqList<int>L;//建立类型为int的顺序表对象Lcout<<"创建整数顺序表L"<<endl;L.Insert(0,2); //插入元素2L.Insert(1,3); //插入元素3L.Insert(2,1); //插入元素1L.Insert(3,5); //插入元素5L.Insert(4,4); //插入元素4L.Insert(5,1); //插入元素1L.Add(8); //添加整数8cout<<"顺序表L:";L.DispList();cout<<"长度:"<<L.length<<"容量:" <<L.capacity<<endl;i=3;L.GetElem(i,e);cout<<"序号为"<<i<<"的元素:"<<e<<endl;程序验证23/48e=1;cout<<"第一个"<<e<<"的元素序号="<< L.GetNo(e)<<"\n";i=2;cout<<"删除序号为"<<i<<"的元素\n";L.Delete(i);cout<<"顺序表L:";L.DispList();cout<<"长度:"<<L.length<<"容量:" <<L.capacity<<endl;intb[]={0,1,1,0,1};for(inti=0;i<5;i++){cout<<"删除序号为"<<b[i]<<"的元素\n";L.Delete(b[i]);cout<<"顺序表L:";L.DispList();cout<<"长度:"<<L.length<<"容量:" <<L.capacity<<endl;}cout<<"销毁顺序表L"<<endl;return0;}程序验证24/48线性表元素基本运算应用程序25/482.2.3顺序表的应用算法设计示例1.基于顺序表基本操作的算法设计

【例2.1】对于含有n个整数元素的顺序表L，设计一个算法将其中所有元素逆置。

例如L=(1，2，3，4，5)，逆置后L=(5，4，3，2，1)。并给出算法的时间复杂度和空间复杂度。26/48a0…an-1交换ai…aj…ijvoidReverse(SqList<T>&L){ //求解算法inti=0,j=L.length-1;while(i<j){swap(L.data[i],L.data[j]);//序号i和j的两个元素交换i++;j--;}}27/48

【例2.2】假设有一个整数顺序表L，设计一个算法用于删除从序号i开始的k个元素。

例如L=（1，2，3，4，5），删除i=1开始的k=2个元素后L=（1，4，5）。28/48boolDeletek(SqList<T>&L,inti,intk){ //求解算法if(i<0||k<1||i+k<1||i+k>L.length)returnfalse; //参数i和k错误返回falsefor(intj=i+k;j<L.length;j++) //删除k个元素

L.data[j-k]=L.data[j];L.length-=k; //长度减kreturntrue;}在参数正确时，直接将ai+k～an-1的所有元素依次前移k个位置。a0…aiai+1…an-1…均前移k个位置ai+k-1ai+k…删除k个元素29/482.基于整体建立顺序表的算法设计给定的顺序表L结果顺序表L1按要求插入如果两者可以共享，直接在L中操作产生结果顺序表30/48

【例2.3】对于含有n个整数元素的顺序表L，设计一个算法用于删除其中所有值为x的元素。

例如L=(1，2，1，5，1)，若x=1，删除后L=(2，5)。并给出算法的时间复杂度和空间复杂度。31/48

解法1：对于整数顺序表L，删除其中所有x元素后得到的结果顺序表可以与原L共享，所以求解问题转化为新建结果顺序表。结果顺序表中k个元素a0…ak-1…an-1ai≠x时插入到ak-1的后面ai…i32/48template<typenameT>voidDeletex1(SqList<T>&L,intx){ //求解算法1intk=0;for(inti=0;i<L.length;i++){if(L.data[i]!=x){ //将不为x的元素插入到data中L.data[k]=L.data[i];k++;}}L.length=k; //重置L的长度为k}结果顺序表中k个元素a0…ak-1…an-1ai≠x时插入到ak-1的后面ai…i33/48

解法2：前移法，对于整数顺序表L，从头开始遍历L，用k累计当前为止值为x的元素个数（初始值为0），处理当前序号为i的元素ai：

（1）若ai是不为x的元素，此时前面有k个为x的元素，将ai前移k个位置，继续处理下一个元素。

（2）若是为x的元素，置k++，继续处理下一个元素。

最后将L的长度减少k。结果顺序表中的元素a0…ai-k-1…an-1ai≠x时前移k个位置ai…ik个要删除的元素34/48template<typenameT>voidDeletex2(SqList<T>&L,intx){ //求解算法2intk=0; //累计等于x的元素个数for(inti=0;i<L.length;i++){if(L.data[i]!=x) //将不为x的元素前移k个位置L.data[i-k]=L.data[i];else //累计删除的元素个数kk++;}L.length-=k; //将L的长度减少k}35/48结果顺序表中的元素a0…ai-k-1…an-1ai≠x时前移k个位置ai…ik个要删除的元素解法3：由解法2延伸出区间划分法

初始时，“不为x的区间”为空

i=-1，j从0开始遍历，“为x的区间”是a[i+1..j-1]若a[j]=x，跳过，j++。若a[j]≠x，操作是，先执行i++，将a[j]与a[i]进行交换，再执行j++继续遍历其余元素。a0…aiai+1…an-1aj≠x时交换aj…不为x元素区间j为x元素区间36/48template<typenameT>voidDeletex3(SqList<T>&L,intx){ //求解算法3inti=-1,j=0;while(j<L.length) { //j遍历所有元素if(L.data[j]!=x){ //找到不为x的元素a[j]i++; //扩大不为x的区间if(i!=j)swap(L.data[i],L.data[j]); //序号i和j的两个元素交换}j++; //继续遍历}L.length=i+1; //将L的长度置为i+1}37/48a0…aiai+1…an-1aj≠x时交换aj…不为x元素区间j为x元素区间设计一个算法，从一给定的顺序表L中删除元素值在x到y（x≤y）之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。…扩展各种顺序表的高效算法设计38/483.有序顺序表的算法设计有序表是指按元素值或者某属性值递增或者递减排列的线性表，有序表是线性表的一个子集。有序顺序表是有序表的顺序存储结构。对于有序表可以利用其元素的有序性提高相关算法的效率，二路归并就是有序表的一种经典算法。A=(1,3,8,23,30)一个递增有序整数顺序表39/48

【例2.4】有两个按元素值递增有序的整数顺序表A和B，设计一个算法将顺序表A和B的全部元素合并到一个递增有序顺序表C中。并给出算法的时间复杂度和空间复杂度。A=(1,3,5,8)B=(2,3,8,10,11)合并C=(1,2,3,3,5,8,8,10,11)40/48iA：a0a1…ai…an-1jB：b0b1…bj…bm-1C：c0c1…ck…cn+m-1k两者比较将较小者添加到C中二路归并：i遍历A，j遍历B，均从0开始whilei,j都没有超界

ai与bj比较：较小元素添加到C中，后移相应指针将没有遍历完的元素添加到C中41/48template<typenameT>voidMerge2(SqList<T>A,SqList<T>B,SqList<T>&C){inti=0,j=0; //i用于遍历A,j用于遍历Bwhile(i<A.length&&j<B.length){//两个表均没有遍历完毕if(A.data[i]<B.data[j]){C.Add(A.data[i]); //归并A[i]:将较小的A[i]添加到C中i++;}else{ //归并B[j]:将较小的B[j]添加到C中C.Add(B.data[j]);j++;}}42/48while(i<A.length){ //若A没有遍历完毕C.Add(A.data[i]); //归并A中剩余元素i++;}while(j<B.length){ //若B没有遍历完毕C.Add(B.data[j]); //归并B中剩余元素j++;}}43/48算法中尽管有多个while循环语句，但恰好对顺序表A、B中每个元素均访问一次，所以时间复杂度为O(n+m)。算法中需要在临时顺序表C中添加n+m个元素，所以算法的空间复杂度也是O(n+m)。44/48

二路归并中，若两个有序表的长度分别为n、m，算法的主要时间花费在元素比较上，那么比较次数是多少呢？?最好的情况下，整个归并中仅仅是较长表的第一个元素与较短表每个元素比较一次，此时元素比较次数为MIN(n，m)（为最少元素比较次数），如A=(1，2，3)，B=(4，5，6，7，8)，只需比较3次。最坏的情况下，这n+m个元素均两两比较一次，比较次数为n+m-1（为最多元素比较次数），如A=(1，3，5，7)，B=(2，4，6)，需要比较6次。45/482009年全国计算机学科考研题

【例2.5】一个长度为L（L≥1）的升序序列S，处在第

L/2

个位置的数称为S的中位数。

例如：若序列S1=(11，13，15，17，19)，则S1的中位数是15。

两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。

现有两个等长的升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。46/48S1=(11，13，15，17，19)S2=(2，4，6，8，20)二路归并S=(2，4，6，8，

11，13，15，17，19，20)中位数实际上，不需要求出S的全部元素，用k记录当前归并的元素个数，当k=n时，归并的那个元素就是中位数。

思路47/48template<typenameT>TMiddle(SqList<T>A,SqList<T>B){ //求解算法inti=0,j=0; //i,j分别遍历A和Bintk=0; //累计归并的次数while(i<A.length&&j<B.length){ //两个有序顺序表均没有遍历完k++; //归并次数增1if(A.data[i]<B.data[j]){ //A中当前元素为较小的元素if(k==A.length) //恰好归并了n次returnA.data[i]; //返回A中的当前元素i++;}else{ //B中当前元素为较小的元素if(k==B.length) //恰好归并了n次returnB.data[j]; //返回B中的当前元素j++;}}}算法的时间复杂度为O(n)，空间复杂度为O(1)。48/482.3线性表的链式存储结构2.3.1线性表的链式存储结构—链表线性表：（a0，a1，…，ai，ai+1，…，an-1）结点包含有元素值和前后继结点的地址信息结点映射49/84如果每个结点只设置一个指向其后继结点的指针成员，这样的链表称为线性单向链接表，简称单链表。开始结点尾结点头结点

a0an-1∧a1…head（a）单链表如果每个结点中设置两个指针成员，分别用以指向其前驱结点和后继结点，这样的链表称之为线性双向链接表，简称双链表。开始结点尾结点头结点dheada0a1an-1…∧（b）双链表50/842.3.2单链表

每个结点为LinkNode类型，包括存储元素的数据属性data和存储后继结点的指针next。template<typenameT>structLinkNode{

//单链表结点类型Tdata; //存放数据元素LinkNode<T>*next; //下一个结点的指针LinkNode():next(NULL){} //构造函数LinkNode(Td):data(d),next(NULL){} //重载构造函数};开始结点尾结点头结点

a0an-1∧a1…head51/84单链表类模板LinkListtemplate<typenameT>classLinkList { //单链表类模板public:LinkNode<T>*head; //单链表头结点//基本运算算法};∧head52/84head…∧单链表对象L：L.headL.head->next结点引用方式：53/841.插入和删除结点操作插入结点操作：将结点s插入到单链表中p结点的后面。a…pb…xs（c）p->next=sa…pb…xs（d）插入后a…pb…xs（a）插入前a…pb…xs（b）s->next=p->nexts->next=p->next;p->next=s;54/84删除结点操作：删除单链表中p结点的后继结点。a…pb…（a）删除前q=p->next; //q指向被删结点p->next=q->next; //从单链表中删除结点qdeleteq; //释放空间a…pb…（b）删除操作p->next=p->next->next55/842.整体建立单链表通过一个含有n个元素的a数组来建立单链表。建立单链表的常用方法有两种：头插法和尾插法。56/84头插法建表从一个空表开始，依次读取数组a中的元素。生成新结点s，将读取的数据存放到新结点的数据成员中。将新结点s插入到当前链表的表头上。s->next=head->next;head->next=s;head…∧ais57/84voidCreateListF(Ta[],intn){ //头插法建立单链表for(inti=0;i<n;i++){ //循环建立数据结点LinkNode<T>*s=newLinkNode<T>(a[i]);//创建数据结点ss->next=head->next; //将结点s插入head结点之后head->next=s;}}a=[1,2,3,4]，调用CreateListF(a,4)head41∧32头插法建立的单链表中数据结点的次序与a数组中的次序正好相反58/84尾插法建表从一个空表开始，依次读取数组a中的元素。生成新结点s，将读取的数据存放到新结点的数据成员中。将新结点s插入到当前链表的表尾上。head…ais需要设置一个尾指针r59/84voidCreateListR(Ta[],intn) { //尾插法建立单链表LinkNode<T>*s,*r;r=head; //r指向尾结点,开始时指向头结点for(inti=0;i<n;i++){ //循环建立数据结点s=newLinkNode<T>(a[i]); //创建数据结点sr->next=s; //将结点s插入结点r之后r=s;}r->next=NULL; //将尾结点的next域置为NULL}a=[1,2,3,4]，调用CreateListR(a,4)head14∧23尾插法建立的单链表中数据结点的次序与a数组中的次序正好相同60/843.线性表基本运算在单链表中的实现查找序号为i（-1≤i≤n-1，n为单链表中数据结点个数）的结点//*******************************************//序号i的正确范围：-1≤i<n，超出范围返回NULL//i=-1时返回头结点head//i≥0并且i<n时返回序号i的结点//*******************************************LinkNode<T>*geti(inti){ //返回序号i的结点if(i<-1)returnNULL; //i<-1返回NULLLinkNode<T>*p=head; //首先p指向头结点intj=-1; //j置为-1(可以认为头结点序号为-1)while(j<i&&p!=NULL){ //指针p移动i+1个结点j++;p=p->next;}returnp; //返回p}head…ai…p-10i61/84（1）单链表的初始化和销毁LinkList(){

//构造函数,创建一个空单链表head=newLinkNode<T>();}构造函数62/84~LinkList(){

//析构函数,销毁单链表LinkNode<T>*pre,*p;pre=head;p=pre->next;while(p!=NULL){ //用p遍历结点并释放其前驱结点deletepre; //释放pre结点pre=p;p=p->next; //pre,p同步后移一个结点}deletepre; //p为空时pre指向尾结点,此时释放尾结点}析构函数循环结束条件是p为空prehead…∧while开始前：∧while结束后：p每次释放结点pre，再同步后移prep=NULL63/84（2）将元素e添加的线性表末尾Add(e)voidAdd(Te){ //在单链表末尾添加一个值为e的结点

LinkNode<T>*s=newLinkNode<T>(e); //新建结点sLinkNode<T>*p=head;while(p->next!=NULL) //查找尾结点pp=p->next;p->next=s; //在尾结点之后插入结点s}head…esp添加64/84（3）求线性表的长度Getlength()intGetlength(){ //求单链表中数据结点个数LinkNode<T>*p=head;intcnt=0;while(p->next!=NULL){ //找到尾结点为止cnt++;p=p->next;}returncnt;}若像顺序表中一样，在单链表中设置一个长度length，插入时length++，删除时length--。那么求长度的时间复杂度为O(1)了。提示65/84（4）求线性表中序号为i的元素GetElem(i,&e)boolGetElem(inti,T&e){ //求单链表中序号i的结点值if(i<0)returnfalse; //参数i错误返回falseLinkNode<T>*p=geti(i); //查找序号i的结点if(p!=NULL){ //找到了序号i的结点pe=p->data;returntrue; //成功找到返回true}else //不存在序号i的结点returnfalse; //参数i错误返回false}66/84（5）设置线性表中序号为i的元素SetElem(i，e)boolSetElem(inti,Te){ //设置序号i的结点值if(i<0)returnfalse; //参数i错误返回falseLinkNode<T>*p=geti(i); //查找序号i的结点if(p!=NULL){ //找到了序号i的结点pp->data=e;returntrue;}else //不存在序号i的结点returnfalse; //参数i错误返回false}67/84（6）求线性表中第一个值为e的元素的逻辑序号GetNo(e)intGetNo(Te) { //查找第一个为e的元素的序号intj=0; //j置为0，p指向首结点LinkNode<T>*p=head->next;

while(p!=NULL&&p->data!=e){ //查找第一个值为e的结点pj++; p=p->next;}if(p==NULL)return-1; //未找到时返回-1elsereturnj; //找到后返回其序号}循环结束条件：p不为空且p->data=ep，j=0head…∧while开始前：p指向第一个值为e的结点head…∧ewhile结束后：…01n-10jn-168/84（7）在线性表中插入e作为第i个元素Insert(i，e)head…es…第i-1个结点pp69/84boolInsert(inti,Te){ //在序号i位置插入值为e的结点if(i<0)returnfalse; //参数i错误返回falseLinkNode<T>*s=newLinkNode<T>(e);//建立新结点sLinkNode<T>*p=geti(i-1); //查找序号i-1的结点if(p!=NULL){ //找到了序号i-1的结点ps->next=p->next; //在p结点后面插入s结点p->next=s;returntrue; //插入成功返回true}else //没有找到序号i-1的结点returnfalse; //参数i错误返回false}head…es第i-1个结点p…p70/84（8）在线性表中删除第i个数据元素Delete(i)head…∧…第i-1个结点pp先查找第i-1个结点p：①如果存在结点p，若存在后继结点q，删除结点q，返回true；若不存在后继结点q，返回false②如果不存在结点p，返回false71/84boolDelete(inti){ //在单链表中删除序号i位置的结点if(i<0)returnfalse; //参数i错误返回falseLinkNode<T>*p=geti(i-1); //查找序号i-1的结点if(p!=NULL){ //找到了序号i-1的结点pLinkNode<T>*q=p->next; //q指向序号i的结点(被删结点)

if(q!=NULL){ //存在序号i的结点时删除它p->next=q->next; //删除p结点的后继结点deleteq; //释放空间returntrue; //删除成功返回true}else //没有找到序号i的结点returnfalse; //参数i错误返回false}else //没有找到序号i-1的结点returnfalse; //参数i错误返回false}删除第i个结点算法72/84（9）输出线性表所有元素DispList()voidDispList(){ //输出单链表所有结点值LinkNode<T>*p;p=head->next; //p指向开始结点while(p!=NULL){ //p不为NULL,输出p结点的data域cout<<p->data<<"";p=p->next; //p移向下一个结点}cout<<endl;}73/842.3.3单链表的应用算法设计示例1.基于单链表基本操作的算法设计

【例2.6】有一个长度大于2的整数单链表L，设计一个算法查找L中中间位置的元素。

例如，L=（1，2，3），返回元素为2；L=（1，2，3，4），返回元素为2。74/84

计数法：计算出L的长度n，假设首结点的编号为1，则满足题目要求的结点的编号为(n-1)/2+1（这里的除法为整除）。置j=1，指针p指向首结点，让其后移(n-1)/2个结点即可。template<typenameT>TMiddle1(LinkList<T>&L){ //求解算法1intj=1;intn=L.Getlength();LinkNode<T>*p=L.head->next; //p指向首结点while(j<=(n-1)/2){ //找中间位置的p结点j++;p=p->next;}returnp->data;}75/84template<typenameT>TMiddle2(LinkList<T>&L){ //求解算法2LinkNode<T>*slow=L.head->next;LinkNode<T>*fast=L.head->next; //均指向首结点while(fast!=NULL&&slow!=NULL){if(fast->next==NULL||fast->next->next==NULL)returnslow->data; //满足结束条件时返回slow=slow->next; //慢指针每次后移1个结点fast=fast->next->next; //快指针每次后移2个结点}}

快慢指针法：设置快慢指针fast和slow，首先均指向首结点，当fast结点后面至少存在两个结点时，让慢指针slow每次后移动一个结点，让快指针fast每次后移动两个结点。否则slow指向的结点就是满足题目要求的结点。76/84

【例2.7】有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法查找L中最大值结点的个数。

先让p指向首结点，用maxe记录首结点值，将其看成是最大值结点，cnt置为1。按以下方式循环直到p指向尾结点为止：

（1）若p->next.data>maxe，将p->next看成新的最大值结点，置maxe=p->next->data，cnt=1。

（2）若p->next->data==maxe，maxe仍为最大结点值，置cnt++。

（3）p后移一个结点。

最后返回cnt即为最大值结点个数。77/84template<typenameT>intMaxcount(LinkList<T>&L){ //求解算法intcnt=1;LinkNode<T>*p=L.head->next; //p指向首结点Tmaxe=p->data; //maxe置为首结点值while(p->next!=NULL){ //循环到p结点为尾结点if(p->next->data>maxe){ //找到更大的结点maxe=p->next->data; //第一次找到maxe的结点cnt=1;}elseif(p->next->data==maxe) //p结点为当前最大值结点cnt++; //次数增1

p=p->next;}returncnt;}78/84

【例2.8】有一个整数单链表L，其中可能存在多个值相同的结点，设计一个算法删除L中所有最大值的结点。过程如下：先遍历L的所有结点，求出最大结点值maxe。再遍历一次删除所有值为maxe的结点，在删除中，通过（pre，p）一对指针指向相邻的两个结点，若p->data==maxe，再通过pre结点删除p结点。79/84template<typenameT>voidDelmaxnodes(LinkList<T>&L){ //求解算法LinkNode<T>*p=L.head->next; //p指向首结点Tmaxe=p->data; //maxe置为首结点值while(p->next!=NULL){ //查找最大结点值maxeif(p->next->data>maxe)maxe=p->next->data;p=p->next;}LinkNode<T>*pre=L.head; //pre指向头结点p=pre->next; //p指向pre的后继结点while(p!=NULL){ //p遍历所有结点if(p->data==maxe){ //p结点为最大值结点pre->next=p->next; //删除p结点deletep;p=pre->next; //让p指向pre的后继结点}else{pre=pre->next; //pre后移一个结点p=pre->next; //让p指向pre的后继结点}}}80/842.基于整体建立单链表的算法设计

【例2.9】有一个整数单链表L，设计一个算法逆置L中的所有结点。例如L=(1，2，3，4，5)，逆置后L=(5，4，3，2，1)。template<typenameT>voidReverse1(LinkList<T>&L) { //求解算法1LinkNode<T>*p=L.head->next,*q; //p指向首结点L.head->next=NULL; //将L置为一个空表while(p!=NULL){ //用p遍历所有数据结点q=p->next; //q临时保存p结点的后继结点p->next=L.head->next; //将p结点插入到表头L.head->next=p;p=q;}}解法1：采用头插法建表的思路81/84解法2：3指针方法q->next=pL.head->next=qq->next=phead…∧pqrr!=NULL时循环：head…pqr=NULL时：循环直到r为空82/84template<typenameT>voidReverse2(LinkList<T>&L) { //求解算法2LinkNode<T>*p=L.head->next,*q,*r;//p指向首结点if(p==NULL)return; //L为空单链表时返回q=p->next;if(q==NULL)return; //L只有一个结点时返回r=q->next; //r指向第3个结点if(r==NULL){ //L只有一个结点时L.head->next=q;q->next=p;p->next=NULL;return;}p->next=NULL; //原首结点p置为尾结点while(r!=NULL){ //(p,q,r)指向的结点都存在时循环q->next=p; //修改结点q的next指针p=q; //(p,q,r)同步指针后移q=r;r=r->next;}q->next=p; //修改结点q的next指针L.head->next=q;}83/84不建议：远不如解法1清晰！

【例2.10】有一个含2n个整数的单链表L=（a0，b0，a1，b1，…，an-1，bn-1），设计一个算法将其拆分成两个带头结点的单链表A和B。

其中A=（a0，a1，…，an-1），B=（bn-1，bn-2，…，b0）。La0b0bn-1∧…an-1Aa0a1an-1∧…an-2Bbn-1bn-2b0∧…b184/84L=(a0，b0，a1，b1，…，an-1，bn-1)A=(a0，a1，…，an-1)，B=(bn-1，bn-2，…，b0)尾插法建表A∧p…B头插法建表

思路85/84template<typenameT>voidSplit(LinkList<T>&L,LinkList<T>&A,LinkList<T>&B){LinkNode<T>*p=L.head->next,*q; //p指向L的首结点LinkNode<T>*r=A.head; //r始终指向A的尾结点while(p!=NULL){ //遍历L的所有数据结点r->next=p;r=p; //尾插法建立Ap=p->next; //p后移一个结点if(p!=NULL){q=p->next; //临时保存p结点的后继结点p->next=B.head->next; //头插法建立BB.head->next=p;p=q; //p指向q结点}}r->next=NULL; //尾结点next置空}86/843.有序单链表的算法设计

【例2.11】有两个递增有序整数单链表A和B，设计一个算法采用二路归并方法将A和B的所有数据结点合并到递增有序单链表C中。

要求算法的空间复杂度为O(1)。算法的空间复杂度为O(1)?87/84template<typenameT>voidMerge2(LinkList<T>&A,LinkList<T>&B,LinkList<T>&C){LinkNode<T>*p=A.head->next; //p指向A的首结点LinkNode<T>*q=B.head->next; //q指向B的首结点LinkNode<T>*r=C.head; //r为C的尾结点while(p!=NULL&&q!=NULL) { //两个单链表都没有遍历完if(p->data<q->data){ //将较小结点p链接到C的末尾r->next=p;r=p;p=p->next;}else{ //将较小结点q链接到C的末尾r->next=q;r=q;q=q->next;}}r->next=NULL; //尾结点next置空if(p!=NULL)r->next=p; //将未归并完的结点链接到C的末尾if(q!=NULL)r->next=q;}88/84

【例2.12】有两个递增有序整数单链表A和B，假设每个单链表中没有值相同的结点，但两个单链表中存在相同值的结点，设计一个尽可能高效的算法建立一个新的递增有序整数单链表C，其中包含A和B相同值的结点，要求算法执行后不改变单链表A和B。89/84A=(1,3,5,7,8)B=(1,2,5,8,10,11)C=(1,5,8)二路归并二路归并+尾插法新建单链表C90/84template<typenameT>voidCommnodes(LinkList<T>&A,LinkList<T>&B,LinkList<T>&C){LinkNode<T>*p=A.head->next; //p指向A的首结点LinkNode<T>*q=B.head->next; //q指向B的首结点LinkNode<T>*r=C.head; //r为C的尾结点while(p!=NULL&&q!=NULL) { //两个单链表都没有遍历完if(p->data<q->data) //跳过较小的p结点p=p->next;elseif(q->data<p->data) //跳过较小的q结点q=q->next;else{ //p结点和q结点值相同LinkNode<T>*s=newLinkNode<T>(p->data);r->next=s;r=s; //将s结点链接到C的末尾p=p->next;q=q->next;}}r->next=NULL; //尾结点next置空}91/84本算法的时间复杂度为O(n+m)。空间复杂度为O(MIN(n，m))。其中m、n分别为A、B单链表中的数据结点个数，MIN为取最小值函数，因为单链表C中最多只有MIN(n，m)个结点。92/84基本操作1…基本算法设计1基本算法设计m……问题求解基本操作2基本操作n…数据结构的知识结构数据结构存储结构设计通用算法设计方法1……通用算法设计方法k总结93/84各种数据结构的知识结构逻辑结构特征+基本运算存储结构存储结构的基本操作基本运算算法设计应用算法设计复杂算法设计94/84逻辑结构特征+基本运算存储结构存储结构的基本操作基本运算算法设计应用算法设计复杂算法设计逻辑特征：元素为一对一关系基本运算：查找、插入和删除等顺序表，单链表、双链表和循环链表单链表：指针p后移，在p结点之后插入一个结点，删除结点p的后继结点头插法、尾插法、查找、插入和删除等算法设计单链表逆置，有序单链表二路归并，…两个单链表的公共结点，两个有序单链表的公共结点，3个有序单链表的归并，…线性表95/842.3.4双链表开始结点尾结点头结点dheada0a1an-1…∧

每个结点为DLinkNode类型，包括存储元素的列表data、存储前驱结点指针prior和后继结点指针next。template<typenameT>structDLinkNode{

//双链表结点类型Tdata; //存放数据元素DLinkNode<T>*next; //指向后继结点的指针DLinkNode<T>*prior; //指向前驱结点的指针DLinkNode():next(NULL),prior(NULL){} //构造函数DLinkNode(Td):data(d),next(NULL),prior(NULL){}//重载构造函数};DLinkNode类型96/84双链表类模板DLinkListtemplate<typenameT>classDLinkList{

//双链表类模板public:DLinkNode<T>*dhead; //双链表头结点

//基本运算算法};∧dhead∧97/84…p…∧s（b）s->next=p->next1.插入和删除结点操作插入结点操作：将结点s插入到双链表中p结点的后面。…p…∧∧s（a）插入前98/84…p∧s（c）p->next->prior=s……p…s（d）s->prior=p说明尽可能让间接结点指针修改靠前执行！…ps（e）p->next=s…99/84删除结点操作：删除双链表中的p结点。……（a）删除前p……（b）p->next->prior=p->priorp……（c）p->prior->next=p->nextp100/842.整体建立双链表通过一个含有n个元素的a数组来建立双链表。建立双链表的常用方法有两种：头插法和尾插法。101/84头插法建表voidCreateListF(Ta[],intn) { //头插法建立双链表DLinkNode<T>*s;for(inti=0;i<n;i++){ //循环建立数据结点s=newDLinkNode<T>(a[i]); //创建数据结点ss->next=dhead->next; //修改s结点的next成员if(dhead->next!=NULL) //修改头结点的非空后继结点的priordhead->next->prior=s;dhead->next=s; //修改头结点的nexts->prior=dhead; //修改s结点的prior}}s头结点dheadai…102/84尾插法建表voidCreateListR(Ta[],