数据结构-线性表

数据结构第二章线性表内容提要线性表的类型定义2.1线性表的顺序表示和实现2.2线性表的链式表示和实现2.3基本要求（1）掌握线性表的逻辑结构。（2）掌握顺序存储结构的操作及其效率分析。（3）掌握链式存储结构的概念及操作。重点线性表的逻辑结构和存储结构，线性表在顺序结构和链式结构上实现基本操作的方法，从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合。

难点线性表在顺序结构和链式结构上基本操作的算法实现。

基本要求、重点、难点线性结构的基本特征为:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。

线性结构是一个数据元素的有序（次序）集线性表是一种最简单的线性结构。2.1线性表的类型定义比较典型的线性结构：线性表、栈、队列、串等。2.1线性表的类型定义

线性表(linear_list)是n个数据元素的有限序列，记作（a1,a2,…，ai-1，ai，ai+1，…，an）

其中：数据元素可以是各种类型（整、实、记录类型等）2.1线性表的类型定义

例如：英文字母表(‘A’,‘B’,…,‘Z’)就是一个简单的线性表，其中数据元素是单个英文字母。例如：一副扑克牌的点数（2，3，4…，J，Q，K，A），其中数据元素是每张牌的点数。例如：在较为复杂的线性表中，数据元素(dataelements)可以是由若干数据项组成的记录类型。2.1线性表的类型定义

线性表的数学模型（形式定义）

含有n个数据元素的线性表是一个数据结构

linear_list=（D,R）其中：D={ai|ai∈ElemType

，1≤i≤n，n≥0} R=｛<ai,ai+1>|1≤i≤n-1}

说明：（1）线性表的数据元素可以是各种类型（原子类型、结构类型）

typedef

int

ElemType;

typedefcharElemType

等（2）同一线性表中的数据元素必须具有相同的特性，属同一类型（3）关系R是一个有序偶对的集合，即对于非空的线性表（a1,a2,…，ai-1,ai,ai+1,…,an），ai-1

领先于ai，表示了数据元素之间的相邻关系，称ai-1

是ai的直接前驱，ai是ai-1的直接后继（4）n表示线性表中数据元素的个数，n=0时称为空表线性表的抽象数据类型定义如下：ADTList{

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

结构初始化操作结构销毁操作

引用型操作

加工型操作

}ADTList结构初始化操作

InitList(&L)

操作结果：构造一个空的线性表L。CreateList(&L,A[],n)

初始条件：A[]中存在线性表的n个数据元素。操作结果：构造一个含n个数据元素的线性表L。操作定义结构销毁操作DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。

操作定义ListEmpty(L)ListLength(L)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)

GetElem(L,i,&e)LocateElem(L,e,compare())ListTraverse(L,visit())引用型操作操作定义

ListEmpty(L)（线性表判空）初始条件：操作结果：线性表L已存在。若L为空表，则返回TRUE，否则FALSE。ListLength(L)（求线性表的长度）初始条件：操作结果：线性表L已存在。返回线性表L

中元素个数。操作定义

PriorElem(L,cur_e,&pre_e)（求前驱）初始条件：操作结果：线性表L已存在。若cur_e

是L中的元素，则以pre_e

带回它的前驱，否则操作失败，pre_e无定义。NextElem(L,cur_e,&next_e)（求后继）初始条件：操作结果：线性表L已存在。若cur_e是L中的元素，则以next_e带回它的后继，否则操作失败，next_e无定义。操作定义

GetElem(L,i,&e)（求线性表中某个元素）初始条件：操作结果：线性表L已存在以e

带回L

中第i

个数据元素值。LocateElem(L,e,compare())（定位函数）初始条件：操作结果：线性表L已存在,compare()为判定函数。返回L中第1个与e满足关系

compare()的元素的位序，若不存在这样的元素，则返回0。且1≤i≤LengthList(L)。操作定义

ListTraverse(L,visit())（遍历线性表）初始条件：操作结果：线性表L已存在,visit()为数据元素的访问函数。依次对L

