数据结构与算法设计

数据结构与算法设计课件第一页，共九十九页，编辑于2023年，星期三线性表是一种最简单的线性结构。

什么是线性结构？简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：

1．集合中必存在唯一的一个"第一元素"；

2．集合中必存在唯一的一个"最后元素"；

3．除最后元素之外，其它数据元素均有唯一的"后继"；

4．除第一元素之外，其它数据元素均有唯一的"前驱"。第二页，共九十九页，编辑于2023年，星期三2.1.1抽象数据类型线性表的定义

通常可以下列“n个数据元素的序列”表示线性表(Linear_List)

(a1,a2,...,ai,...,an)

序列中数据元素的个数n定义为线性表的表长；n=0时的线性表被称为空表。称i为ai在线性表中的位序。其抽象数据类型的定义如下：

ADTList{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{<ai-1,ai>|,∈D,i=2,...,n}第三页，共九十九页，编辑于2023年，星期三基本操作：

{结构初始化}

InitList(&L)

操作结果：构造一个空的线性表L。{销毁结构}

DestroyList(&L)

初始条件：线性表L已存在。

操作结果：销毁线性表L。第四页，共九十九页，编辑于2023年，星期三{引用型操作}ListEmpty(L)

初始条件：线性表L已存在。

操作结果：若L为空表，则返回TRUE，否则返回FALSE。ListLength(L)

初始条件：线性表L已存在。

操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)

初始条件：线性表L已存在。

操作结果：若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。第五页，共九十九页，编辑于2023年，星期三NextElem(L,cur_e,&next_e)

初始条件：线性表L已存在。

操作结果：若cur_e是L中的数据元素，则用next_e返回它的后继，

否则操作失败，next_e无定义。GetElem(L,i,&e)

初始条件：线性表L已存在，1≤i≤LengthList(L)。

操作结果：用e返回L中第i个元素的值。第六页，共九十九页，编辑于2023年，星期三LocateElem(L,e,compare())

初始条件：线性表L已存在，compare()是元素判定函数。

操作结果：返回L中第1个与e满足关系compare()的元素的位序。

若这样的元素不存在，则返回值为0。ListTraverse(L,visit())

初始条件：线性表L已存在，visit()为元素的访问函数。

操作结果：依次对L的每个元素调用函数visit()。

一旦visit()失败，则操作失败。第七页，共九十九页，编辑于2023年，星期三{加工型操作}ClearList(&L)

初始条件：线性表L已存在。

操作结果：将L重置为空表。PutElem(&L,i,&e)

初始条件：线性表L已存在，1≤i≤LengthList(L)。

操作结果：L中第i个元素赋值同e的值。第八页，共九十九页，编辑于2023年，星期三ListInsert(&L,i,e)

初始条件：线性表L已存在，1≤i≤LengthList(L)+1。

操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。ListDelete(&L,i,&e)

初始条件：线性表L已存在且非空，1≤i≤LengthList(L)。

操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList第九页，共九十九页，编辑于2023年，星期三2.1.2线性表类型的应用

如果已经实现了上述定义的线性表类型，那么在应用问题的求解中就可以利用类型中定义的各种操作。下面将举三个例子说明之。第十页，共九十九页，编辑于2023年，星期三例2-1

已知集合

A和

B，求两个集合的并集，使

A＝A∪B，且

B不再单独存在。

从集合的观点看，此问题求解的方法很简单，只要对集合

B中的所有元素一个一个地检查，看看在集合

A中是否存在相同元素，若不存在，则将该元素插入到集合

A，否则舍弃之。

要在计算机中求解，首先要确定"如何表示集合"。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。

现假设以线性表

LA和

LB分别表示集合

A和

B，即构造两个线性表

LA和

LB，它们的数据元素分别为集合

A和

B中的成员。

由此，上述集合求并的问题便可演绎为：要求对线性表作如下操作：扩大线性表

LA，将存在于线性表

LB中而不存在于线性表

LA中的数据元素插入到线性表

LA中去。第十一页，共九十九页，编辑于2023年，星期三具体操作步骤为：

1．从线性表

LB中取出一个数据元素；

2．依值在线性表

LA中进行查询；

3．若不存在，则将它插入到

LA中。

重复上述三步直至

LB为空表止。

那么，其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢？第十二页，共九十九页，编辑于2023年，星期三容易看出，上述的每一步恰好对应线性表的一个基本操作：

1.ListDelete(LB,1,e);

2.LocateElem(LA,e,equal());

3.ListInsert(LA,n+1,e)

第十三页，共九十九页，编辑于2023年，星期三由此得到求并集的算法如下所示：算法2.1

voidunion(List&LA,List&LB)