的每个数据元素调用函数visit()，一旦visit()失败，则遍历操作失败。操作定义ClearList(&L)(线性表置空)ListInsert(&L,i,e) (插入数据元素)PutElem(&L,i,e) (改变数据元素的值)ListDelete(&L,i,&e)(删除数据元素)加工型操作操作定义

ClearList(&L)初始条件：操作结果：线性表L已存在。将L重置为空表。PutElem(&L,i,e)初始条件：操作结果：L中第i个元素赋值和e相同。线性表L已存在，且1≤i≤LengthList(L)。操作定义

ListInsert(&L,i,e)初始条件：操作结果：线性表L已存在在L的第i个元素之前插入新的元素e,L的长度增1。

ListDelete(&L,i,&e)初始条件：操作结果：线性表L已存在删除L中第i个元素，并以e带回其值,L的长度减1。,1≤i≤LengthList(L)+1。,1≤i≤LengthList(L)。操作定义

假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。例2-1

可利用上述定义的线性表实现其它更复杂的操作。

即要求对线性表作如下操作：

扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。操作示例（一）1．从线性表LB中依次察看每个数据元素;2．依值在线性表LA中进行查访;

3．若不存在，则插入之。GetElem(LB,i,&e)

LocateElem(LA,e,equal)

ListInsert(&LA,n+1,e)操作步骤：

GetElem(Lb,i,&e);

//取Lb中第i个数据元素赋给e

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

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之void

union(List

&La,ListLb){

La_len=ListLength(La);

//求线性表的长度

Lb_len=ListLength(Lb);

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

//union算法

已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。仍选用线性表表示集合。例

2-2从集合B

取出元素放入集合A要求集合A中同样元素不能有两个以上因此，算法的策略和例2-1相同.操作示例（二）void

union(List

&La,ListLb){

La_len=ListLength(La);Lb_len=ListLength(Lb);}

//union

GetElem(Lb,i,&e);//取Lb中第i个数据元素赋给e

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

ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之for(i=1;i<=Lb_len;i++){}InitList(La);//构造(空的)线性表LA算法例2-3

已知线性表LA和LB中的元素按值非降序排列,将LA和LB归并为一个新的线性表LC，且LC中的元素仍按非降序排列.

LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)

则

LC=(2,3,5,6,8,8,9,11,11,15,20)操作示例（三）算法思想设表LC是一个空表，为使LC也是非递减有序排列，设两个位置指针i、j分别指向表LA和LB中的元素，k指向LC中的元素

ijk

LA=(2,2,3)LB=(1,3,3,4)LC=（）(1)循比LA.list［i］>LB.list［j］:则先将LB.list［j］插入到表LC中环较LA.list［i］≤LB.list［j］:则先将LA.list［i］插入到表LC中

(2)直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表LC中

void

MergeList(ListLa,ListLb,List&Lc){

//本算法将非递减的有序表La和Lb归并为Lc}

//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{归并1}while(i<=La_len){归并2}//若La还有剩余元素while(j<=Lb_len){归并3}

//若Lb还有剩余元素InitList(Lc);//构造空的线性表Lci=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);算法归并1

GetElem(La,i,&ai);

GetElem(Lb,j,&bj);

if(ai<=bj){//将ai

插入到Lc

中

ListInsert(Lc,++k,ai);++i;} else{//将bj

插入到Lc

中

ListInsert(Lc,++k,bj);++j;}

GetElem(La,i++,&ai);

ListInsert(Lc,++k,ai);

GetElem(Lb,j++,&bj);

ListInsert(Lc,++k,bj);

归并2归并3算法（续）2.2线性表类型的实现顺序映象最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。顺序映象——

以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>。2.2线性表类型的实现顺序映象

线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。

采用顺序存储结构的线性表通常称为顺序表。

a1a2

…ai-1

ai

…an线性表的起始地址称作线性表的基地址以“存储位置相邻”表示有序对<ai-1，ai>

即：

LOC(ai)=LOC(ai-1)+l

（一个数据元素所占存储量）所有数据元素的存储位置均取决于第一个数据元素的存储位置。

LOC(ai)=

LOC(a1)+(i-1)×l

↑基地址2.2线性表类型的实现顺序映象图线性表的顺序存储结构示意图

lll2.2线性表类型的实现顺序映象顺序映像的C语言描述typedef

struct{

}SqList;#defineLIST_INIT_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量ElemType

*elem;//存储空间基址int

length;//当前长度int

listsize;//当前分配的存储容量

(以sizeof(ElemType)为单位)

顺序存储结构可以借助于高级程序设计语言中的一维数组来表示。线性表的顺序存储结构用C语言定义如下：Status

InitList_Sq(SqList

&L){

//构造一个空的线性表

}//InitList_Sq算法时间复杂度：O(1)L.elem=(ElemType*)malloc

(LIST_

INIT_SIZEsizeof

(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZEreturnOK;需要包含#include<malloc.h>需要包含#include<stdlib.h>线性表操作InitList的实现：23754138546217L.elemL.lengthL.listsizee=38pppppi12341850p可见，查询操作是将顺序表中的元素逐个和给定值e相比较。线性表操作LocateElem

的实现：

int

LocateElem_Sq(SqListL,ElemTypee,

Status(*compare)(ElemType,ElemType)){

//

在顺序表中查询第一个满足判定条件的数据元素，

//若存在，则返回它的位序，否则返回0}//LocateElem_Sqi=1;//i的初值为第1元素的位序p=L.elem;

//p的初值为第1元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;函数指针！线性表操作LocateElem

的实现：(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)a1a2

…ai-1

ai

…ana1a2

…ai-1

…aiean<ai-1,ai><ai-1,e>,<e,ai>表的长度增加线性表操作ListInsert的实现：算法分析:插入元素时，线性表的逻辑结构发生什么变化？

Status

ListInsert_Sq(SqList

&L,inti,ElemTypee){//

在顺序表L的第i个元素之前插入新的元素e,

//i的合法范围为1≤i≤L.length+1}

//ListInsert_Sq

算法时间复杂度为:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素右移*q=e;//插入e++L.length;//表长增1returnOK;……线性表操作ListInsert的实现：考虑移动元素的平均情况:

假设在第

i个元素之前插入的概率为，

则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：if(L.length>=L.listsize){//当前存储空间已满，增加分配

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存储容量}if(i<1||i>L.length+1)returnERROR;//

插入位置不合法2118307542568721183075例如：ListInsert_Sq(L,5,66)L.length-10pppq87564266q=&(L.elem[i-1]);//q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;p

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

ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的长度减少a1a2

…ai-1

ai

ai+1

…ana1a2

…ai-1

线性表操作ListDelete的实现：算法分析：删除元素时，线性表的逻辑结构发生什么变化？a1a2

…ai-1

ai

ai+1

…anStatus

ListDelete_Sq(SqList

&L,inti,ElemType

&e){}//ListDelete_Sqfor(++p;p<=q;++p)*(p-1)=*p;

//

被删除元素之后的元素左移--L.length;//表长减1算法时间复杂度为:

O(ListLength(L))p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//删除位置不合法考虑移动元素的平均情况:

假设删除第

i个元素的概率为

,则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：2118307542568721183075L.length-10pppq8756p=&(L.elem[i-1]);q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;例如：ListDelete_Sq(L,5,e)p大家来思考问题？？？问题：讨论顺序表的优缺点？回答：优点：顺序存储结构的线性表是可以随机存取其中的任意元素。缺点：（1）数据元素最大个数通常需预先确定，存储空间不便于扩充。（2）插入与删除运算的效率很低。46

练习一下吧…判断：1．线性表的逻辑顺序与存储顺序总是一致的。（）

2．顺序存储的线性表可以按序号随机存取。（）

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（）

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。（）

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（）

6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（）

小结

线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。但是，顺序存储结构也有一些不方便之处，主要表现在：（1）数据元素最大个数通常需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；（2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高；（3）存储空间不便于扩充。当为一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。2.3线性表类型的实现

链式映象2.3.1线性链表2.3.2循环链表2.3.3双向链表问题引入1.顺序存储结构通常需要在程序编译前就规定好数据元素的多少(即数组长度)，事先难估计，多了造成浪费存储空间，少了不够用；2.顺序存储结构在插入和删除运算中可能需要大量移动元素，降低程序执行效率。基于上述两点，需要引入链式存储结构。注意：与顺序存储结构的不同点是数据元素在内存中的位置不一定相邻，即每一个数据元素都有一个链接字段，用来存放下一个数据元素的地址，形成链表结构。1线性表的链式存储表示

采用一组任意的存储单元来存放线性表中的数据元素，这些存储单元可以是连续的，也可以是不连续的。数据元素间的逻辑关系通过附加信息－指针来描述。数据元素除了具有代表其本身信息的数据域外，还有一个用来指示逻辑关系的指针域。这样的存储结构称为结点。数据域data指针域next结点node2.3.1线性链表

以线性表中第一个数据元素的存储地址作为线性表的地址，称作线性表的头指针。

a1a2…...an^

有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空2.3.1线性链表链式存储通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起，称为线性表的链式存储表示。由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。头指针头指针何谓头指针、头结点和首元结点？头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。

单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域或空或存放表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点。

头指针头结点首元结点a1一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是31举例上例链表的结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②

有头结点答：1.在链表中设置头结点有什么好处？2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针^头指针头结点无头结点有头结点讨论：线性链表（单链表）：结点中只有一个指针域不带头结点的单链表，头指针指向第一个数据元素带头结点的单链表，头指针指向头结点，头结点的数据域为空，指针域为第一个数据元素的地址不带头结点的单链表为空表，则头指针为空，而带头结点的，则头结点的指针域为空2.3.1线性链表结点和单链表的C语言描述LinkListL；//L为单链表的头指针typedef

struct

LNode{

ElemType

data；/*结点的数据域*/

struct

LNode

*next；/*结点的指针域*/}LNode,*LinkList;若LNode*p，则p的含义是什么？若p的值非空，则表明p指向某个结点，p->data表示p所指结点中的数据域，p->next表示p所指结点中的指针域，若非空，则指向其"后继"结点。

线性链表是一种动态存储结构，所占用的存储空间是在程序的执行过程中得到的，当线性链表要增加一个结点时，向系统申请一个存储空间，删除结点时要将空间释放。LNode*p;p=(LNode*)malloc(sizeof(LNode));free(p);链表结点的申请与释放

1.线性链表的初始化

建立一个空的线性链表。对于带头结点的单链表，设定一个头指针指向头结点。并且设置头结点的指针域为空。voidInitList(LinkList&H){H=(LNode*)malloc(sizeof(LNode));/*申请一个头结点*/if(!H)returnERROR;/*申请失败*/H->next=NULL;/*头结点的指针域置空*/}单链表操作的实现LNode*create_list(intn){

LNode*head,*p,*q;

inti; p=(LNode*)malloc(sizeof(LNode));head=p;

for(i=1;i<=n,i++){

q=(LNode*)malloc(sizeof(LNode));

scanf(&q->data);q->next=NULL; p->next=q;p=q;}

return(head);}建立结点的算法2.建立有n个结点的单链表单链表操作的实现链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。void

ClearList(&L){ while(L->next){

p=L->next; L->next=p->next;

}}//ClearListfree(p);单链表操作的实现3.重新置单链表为一个空表从线性链表的第一个结点开始，依次查找是否存在与给定值相同的元素，若存在，返回OK,否则返回ERROR。int

Search_list(LinkListH,inte){

LinkListp; p=H->next;

while(p)

if(p->data==e)returnOK; elsep=p->next; returnERROR;}单链表操作的实现4.线性链表的查找5.单链表的插入在链表中插入一个元素的示意图如下：xsbapabp插入步骤（即核心语句）：Step1：s->next=p->next;Step2：p->next=s；p->nexts->next元素x结点应预先生成：S=(LinkList)malloc(m);S->data=x;单链表操作的实现StatusListInsert(LinkList&L,inti,ElemTypee)/*在单链表L的第i个位置上插入值为e的元素*/{ p=L;j=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p||j>i-1)returnERROR; s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->next=p->next; p->next=s; returnOK;}单链表结点插入的演示单链表操作的实现5.单链表的删除在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q=p->next;//保存b的指针，靠它才能指向cp->next=q->next;//a、c两结点相连free(q)；//删除b结点，彻底释放p->next思考：省略free(q)语句行不行？(p->next)->next××单链表操作的实现StatusListDelete(LinkList&L,inti,ElemType&e){ p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)returnERROR;q=p->next;p->next=q->next;e=q->data;free(q); returnOK;}单链表结点的删除演示单链表操作的实现算法要求：已知：线性表A、B，分别由单链表LA,LB

存储，其中数据元素按值非递减有序排列，要求：将A，B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表LC

存储。假设：A=（3，5，8，11），B=（2，6，8，9，11）预测：合并后C=（2,3,5,6,8,8,9,11，11）6.链表的归并单链表操作的实现用链表可表示为：3511/\8

La2611/\8

Lb92365

Lc8头结点单链表操作的实现算法分析：算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。单链表操作的实现La3

5

8

11^

Lb2

6

8

11^9

PaPbPaPbPa、Pb用于搜索La和Lb，

Pc指向新链表当前结点Lc

…

Pa3

PcPa5

Pc11^Pc2

PbPcPa单链表操作的实现

VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//按值排序的单链表LA,LB，归并为LC后也按值排序

free(Lb);//释放Lb的头结点}//MergeList_Lpc->next=pa?pa:pb;//插入剩余段

while(pa&&pb)//将pa、pb结点按大小依次插入C中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next}}pa=La-->next;pb=Lb-->next;Lc=pc=La；//初始化

单链表操作的实现单链表的特点

根据实际需求来分配存储空间；插入和删除不需要移动大量的数据元素；只需要修改相应的指针即可。适合存储结构多变或变化较大的情形。无法实现随机存取，每次的查找过程均需从头指针开始。

循环链表(CircularLinkedList)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称为循环单链表。为了使某些操作实现起来方便，在循环单链表中也可设置一个头结点。这样，空循环链表仅由一个自成循环的头结点表示。2.3.2循环链表

带头结点的循环单链表2.3.2循环链表单链表与循环链表的异同：

（1）操作基本相同

（2）差别：

a.查找单链表：从表头开始查表头结点O(1)

查表尾结点

O(n)

循环链表：从任一点出发均可

用尾指针表示查表尾O(1)rear

查表头O(1)rear->next

b.判定是否到链尾：单链表p->next==NULL

循环链表p->next==L

c.链表的合并2.3.2循环链表例有两个带头结点的循环单链表A、B，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为A。

算法思想1（无尾指针必需的方法）：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。a1a2a3……^nanb1b2b3……^bm

Bm

A

(1)p

(2)q

(3)

(4)2.3.2循环链表

采用上面的方法，需要遍历链表，找到表尾，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间是O(1)。a1a2a3……nanb1b2b3……bm

Bm

A

p(1)

(2)

释放（3）

(4)

A(5)2.3.2循环链表voidmerge（LinkList&A,LinkList&B){/*此算法将两个链表首尾连接起来*/

LNode*p;p=A->next;/*保存链表A的头结点地址*/A->next=B->next->next;/*链表B的开始结点链到链表A的终端结点之后*/

free(B->next);/*释放链表B的头结点*/B->next=p;/*链表A的头结点链到链表B的终端结点之后*/A=B;}2.3.2循环链表2.3.3双向链表

循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗费是O(n)。如果希望从表中快速确定某一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的指针域。这样形成的链表中就有两条方向不同的链，我们可称之为双(向)链表(DoubleLinkedList)。

data数据域双向链表结点结构：aiprior指向前驱

next

指向后继双链表的结构定义如下：typedef

struct

DuLNode{

ElemTypedata;

struct

DuLNode*prior

struct

DuLNode*next;}DuLNode,*DuLinkList;

由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。设指针p指向双链表中某一结点，则有下式成立：

p->prior->next=p=p->next->priorp2.3.2双向链表

1.双向链表的插入操作

双向链表插入操作

2.3.2双向链表

s=newLNo