{//将所有在线性表LB中但不在LA中的数据元素插入到LA中,算法执行之后，线性表LB不再存在。

La_len=ListLength(LA);//求得线性表LA的长度

while(!ListEmpty(LB))//依次处理LB中元素直至LB为空表止

{

ListDelete(LB,1,e);//从LB中删除第1个数据元素并赋给e

if(!LocateElem(LA,e,equal())

ListInsert(LA,++La_len,e);

//当LA中不存在和e值相同的数据元素时进行插入

}//while

DestroyList(LB);//销毁线性表LB

)//union第十四页，共九十九页，编辑于2023年，星期三例2-2已知一个"非纯集合"B，试构造一个集合A，使A中只包含B中所有值各不相同的数据元素。换句话说，此问题即为从

B中挑选出所有"彼此相异"的元素构成一个新的集合。如何区分元素的"相异"或"相同"，一个简单方法即为将每个从

B中取出的元素和已经加入到集合

A中的元素相比较。

如果还是以线性表

LB和

LA分别表示"集合"B和

A，那么和例2-1的问题相比，此问题求解的算法应该如何写呢？第十五页，共九十九页，编辑于2023年，星期三容易看出，应对线性表作和上例相同的操作，具体的三步也都相同，所不同之处仅仅在于两点：一是例2-1的算法中

LA是已知的，而在此例算法中的

LA是待新建的；二是例2-1在求得并集之后，原来的两个集合不再保留，而在此例中构建新的集合

A的同时，原来的集合

B不变。第十六页，共九十九页，编辑于2023年，星期三算法2.2

voidpurge(List&LA,ListLB)

{

//构造线性表LA，使其只包含LB中所有值不相同的数据

//元素,算法不改变线性表LB

InitList(LA);

//创建一个空的线性表

LA

La_len=0;

Lb_len=ListLength(LB);

//求线性表

LB的长度

for(i=1;i<=Lb_len;i++)//依次处理

LB中每个元素

{

GetElem(LB,i,e);//取

LB中第

i个数据元素赋给

e

if(!LocateElem(LA,e,equal())

ListInsert(LA,++La_len,e);

//当

LA中不存在和

e值相同的数据元素时进行插入

}//for

)//purge

第十七页，共九十九页，编辑于2023年，星期三例2-3

判别两个集合是否相等。

两个集合相等的充分必要条件是它们具有相同的元素。当以线性表表示集合时，两个线性表的长度应该相等，且表中所有数据元素都能一一对应，但相同的数据元素在各自的线性表中的"位序"不一定相同。

由此，"判别两个线性表中的数据元素是否完全相同"的算法的基本思想为：首先判别两者的表长是否相等；在表长相等的前提下，如果对于一个表中的所有元素，都能在另一个表中找到和它相等的元素的话，便可得到"两个线性表表示的集合相等"的结论；反之，只要有一个元素在另一个表中不能找到相等元素时，便可得出"不等"的结论。第十八页，共九十九页，编辑于2023年，星期三算法2.3

boolisEqual(ListLA,ListLB)

{

//若线性表LA和LB不仅长度相等，且所含数据元素也相同，

//则返回TRUE，否则返回FALSE。

La_len=Listlength(LA);

Lb_len=Listlength(LB);if(La_len!=Lb_len)return

FALSE;//两表的长度不等

else

{

i=1;found=TRUE;

while(i<=La_len&&found)

{

GetElem(LA,i,e);

//取得

LA中一个元素

if(LocateElem(LB,e,equal())

i++;

//依次处理下一个

elsefound=FALSE;//LB中没有和该元素相同的元素

}//while

returnfound;

}//else

)//isEqual

第十九页，共九十九页，编辑于2023年，星期三2.2.1顺序表

顺序表是线性表的顺序存储表示的简称，它指的是，“用一组地址连续的存储单元依次存放线性表中的数据元素”，即以“存储位置相邻”表示“位序相继的两个数据元素之间的前驱和后继的关系(有序对<ai-1,ai>)”，并以表中第一个元素的存储位置作为线性表的起始地址，称作线性表的基地址。如下图所示。第二十页，共九十九页，编辑于2023年，星期三不失一般性，假设每个数据元素占据的存储量是一个常量C，则后继元素的存储地址和其前驱元素相隔一个常量，

即：LOC(ai)=LOC(ai-1)+C

↑一个数据元素所占存储量由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到

LOC(ai)=LOC(a1)+(i-1)×C

↑基地址

第二十一页，共九十九页，编辑于2023年，星期三用C语言描述的顺序表类型如下所示：

//存储结构

const

intMAXLISTSIZE=80;//预设的存储空间最大容量

typedefstruct{

ElemType*elem;

//存储空间基址

intlength;

//当前长度

intlistsize;

//允许的最大存储容量(以sizeof(ElemType)为单位)

}

SqList;

//俗称

顺序表

第二十二页，共九十九页，编辑于2023年，星期三//基本操作接口(函数声明)

voidInitList(SqList&L,intmaxsize);

//构造一个最大存储容量为maxsize的空的顺序表L。voidDestroyList(SqList&L)

//

销毁顺序表

L。

boolListEmpty(SqListL)

//

若顺序表

L为空表，则返回TRUE，否则返回

FALSE。

intListLength(SqListL)

//

返回顺序表

L中元素个数。

intPriorElem(SqListL,ElemTypecur_e)

//

若

cur_e是顺序表

L的元素，则返回其前驱的位序

//

(设第一个元素的前驱的位序为0)，否则返回-1。

第二十三页，共九十九页，编辑于2023年，星期三intNextElem(SqListL,ElemTypecur_e)

//若cur_e是顺序表L的元素，则返回其后继的位序

//(设最后一个元素的后继的位序为L的表长+1)，否则返回-1。boolGetElem(SqListL,intpos,ElemType&e)

//若1≤pos≤LengthList(L)，则用e带回顺序表L中第

//pos个元素的值且返回函数值为TRUE，否则返回函数值为FALSE。intLocateElem(SqListL,ElemTypee,bool(*compare)(ElemType,ElemType))

//返回顺序表L中第1个与e

满足关系compare()的数据元素的位序。

//若这样的元素不存在，则返回值为0。compare()为数据元素的判定函数。voidListTraverse(SqListL,void(*visit)(ElemType))

//依次对顺序表L的每个元素调用函数visit()。

//一旦visit()失败，则操作失败。voidClearList(SqList&L)//

将顺序表

L重置为空表。

第二十四页，共九十九页，编辑于2023年，星期三boolPutElem(SqListL,intpos,ElemType&e)

//

若1≤pos≤LengthList(L)，则对顺序表

L中第

pos个元素

//赋值同

e的值且返回函数值为

TRUE，否则返回函数值为

FALSE。

boolListInsert(SqList&L,intpos,ElemTypee)

//

若存储空间未满且1≤pos≤LengthList(L)+1，则在顺序表

L的

//第

pos个元素之前插入新的元素

e，L的长度增1，且返回函数值为TRUE，

//

否则不改变顺序表且返回函数值为

FALSE。

boolListDelete(SqList&L,intpos,ElemType&e)

//

若1≤pos≤LengthList(L)，则删除顺序表

L的第

pos个元素

e，

//

L的长度增1，且返回函数值为TRUE，否则不改变顺序表且返回函数值为FALSE。

第二十五页，共九十九页，编辑于2023年，星期三以上定义的函数可在程序设计中引用，例如，上述算法2.2可改写为下列可在主函数中调用的函数。

voidpurge(SqList&La,SqListLb)

{

//构造顺序表

La，使其只包含

Lb中所有值不相同的数据元素,

//算法不改变顺序表

Lb

boolb;

intLb_len=Listlength(Lb);

//求线性表

Lb的长度

InitList(La,Lb_len);

//创建一个空的线性表

La

intLa_len=0;

for(i=1;i<=Lb_len;i++)

//依次处理

Lb中每个元素

{

b=GetElem(Lb,i,e);

//取Lb中第

i个数据元素赋给

e

if(!LocateElem(La,e,equal()))

{

++La_len;

b=ListInsert(La,La_len,e);//当

La中不存在和

e值相同的

}

//数据元素时，进行插入

}//for

第二十六页，共九十九页，编辑于2023年，星期三2.2.2顺序表中基本操作的实现

从顺序表的存储结构定义容易看出，由于顺序表的"长度"是个"显值"，且由于第i个元素恰好存储在数组的第

i个分量(数组下标为

i-1)中，因此其"求长"、"判空"以及"存取第

i个数据元素"等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。

一、初始化操作

二、元素定位操作

三、插入元素操作

四、删除元素操作

五、销毁结构操作

第二十七页，共九十九页，编辑于2023年，星期三一、初始化操作

对顺序表而言，"初始化"的实质是为它分配一个"足够应用"的元素存储空间，由用户根据它对线性表的使用要求定义一个最大存储容量

maxsize，并约定当用户没有提出特殊需求(maxsize=0)时，按予设的最大存储量

MAXLISTSIZE进行分配。第二十八页，共九十九页，编辑于2023年，星期三算法2.4

voidInitList(SqList&L,intmaxsize)

{

//构造一个空的线性表L

if(maxsize==0)

maxsize=MAXLISTSIZE;

L.elem=newElemType[maxsize];if(!L.elem)

exit(1);

//存储分配失败

L.length=0;

//顺序表的初始长度为0

L.listsize=maxsize;

//该顺序表可以存储元素的最大容量

}//InitList

此算法的时间复杂度为O(1)。

第二十九页，共九十九页，编辑于2023年，星期三二、元素定位操作

在顺序表中"查询"是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。第三十页，共九十九页，编辑于2023年，星期三算法2.5intLocateElem(SqListL,ElemTypee,

void(*compare)(ElemType,ElemType)){//在顺序表L中查找第1个值与

e满足判定条件compare()的元素，

//若找到，则返回其在

L中的位序，否则返回0。

i=1;

//i的初值为第1元素的位序

p=L.elem;

//p的初值为第1元素的存储位置

while(i<=L.length&&!(*compare)(*p++,e))

++i;

//依次进行判定

if(i<=L.length)returni;

//找到满足判定条件的数据元素为第

i个元素

else

return0;

//该线性表中不存在满足判定的数据元素

}//LocateElem

此算法的时间复杂度为：O(ListLength(L))

第三十一页，共九十九页，编辑于2023年，星期三三、插入元素操作

首先分析，“插入元素”使线性表的逻辑结构发生什么变化？

假设在线性表的第i个元素之前插入一个元素e，使得线性表

(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)

即：(1)改变了表中元素之间的关系，使<ai-1,ai>改变为<ai-1,e>和<e,ai>(2)表长增1

由于顺序表是以"存储位置相邻"表示"元素之间的前驱和后继关系"，则必须"移动元素"来体现"元素之间发生的变化"。第三十二页，共九十九页，编辑于2023年，星期三算法2.6boolListInsert(SqList&L,intpos,ElemTypee){

//若存储空间不满且1≤pos≤Listlength(L)+1，则在顺序表

L

的

//第

pos个元素之前插入新的元素

e且返回TRUE，否则返回FALSE

if(pos<1||pos>L.length+1)

returnFALSE;//插入位置不合法

if(L.length>=L.listsize)returnFALSE;

//当前存储空间已满，无法插入

for(j=L.length-1;j>=pos-1;--j)

L.elem[j+1]=L.elem[j];//插入位置及之后的元素右移L.elem[pos-1]=e;

//插入

e

++L.length;

//表长增1

return

TRUE;

}//ListInsert

此算法的时间复杂度为：O(ListLength(L))

第三十三页，共九十九页，编辑于2023年，星期三四、删除元素操作

同样首先分析，“删除元素”使线性表的逻辑结构发生什么变化？

假设删除线性表中第i个元素，使得线性表

(a1,…,ai-1,ai,ai+1,…,an)改变为(a1,…,ai-1,ai+1,…,an)即：(1)改变了表中元素之间的关系，使<ai-1,ai>和<ai,ai+1>改变为<ai-1,ai+1>(2)表长减1

对顺序表而言，需要改变从第

i+1个元素起到第

n个元素的存储位置，即进行"从第

i+1到第

n个元素往前移动一个位置"。第三十四页，共九十九页，编辑于2023年，星期三算法2.7boolListDelete(SqList&L,intpos,ElemType&e){//若1≤pos≤Listlength(L)，则以e带回从顺序表L中删除的//第pos个元素且返回TRUE，否则返回FALSE

if((pos<1)||(pos>L.length))

returnFALSE;//删除位置不合法

for(j=pos;j<L.length;++j)

L.elem[j-1]=L.elem[j];//被删除元素之后的元素左移--L.length;

//表长减1

returnTRUE;}//ListDelete

此算法的时间复杂度为：O(ListLength(L))

第三十五页，共九十九页，编辑于2023年，星期三五、销毁结构操作算法2.8voidDestroyList(SqList&L){//释放顺序表L所占存储空间

delete[]L.elem;

L.listsize=0;

L.length=0;

}//DestroyList_Sq

此算法的时间复杂度为：O(1)

第三十六页，共九十九页，编辑于2023年，星期三六、插入和删除操作的性能分析(p25)第三十七页，共九十九页，编辑于2023年，星期三2.2.3顺序表其它算法举例

例2-4试编写算法“比较”两个顺序表的大小。

算法的基本思想为：若ai=bj，则j增1，之后继续比较后继元素；否则即可得出比较结果。显然，j的初值应为0，循环的条件是j不超出其中任何一个表的范围。若在循环内不能得出比较结果，则循环结束时有三种可能出现的情况需要区分。

根据以上分析可得下列算法。第三十八页，共九十九页，编辑于2023年，星期三算法2.9intcompare(SqListA,SqListB){//若A<B，则返回-1；若A=B，则返回0；若A>B，则返回1

j=0;

while(j<A.length&&j<B.length)

if(A.elem[j]<B.elem[j])return(-1);

elseif(A.elem[j]>B.elem[j])return(1);

elsej++;

if(A.length==B.length)return(0);

elseif(A.length<B.length)return(-1);

elsereturn(1);

}//compare

上述算法中只有一个while循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法2.9的时间复杂度为O(Min(A.length,B.length))。第三十九页，共九十九页，编辑于2023年，星期三例2-5试设计一个算法，用尽可能少的辅助空间将顺序表中前m个元素和后n个元素进行互换，即将线性表(a1,a2,…,am,b1,b2,…,bn)改变成(b1,b2,…,bn,a1,a2,…,am)。

第四十页，共九十九页，编辑于2023年，星期三算法2.10voidinvert(ElemType&R[],ints,intt){//本算法将数组R中下标自s到t的元素逆置，即将//（Rs,Rs+1,…,Rt-1,Rt）改变为（Rt,Rt-1,…,Rs+1,Rs）

for(k=s;k<=(s+t)/2;k++)

{

w=R[k];

R[k]=R[t-k+s];

R[t-k+s]=w;

}//for}//invert

第四十一页，共九十九页，编辑于2023年，星期三算法2.11voidexchange(SqList&A,intm){//本算法实现顺序表中前m个元素和后n个元素的互换

if(m>0&&m<A.length){

n=A.length-m;

invert(A.elem,0,m+n-1);

invert(A.elem,0,n-1);

invert(A.elem,n,m+n-1);

}

}//exchange第四十二页，共九十九页，编辑于2023年，星期三例2-6编写算法删除顺序表中"多余"的数据元素，即使操作之后的顺序表中所有元素的值都不相同。

第四十三页，共九十九页，编辑于2023年，星期三算法2.12voidpurge_Sq(SqList&L){

//删除顺序表L中的冗余元素，即使操作之后的顺序表中只保留

//操作之前表中所有值都不相同的元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length;++i)//顺序考察表中每个元素

{

j=0;

while(j<=k&&L.elem[j]!=L.elem[i])

++j;//在新表中查询是否存在和L.elem[i]相同的元素

if(k==-1||j>k)//k=-1表明当前考察的是第一个元素

L.elem[++k]=L.elem[i];

}//for

L.length=k+1;//修改表长

}//purge_Sq

此算法的时间复杂度为O(ListLength2(L))

第四十四页，共九十九页，编辑于2023年，星期三分析：

算法中的基本操作为"比较"，控制结构为两重循环，外循环的执行次数和顺序表的表长相同，内循环的执行次数则不超过表长。此外，"比较"操作相对于"移动"操作所需的时间也少。

从这个题的算法可以得到一些有益的启示，某种情况下，"删除"操作也可利用"插入"来实现。第四十五页，共九十九页，编辑于2023年，星期三2.3.1单链表和指针

线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如下图所示），表示线性表中一个数据元素ai

其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。数据域data指针域next第四十六页，共九十九页，编辑于2023年，星期三由分别表示a1,a2,…,an的N个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表，如下图所示。和顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，通常称它为头指针，线性表中所有数据元素都可以从头指针出发找到。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的"指针"是一个特殊的值"NULL"（在图上用∧表示），通常称它为"空指针"。第四十七页，共九十九页，编辑于2023年，星期三为了便于处理一些特殊情况，在第一个结点之前附加一个"头结点"，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，如下图所示。

值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空(NULL)，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空，如下图所示。

第四十八页，共九十九页，编辑于2023年，星期三可以用C语言中的“结构指针”来描述链表结构typedefstructLNode{

ElemTypedata;

structLNode*next;

}*SLink;

若设LNode*p,*q;

SLinkH;

则p，q和H均为以上定义的指针型变量。若p的值非空，则表明p指向某个结点，p->data表示p所指结点中的数据域，p->next表示p所指结点中的指针域，若非空，则指向其"后继"结点。第四十九页，共九十九页，编辑于2023年，星期三指针型变量只能作同类型的指针赋值与比较操作。并且，指针型变量的"值"除了由同类型的指针变量赋值得到外，都必须用C语言中的动态分配函数得到。例如，p=newLNode;表示在运行时刻系统动态生成了一个LNode类型的结点，并令指针p"指向"该结点。反之，当指针p所指结点不再使用，可用deletep;释放此结点空间。第五十页，共九十九页，编辑于2023年，星期三2.3.2单链表中基本操作的实现

以下重点讨论线性表的五个基本操作在链式存储结构中的实现。

一、初始化操作

根据上一节的约定，初始化建一个空的链表即为建立一个只有头结点的链表。算法2.13voidInitList(SLink&L){

//创建一个带头结点的空链表,L为指向头结点的指针

L=newLNode;

if(!L)exit(1);//存储空间分配失败

L->next=NULL;}//nitList

算法的时间复杂度为O(1)。第五十一页，共九十九页，编辑于2023年，星期三二、销毁结构操作算法2.14voidDestroyList(SLink&L){

//销毁以L为头指针的单链表，释放链表中所有结点空间

while(L)

{

p=L;

L=L->next;

deletep;

}//while

L=NULL;}//DestroyList

算法的时间复杂度为O(Listlength(L))。第五十二页，共九十九页，编辑于2023年，星期三三、存取元素操作

单链表是一种“顺序存取”的结构，即：为取第i元素，首先必须先找到第i-1个元素。因此不论i值为多少，都必须从头结点开始起“点数“，直数到第i个为止。头结点可看成是第0个结点。第五十三页，共九十九页，编辑于2023年，星期三算法2.15boolGetElem(SLinkL,intpos,ElemType&e){//若1≤pos≤LengthList(L)，则用e带回指针L指向头结点的单链表//中第pos个元素的值且返回函数值为TRUE,否则返回函数值为FALSE

p=L->next;j=1;//变量初始化，p指向第一个结点

while(p&&j<pos)

{//顺结点的指针向后查找，直至p指到第pos个结点或p为空止

p=p->next;++j;

}//while

if(!p||j>pos)returnFALSE;//链表中不存在第pos个结点

e=p->data;//取到第pos个元素

returnTRUE;

}//GetElem

算法的时间复杂度为O(ListLength(L))。第五十四页，共九十九页，编辑于2023年，星期三四、插入元素操作

前面已经分析过，在线性表中“插入”一个元素时，使元素之间的关系<ai-1,ai>改变为<ai-1,e>和<e,ai>。当用指针指示后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可。因为新的元素插入在线性表的第i个元素之前，使得ai不再是ai-1的后继，而是新的元素e的后继，因此需要修改元素e和元素ai-1所在结点的指针。

由此，算法的基本思想就是，首先找到第i-1个结点，然后修改相应指针。第五十五页，共九十九页，编辑于2023年，星期三算法2.16boolListInsert(SLink&L,intpos,ElemTypee){

//若1≤pos≤LengthList(L)+1，则在指针L指向头结点的单链表

//的第pos个元素之前插入新的元素e，且返回函数值为TRUE,

//否则不进行插入且返回函数值为FALSE

p=L;j=0;

while(p&&j<pos-1)

{//查找第pos-1个结点，并令指针p指向该结点

p=p->next;++j;

}//while

if(!p||j>pos-1)

returnFALSE;//参数不合法，pos小于1或者大于表长+1

s=newLNode;

if(!s)exit(1);//存储空间分配失败

s->data=e;//创建新元素的结点

s->next=p->next;p->next=s;//修改指针

returnTRUE;

}//ListInsert算法时间复杂度为O(ListLength(L))。第五十六页，共九十九页，编辑于2023年，星期三五、删除元素操作

和插入类似，由于删除元素ai改变了元素之间的关系，使ai+1不再是ai的后继，而是ai-1的后继，因此需要修改元素ai-1所在结点的指针。因此在单链表中删除元素操作的算法基本思想和插入相同，也是：首先找到第i-1个结点，然后修改相应指针。第五十七页，共九十九页，编辑于2023年，星期三算法2.17boolListDelete(SLink&L,intpos,ElemType&e){

//若1≤pos≤LengthList(L)，则删除指针L指向头结点的单链表

//中第pos个元素并以e带回其值，返回函数值为TRUE，

//否则不进行删除操作且返回函数值为FALSE

p=L;j=0;

while(p->next&&j<i-1)

{//寻找第pos个结点，并令p指向其前驱

p=p->next;++j;

}

if(!(p->next)||j>i-1)

returnFALSE;//删除位置不合理

q=p->next;p->next=q->next;//修改指针

e=q->data;delete(q);//释放结点空间

returnTRUE;}//ListDelete_L算法时间复杂度为O(ListLength(L))。第五十八页，共九十九页，编辑于2023年，星期三2.3.3单链表其它算法举例

例2-7

逆序创建链表假设线性表(a1，a2，…，an)的数据元素存储在一维数组A[n]中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为"空"的链表中。第五十九页，共九十九页，编辑于2023年，星期三算法2.19voidCreateList_L(SLink&L,intn,ElemTypeA[]){

//已知数组A中存有线性表的n个数据元素，

//逆序建立带头结点的单链表。

L=newLNode;

if(!L)exit(1);//存储空间分配失败

L->next=NULL;//先建立一个带头结点的空的单链表

for(i=n;i>0;--i)

{p=newLNode;

if(!p)exit(1);//存储空间分配失败

p->data=A[i-1];//赋元素值

p->next=L->next;L->next=p;//插入在头结点之后

}//for

}//CreateList_L容易看出，算法的时间复杂度为O(ListLength(L))。第六十页，共九十九页，编辑于2023年，星期三例2-8以链表作存储结构解例2-5的问题，即将线性表(a1,a2,…,am,b1,b2,…,bn)改变成(b1,b2,…,bn,a1,a2,…,am)。

解题分析：

因为对链表来说，“插入”和“删除”仅需修改指针即可完成，并且由于前m个元素之间和后n个元素之间的链接关系分别都不需要改变，则算法的实际操作为：

第六十一页，共九十九页，编辑于2023年，星期三算法2.20

voidexchange_L(SLink&L，intm)

{

//本算法实现单链表中前m个结点和后n个结点的互换

if(m&&L->next)//链表不空且m!=0

{

p=L->next;k=1;

while(k<m&&p)//查找所在结点

{

p=p->next;++k;

}//while

if(p&&p->next)//n!=0时才需要修改指针

{

ha=L->next;//以指针ha记结点的位置

L->next=p->next;//将结点链接在头结点之后

p->next=NULL;//设的后继为空

q=L->next;//令q指向结点

while(q->next)q=q->next;//查找结点

q->next=ha;//将结点链接到结点之后

}//if(p)

}//if(m)

}//exchange_L

算法的时间复杂度为O(ListLength(L))。第六十二页，共九十九页，编辑于2023年，星期三例2-9

编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。

解题分析：

可以和顺序表采用同样算法，即设想新建一个链表，然后顺序考察原链表中每一个结点的数据元素，在"新表"中进行查找，如果有相同的则舍弃之，否则就插入到新表中。

第六十三页，共九十九页，编辑于2023年，星期三算法2.21

voidpurge_L(SLink&L)

{

//删除单链表L中的冗余元素，即使操作之后的单链表中只保留

//操作之前表中所有值都不相同的元素

p=L->next;

L->next=NULL;;//设新表为空表

while(p)//顺序考察原表中每个元素

{

succ=p->next;//记下结点*p的后继

q=L->next;//q指向新表的第一个结点

while(q&&p->data!=q->data)q=q->next;

//在新表中查询是否存在和p->data相同的元素

if(!q)//将结点*p插入到新的表中

{

p->next=L->next;

L->next=p;

}

elsedeletep;//释放结点*p

p=succ;

}//for

}//purge_L

此算法的时间复杂度为O(ListLength2(L))。第六十四页，共九十九页，编辑于2023年，星期三从以上对链表的各种操作的讨论可知，链式存储结构的优势在于：

(1)能有效利用存储空间；因为它是动态存储分配的结构，不需要预先为线性表分配足够大的空间，而是向系统"随用随取"，并且在删除元素时可同时释放空间。(2)用"指针"指示数据元素之间的后继关系，便于进行"插入"、"删除"等操作；而其劣势则是不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的"表长"和数据元素在线性表中的"位序"，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。第六十五页，共九十九页，编辑于2023年，星期三

为了更突出链表的优势，需改进单链表结构的定义。除了保留指向头结点的指针外，还应增设"尾指针"和"表长"两个属性，同时，我们从上面讨论的链表基本操作的实现算法中可以看出，在对链表进行操作时，经常需要一个指针在链表中巡游，由此可以设想，如果将这个在操作中进行巡游的"指针"以及它所指结点的数据元素在线性表中的"位序"纳入链表结构中，作为链表定义中的两个成员，必然会对链表的操作带来很多方便。

由此，在实际使用链表时需重新考虑链表结构的定义并重新设计操作界面。详细情况将留在2.5节进行讨论。第六十六页，共九十九页，编辑于2023年，星期三2.3.4循环链表

循环链表(CircularLinkedList)是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个自成循环的头结点表示。第六十七页，共九十九页，编辑于2023年，星期三

循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是"后继是否为空"，而是"后继是否为头结点"。第六十八页，共九十九页，编辑于2023年，星期三2.3.5双向链表

顾名思义，双向链表(DoubleLinkedList)的特点是其结点结构中含有两个指针域，其一指向数据元素的"直接后继"，另一指向数据元素的"直接前驱"，用C语言描述如下：

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLink;

第六十九页，共九十九页，编辑于2023年，星期三

与单链表类似，双向链表也是由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。空的双向循环链表则由只含一个自成双环的头结点表示。

第七十页，共九十九页，编辑于2023年，星期三2.3.5双向链表

在双向链表上进行操作基本上和单向链表相同，例如，查找结点也是要从头指针指示的头结点开始，但插入和删除时必须同时修改两个方向上的指针，它们的算法分别如下所示。

第七十一页，共九十九页，编辑于2023年，星期三算法2.22

voidListInsert_DuL(DuLink&L,DuLNode*p,DuLNode*s)

{

//在带头结点的双向循环链表L中结点*p之后插入结点*s

s->next=p->next;p->next=s;

s->next->prior=s;s->prior=p;

}//ListInsert_DuL

第七十二页，共九十九页，编辑于2023年，星期三算法2.23

voidListDelete_DuL(DuLink&L,DuNode*p,ElemType&e)

{

//删除带头结点的双向循环链表L中结点*p的后继，

//并以e返回它的数据元素

q=p->next;e=q->data;

p->next=q->next;

p->next->prior=p;

deleteq;

}//ListDelete_DuL第七十三页，共九十九页，编辑于2023年，星期三2.4.1有序表的定义

若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即ai≥ai-1或ai≤ai-1(i=2,3,…,n)，则称该线性表为有序表(OrderedList)。

有序表的"有序"特性可以给某些操作带来很大方便，在某些应用问题中，如果用有序表而不是线性表将使算法的时间复杂度下降。第七十四页，共九十九页，编辑于2023年，星期三例2-10

编写算法删除有序顺序表中“多余”的数据元素，即使操作之后的有序顺序表中所有元素的值都不相同。

算法2.24

voidpurge_OL(SqList&L)

{

//删除有序顺序表L中的冗余元素，即使操作之后的有序顺序表中

//只保留操作之前表中所有值都不相同的元素

k=-1;//k指示新表的表尾

for(i=0;i<L.length-1;++i)//顺序考察表中每个元素

{

if(k==-1||L.elem[k]!=L.elem[i])

L.elem[++k]=L.elem[i];//在新表中不存在和L.elem[i]相同的元素

}//for

L.length=k+1;//修改表长

}//purge_OL

显然，此算法的时间复杂度为O(ListLength(L))。第七十五页，共九十九页，编辑于2023年，星期三2.4.1有序表的定义

例2-11

已知两个链表（头指针分别为La和Lb）中的数据元素均自小至大有序，编写算法将这两个链表归并为一个链表。第七十六页，共九十九页，编辑于2023年，星期三算法2.25

voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)

{

//已知单链线性表La和Lb的元素按值非递减排列。本算法

//归并La和Lb得到新的单链线性表Lc，Lc的元素也按

//值非递减排列。操作之后La和Lb消失

pa=La->next;pb=Lb->next;

Lc=rc=newLNode;//建空表，Lc为头指针while(pa&&pb)

{

if(pa->data<=pb->data)

{//将*pa插入Lc表，指针pa后移

rc->next=pa;rc=pa;pa=pa->next;

}//if

else

{//将*pb插入Lc表，指针pb后移

rc->next=pb;rc=pb;pb=pb->next;

}//else

}//whilerc->next=pa?pa:pb;//插入剩余段

delete(La);delete(Lb);//释放La和Lb的头结点

}//MergeList_L

显然，此算法的时间复杂度为O(ListLength(La)+ListLength(Lb))。第七十七页，共九十九页，编辑于2023年，星期三2.4.2有序表的基本操作

有序表类型的基本操作和线性表类型中定义的基本操作基本相同，但由于LocateElem中函数参数compare的类型不同，（在有序表中，元素相互比较的结果将产生三种结果："小于"、"等于"和"大于"），则该函数的定义和实现的算法也就和线性表中的不同。

LocateElem(L,e,&q,int(*compare)(ElemType,ElemType))

初始条件：有序表L已存在，compare为有序判定函数。

操作结果：若有序表L中存在元素e，则q指示L中第一个值为e的元素的位置，并返回函数值TRUE；否则q指示第一个大于e的元素的前驱的位置，并返回函数值FALSE。

此外，在有序表中进行"插入"操作时必须保持表的有序性。也就是说，在有序表中进行插入时首先要查找插入位置，显然，上述函数返回的位置即为插入位置，即应插入在q指示的元素之后。第七十八页，共九十九页，编辑于2023年，星期三2.5.1有序链表类型

//结构定义

typedef

structLNode{//结点结构

ElemTypedata;

structLNode*next;

}

*SLink;

typedef

struct

{//链表结构

SLinkhead,//指向有序链表中的头结点

tail,//指向有序链表中最后一个结点

curPtr;//指向操作的当前结点，称为“当前指针”

intlength,//指示有序链表的长度

curPos;//指示当前指针所指结点的位序

}

OrderedLinkList;第七十九页，共九十九页，编辑于2023年，星期三//基本操作接口(函数声明)

boolMakeNode(SLink&p,ElemTypee);

//生成一个数据元素和e相同的新结点*p，并返回TRUE,若存储分配失败，

//则返回

FALSE。

boolInitList(OrderedLinkList&L);

//构造一个空的有序链表L，若存储分配失败，令L.head为空并返回FALSE，

//否则返回TRUE。

voidDestroyList(OrderedLinkList&L);

//销毁有序链表L，L不再存在。

boolListEmpty(OrderedLinkListL);

//若有序链表L为空表，则返回TRUE，否则返回FALSE。第八十页，共九十九页，编辑于2023年，星期三

intListLength(OrderedLinkListL);

//返回有序链表L中元素个数。

SLinkPriorPos(OrderedLinkListL);

//移动有序链表L中当前指针到它当前所指结点的直接前驱并返回。

SLinkNextPos(OrderedLinkListL);

//移动有序链表L中当前指针到它当前所指结点的直接后继并返回。

boolGetPos(OrderedLinkListL,intpos);

//若1≤pos≤LengthList(L)，则移动当前指针指向第pos个结点

//且返回函数值为TRUE，否则不移动当前指针且返回函数值为FALSE。第八十一页，共九十九页，编辑于2023年，星期三

voidGetCurElem(OrderedLinkListL,ElemType&e);

//以e带回当前指针所指结点中的数据元素。

boolLocateElem(OrderedLinkListL,ElemTypee,

int(*compare)(ElemType,ElemType));

//若有序链表L中存在和e相同的数据元素,则当前指针指向第1个和e相同的结点，

//并返回TRUE，否则当前指针指向第一个大于e的元素的前驱，并返回FALSE。

voidListTraverse(LinkListL,void(*visit)());

//依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。

voidClearList(LinkList&L);

//将有序链表L重置为空表，并释放原链表的结点空间。第八十二页，共九十九页，编辑于2023年，星期三

voidSetcurElem(LinkListL,ElemTypee);

//将有序链表L中当前指针所指结点中的数据元素修改为和e相同。

voidInsAfter(LinkList&L,SLinks);

//在有序链表L中当前指针所指结点之后插入一个新的结点*s

//并移动当前指针指向新插入的结点。

boolDelAfter(LinkList&L,ElemType&e);

//若当前指针所指非单链表L中最后一个结点，则删除当前指针所指结点之后的

//结点,以e带回它的数据元素并返回TRUE,否则不进行删除操作且返回FALSE。第八十三页，共九十九页，编辑于2023年，星期三其中部分操作的伪码算法如下：

boolMakeNode(SLink&p,ElemTypee)

{

//生成一个数据元素和e相同的新结点*p，并返回TRUE，

//若存储分配失败，则返回FALSE。

p=newLNode;

if(!p)returnFALSE;

p->data=e;p->next=NULL;

re