数据结构(C语言版)-第2章-线性表课件

数据结构(C语言版)第2章线性表数据结构(C语言版)第2章线性表数据结构(C语言版)第2章线性表线性结构的特点：除第一个之外的数据元素均只有一个前驱;存在唯一的一个被称作“第一个”的数据元素;除最后一个之外的数据元素均只有一个后继。数据元素的非空有限集存在唯一的一个被称作“最后一个”的数据元素;例：“第一个”数据元素“最后一个”数据元素直接前驱直接后继2.1线性表的类型定义线性结构的特点：除第一个之外的数据元素均只有一个前驱;存在唯一的一个被称作“第一个”的数据元素;除最后一个之外的数据元素均只有一个后继。数据元素的非空有限集存在唯一的一个被称作“最后一个”的数据元素;

姓名学号

张三790631

李四790631王五790631赵六790634钱七790635

孙八790800例：“第一个”数据元素“最后一个”数据元素直接前驱直接后继2.1线性表的类型定义线性表(Linear_List)：由n(n0)个数据元素a1,a2,…,an

组成的

有限并且有序的序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表。

非空的线性表(n>0)常记作：(a1,a2,…,ai-1,ai,ai+1,…,an)例1：26个英文字母组成的字母表：（A,B,C,…,Z）例2：某校从1978年到1983年各种型号的计算机拥有量的变化情况：（6,17,28,50,92,188）数据元素为数字i为数据元素ai

的位序。这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。数据元素为字符指线性表中的每一个元素都有自己的位置（position）。例3：学生健康情况登记表：姓名学号性别年龄健康情况王小林790631男18健康陈红790632女20一般刘建平790633男21健康张立立790634男17神经衰弱……..……..…….…….…….数据元素(结点、记录)由5个数据项(字段、域)组成。文件(file)线性表中的数据元素可以是各种各样的，但同一线性表中的元素必定具有相同特性（属于同一数据对象）。线性表中的数据元素之间存在着序偶关系<ai–1,ai>。从以上例子可看出线性表（非空）的逻辑特征是：1、有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2，a1叫表头元素；2、有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1，an

叫表尾元素；3、其余的内部结点ai(2

i

n-1)都有且仅有一个直接前趋ai–1和一个直接后继ai+1。ADTList{抽象数据类型线性表的定义：参看P19。

数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：（线性表的基本操作很多，为讨论方便起见，在此将它归为四类。）

{结构初始化

}任何数据结构在被使用之前都必须进行“初始化”，它类似于编程中使用的变量都必须先有定义。

InitList(&L)

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

}

任何数据结构不再使用时都必须进行“结构销毁”，其实质为“释放”它所占有的存储空间。DestroyList(&L)

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

操作结果：销毁线性表L。{引用型操作}

ListEmpty(L)

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

操作结果：若L为空表，则返回TRUE，否则返回FALSE。操作的结果不改变线性表中的数据元素，也不改变数据元素之间的关系。ListLength(L)

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

操作结果：返回L中元素个数。若cur_e是线性表L中第一个数据元素，则它的前驱pre_e为“空元素”。NextElem(L,cur_e,&next_e)

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

操作结果：若cur_e是L中的数据元素，则用next_e返回它的后继，否则操作失败，next_e无定义。PriorElem(L,cur_e,&pre_e)

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

操作结果：若cur_e是L中的数据元素，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。若cur_e是线性表L中最后一个数据元素，则它的后继next_e为“空元素”。GetElem(L,i,&e)

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

操作结果：用e返回L中第i个元素的值。此操作通常称为“定位函数”，这是一种广义的定位函数写法，以compare()作为判定的条件，参数e和线性表中数据元素具有相同类型。较多场合是以“相等”作为判定条件，此时可省略函数参数，且操作结果为：若线性表中存在与e值相同的数据元素，则返回第一个这样的元素在表中的位序，否则返回函数值为0。LocateElem(L,e,compare())

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

操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回0。ListTraverse(L,visit())

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

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

一旦visit()失败，则操作失败。visit()亦为函数参数，常见的情况是“依次输出表中元素的值”，同样在这种情况下，通常的写法也是省略函数参数。{加工型操作}操作的结果或修改表中的数据元素，或修改元素之间的关系ClearList(&L)

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

操作结果：将L重置为空表。在对线性表L进行ClearList(L)操作之后，仅是删除表中所有元素，在以后的程序中仍可对它进行某些“合法”操作，如判空、插入等。但在进行了DestroyList(L)操作之后，线性表

L不再存在，即不能在以后的程序中再引用它。PutElem(&L,i,e)

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

操作结果：L中第i个元素赋值为e的值。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▲上述各个操作目前还无法在程序设计中加以引用。但如果已经实现了上述定义的线性表类型，那么在应用问题的求解中就可以用这些操作实现应用问题的算法设计。注例2-1：已知集合A和B，求这两个集合的并集，使A＝A∪B，且B不再单独存在。要在计算机中求解，首先要确定“如何表示集合”。用线性表表示集合以线性表LA和LB分别表示集合A和B，两个线性表的数据元素分别为集合A和B中的成员。

由此，上述集合求并的问题便可演绎为：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。思路：

1．逐一从LB中取出一个数据元素；

2．依值在LA中进行查询；

3.若不存在，则插入之。重复上述三步直至LB中的数据元素取完为止。

ListInsert(&LA,n+1,e)GetElem(LB,i,&e)LocateElem(LA,e,equal())其中的每一步能否利用线性表类型中定义的基本操作来完成呢？

voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度

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

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

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

ListInsert(&La,++La_len,e);//La中不存在和e相同的数据元素，则插入之

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

}//union执行时间与表长无关执行时间与表长成正比时间复杂度：O(ListLength(La)ListLength(Lb))算法2.1

例2-2：归并两个“其数据元素按值非递减有序排列的”线性表La和Lb，求得线性表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)思路：

1．分别从La和Lb中取得当前元素ai和bj；

2．若ai

bj，则将ai插入到Lc中，否则将bj插入到Lc中。voidMergeList(ListLa,ListLb,List&Lc){InitList(&Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i

La_len)&&(j

Lb_len)){//La和Lb均未取完GetElem(La,i,ai

);GetElem(Lb,j,bj

);if(ai

bj

){ListInsert(Lc,++k,ai

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

);++j;}}while(iLa_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(jLb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}执行时间与表长无关时间复杂度：O(ListLength(La)+ListLength(Lb))算法2.2

在实际的程序设计中要引用线性表的基本操作，必须先实现线性表类型。确定存储结构实现基本操作▲2.2线性表的顺序表示和实现

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构或顺序映象。用这种方法存储的线性表称作顺序表。

例如：线性表(1,2,3,4,5,6)的存储结构：123456是一个典型的线形表顺序存储结构。不是一个线形表顺序存储结构。123456依次存储，地址连续——中间没有空出存储单元。存储结构：地址不连续——中间存在空的存储单元。顺序表中元素存储位置的计算：

假设线性表的每个元素需占l个存储单元，则第i+1个数据元素的存储位置和第i个数据元素的存储位置之间满足关系：

LOC(ai+1)=LOC(ai)+l由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到：

LOC(ai)=LOC(a1)+(i-1)l线性表的第1个数据元素a1

的存储位置，称作线性表的起始位置或基地址。基地址基地址a1

a2…ai-1

aiai+1

…an线性表顺序存储结构的图示：存储地址内存状态数据元素在线性表中的位序a1a2ai

an

…

…

LOC(a1)LOC(a1)+l

LOC(a1)+(i-1)l

…

…

LOC(a1)+(n-1)l

1

2

i

n

…

…

顺序表的特点：以物理位置相邻表示逻辑关系。任一元素均可随机存取。（优点）LOC(a1)+nl

LOC(a1)+(maxlen-1)l

空闲顺序表在机器内存中的物理状态本课程在高级语

言层次讨论数据结构的实现方法需用高级语言已经实现的数据类型描述存储结构用一维数组表示顺序表类型相同用一变量表示顺序表的长度属性线性表长可变（删除）顺序表（元素）地址连续随机存取依次存放数组（元素）数组长度不可动态定义#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量

typedefstruct{

ElemTypeelem[LIST_INIT_SIZE];

intlength;//当前长度

}SqList;一维数组的定义方式：类型说明符数组名[常量表达式]说明：常量表达式中可以包含常量和符号常量，不能包含变量。即C不允许对数组的大小作动态定义。考虑到线性表因插入元素而使存储空间不足的问题，应允许数组容量进行动态扩充。

#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量

#defineLISTINCREMENT10//线性表存储空间的分配增量

typedefstruct{

ElemType*elem;//数组指针，指示线性表的基地址

intlength;//当前长度

intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)

}SqList;C语言中的数组下标从“0”开始，因此若L是Sqlist类型的顺序表，则表中第i个元素是L.elem[i-1]。注意StatusInitList_Sq(Sqlist&L){//构造一个空的顺序表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.lengh=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq初始化操作：为顺序表分配一预定义大小的数组空间，并将线性表的当前长度设为0。顺序表基本操作的实现77123456线性表的插入运算是指在表的第i(1i

n+1)个位置上，插入一个新结点b，使长度为n的线性表(a1,…,ai–1,ai,…,an)变成长度为n+1的线性表(a1,…,ai–1,b,ai,…,an)12345671234565671234567算法思想：

1）检查i值是否超出所允许的范围(1i

n+1)，若超出，则进行“超出范围”错误处理；

2）将线性表的第i个元素和它后面的所有元素均后移一个位置；

3）将新元素写入到空出的第i个位置上；

4）使线性表的长度增1。插入操作：StatusListInsert_Sq(SqList&L,inti,ElemTypee){

if(i<1||i>L.length+1)returnERROR;//插入位置不合法

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;//增加存储容量

}

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_sq算法2.4

▲插入算法的时间复杂度分析：

问题规模是表的长度，设它的值为n。算法的时间主要花费在向后移动元素的for循环语句上。该语句的循环次数为(n–i+1)。由此可看出，所需移动结点的次数不仅依赖于表的长度n，而且还与插入位置i有关。当插入位置在表尾(i=n+1)时，不需要移动任何元素；这是最好情况，其时间复杂度O(1)。当插入位置在表头(i=1)时，所有元素都要向后移动，循环语句执行n

次，这是最坏情况，其时间复杂度O(n)。算法的平均时间复杂度：设pi

为在第i

个元素之前插入一个元素的概率，则在长度为n

的线性表中插入一个元素时所需移动元素次数的期望值为

假设在表中任何位置(1

i

n+1)上插入结点的机会是均等的，则

由此可见，在顺序表上做插入运算，平均要移动表上一半元素。当表长n较大时，算法的效率相当低。算法的平均时间复杂度为O(n)。删除操作线性表的删除运算是指将表的第i(1i

n)个结点删除，使长度为n的线性表(a1,…,ai–1,ai,…,an)变成长度为n-1的线性表(a1,…,ai–1,ai+1,…,an)612345641234561算法思想：

1)检查i值是否超出所允许的范围(1i

n)，若超出，则进行“超出范围”错误处理；

2)将线性表的第i个元素后面的所有元素均前移一个位置；

3)使线性表的长度减1。6123455623456StatusListDelete_Sq(SqList&L,inti,ElemType&e){

if((i<1)||(i>L.length))returnERROR;//删除位置不合法

p=&(L.elem[i-1]);//p为被删除元素的位置

e=*p;//被删除元素的值赋给e

q=L.elem+L.length-1;//表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--L.length;//表长减1returnOK;}//ListInsert_sq算法2.5

删除算法的复杂度分析：

问题规模是表的长度，设它的值为n。算法的时间主要花费在向前移动元素的for循环语句上。该语句的循环次数为(n–i)。由此可看出，所需移动结点的次数不仅依赖于表的长度n，而且还与删除位置i有关。当删除位置在表尾(i=n)时，不需要移动任何元素；这是最好情况，其时间复杂度O(1)。当删除位置在表头(i=1)时，有n-1个元素要向前移动，循环语句执行n-1次，这是最坏情况，其时间复杂度O(n)。

算法的平均时间复杂度：设qi

为删除第i

个元素的概率，则在长度为n

的线性表中删除一个元素时所需移动元素次数的期望值为假设在表中任何位置(1

i

n)删除结点的机会是均等的，则由此可见，在顺序表上做删除运算，平均约要移动表上一半元素。当表长n较大时，算法的效率相当低。算法的平均时间复杂度为O(n)。2.3线性表的链式表示和实现

顺序表的特点：以物理位置相邻表示逻辑关系。任一元素均可随机存取。顺序表的优点：顺序表的缺点：进行插入和删除操作时，需移动大量的元素。为避免元素的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(LinkedList)。2.3.1线性链表链表的存储方式

用一组物理位置任意的存储单元来存放线性表的数据元素。

这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中元素的逻辑次序和物理次序不一定相同。链顺序表存储地址存储状态0031赵0033钱0035孙0037李0039周0041吴0043郑0045王链表存储地址存储状态0001李0007钱0013孙0019王0025吴0031赵0037郑0043周

004300130001NULL0037000700190025头指针H0031指针域数据域结点

指针链表

单链表

例：线性表：(赵，钱，孙，李，周，吴，郑，王）H赵钱孙李周吴郑王^单链表是由头指针唯一确定。单链表的表示

单链表在C语言中可用“结构指针”来描述：typedefstructLnode{//声明结点的类型和指向结点的指针类型ElemTypedata;//数据元素的类型structLnode*next;//指示结点地址的指针

}Lnode,*LinkList;

头结点：在单链表的第一个结点之前人为地附设的一个结点。数据域La1a2an^…L^头指针

头结点头指针存放头结点的地址。头结点不存放任何数据存放附加信息（链表的结点个数等）。指针域存放第一个结点的地址（若线性表为空表，则“空”，用^表示。）讨论1.在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。单链表的基本操作

1、查找运算按序号查找（GetElem(L,i,&e)在链表中的实现）在单链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，单链表是非随机存取的存储结构。StatusGetElem_L(LinkListL,inti,ElemType&e){

p=Lnext;j=1;//初始化，p指向第一个结点，j为计数器

while(p&&j<i){p=pnext;++j;

}

if(!p||j>i)returnERROR;//第i个元素不存在

e=pdata;//取第i个元素

returnOK;

}//GetElem_L算法2.8设单链表的长度为n，要查找表中第i个结点，仅当1i

n时，i的值是合法的。其算法如下：算法的时间复杂度为：O(n)按值查找

按值查找是在单链表中查找结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。其算法如下：StatusGetElem_L1(LinkListL1,ElemTypekey){p=L1next;while(p&&p

data!=key)

p=pnext;

returnp;

}//GetElem_L1▲该算法的执行时间与key有关，时间复杂度为：O(n)

2、插入运算（ListInsert(&L,i,e)在链表中的实现）

xssnext=p

next;pnext=s;pai

ai–12、生成一个数据域为x的新结点。1、首先找到ai-1的存储位置p。3、插入新结点：①、结点ai–1的指针域指向新结点。

②、新结点的指针域指向结点ai。步骤：×

StatusListInsert_L(LinkListL,inti,ElemTypee){

p=L;j=0;

while(p&&j<i-1)

{p=pnext;++j;}//寻找第i–1个结点

if(!p||j>i-1)returnERROR;//i

小于1或者大于表长+1

s=(LinkList)malloc(sizeof(LNode));//生成新结点

sdata=e;snext=pnext;//插入L中

pnext=s;returnOK;

}//LinstInsert_L算法2.9

时间复杂度：O(n)。3、删除运算（ListDelete(&L,i,&e)在链表中的实现）1、首先找到ai–1的存储位置p。pnext=p

nextnext;pai–1ai

ai+1步骤：2、令pnext指向ai+1。3、释放结点ai

的空间。StatusListDelete_L(LinkListL,inti,ElemType&e){

p=L;j=0;

while(pnext&&j<i–1){p=pnext;++j;

}

if(!(pnext)||j>i–1)returnERROR;//删除位置不合理

q=pnext;pnext=qnext;//删除并释放结点

e=qdata;free(q);

returnOK;

}//ListDelete_L算法2.10

时间复杂度为：O(n)在链表上实现插入和删除运算，无须移动结点，仅需修改指针。从一个空表开始，逐个将新结点插入到当前链表的表头上。4、建立单链表（头插法建表逆序建表）

voidCreateList_L(LinkList&L,intn){

//逆位序输入n个元素的值，建立带表头结点的单链线性表L。

L=(LinkList)malloc(sizeof(LNode));

Lnext=NULL;//先建立一个带头结点的单链表

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

p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf(&pdata);//输入元素值

pnext=Lnext;Lnext=p;//插入到表头}

}//CreateList_L算法的时间复杂度为：O(n)初始化如果是“顺序”创建单链表，那么算法该如何写呢？因为每个新生成的结点的插入位置在表尾，则算法中必须维持一个始终指向已建立的链表表尾的指针。算法2.11

voidTCreateList_L(LinkList&L,intn){

//顺序输入n个数据元素，建立带头结点的单链表}//TCreateList_LL=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的空单链表q=L;

//q始终指向表尾结点for(i=1;i≤n;++i){

p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);

//输入元素值

p->next=NULL;q->next=p;

//插入

q=p;

//q始终指向表尾结点}5单链表的合并

设有两个有序的单链表，它们的头指针分别是La、Lb，将它们合并为以Lc为头指针的有序链表。合并前的示意图如图2-4所示。15⋀图2-4

两个有序的单链表La，Lb的初始状态-249……

Lb

pb-7312……

23⋀La

Lcpapc合并了值为-7，-2的结点后示意图如图2-5所示。图2-5

合并了值为-7，-2的结点后的状态-249……

15⋀Lb

pcpbLc-7312……

23⋀La

pa算法说明

算法中pa，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。算法描述LNode*Merge_LinkList(LNode*La，LNode*Lb)/*合并以La,Lb为头结点的两个有序单链表*/{LNode*Lc,*pa,*pb,*pc,*ptr;Lc=La;pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}/*将pa所指的结点合并，pa指向下一个结点*/if(pa->data>pb->data){pc->next=pb;pc=pb;pb=pb->next;}/*将pb所指的结点合并，pb指向下一个结点*/if(pa->data==pb->data){pc->next=pa;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(ptr);}/*将pa所指的结点合并，pb所指结点删除*/}if(pa!=NULL)pc->next=pa;elsepc->next=pb;/*将剩余的结点链上*/free(Lb);return(Lc);}算法分析若La，Lb两个链表的长度分别是m，n，则链表合并的时间复杂度为O(m+n)。需要探索的问题:静态链表是用什么方式表示元素间的关系？静态链表如何模拟链表的机制？包括：空间的分配、释放（回收）元素的查找、插入、删除等基本操作如何实现静态链表的操作性能如何？6.静态链表静态链表:用一维结构体数组描述单链表。其中 数组的元素由两个数据域组成，data和cur data用来存放数据， cur相当于单链表中的next指针，存放该元素的后继在数组中的下标 cur称为游标，因此，静态链表又叫游标实现法。数据元素:datacur数据域游标后继元素在数组中的下标静态链表的类型定义#defineMAXSIZE1000typedefstruct{ ElemTypedata; intcur;}component,SLinkList[MAXSIZE];

静态链表在使用中应该能“自动”找到空闲结点，实现元素的插入，在删除元素中可以将被删元素的空间进行收集。为了分辨数组中的空闲空间，将所有空闲空间（未使用的和被删元素空间）链接成一个备用链表。静态链表的实现:03Jerry5Kate0Rose6Alice1Bob8Jane2Adam0Henry70

40123456789备用链表头结点链表头结点

03Jerry5Kate0Rose6Alice1Bob8Jane2Adam0Henry70

40123456789备用链表头结点链表头结点6返回空闲结点的位置：3如何实现为新元素分配空间？intMalloc_SL(SLinkList&space){

//得到一个备用链表的下标，并且返回i=space[0].cur;//得到备用链表的第一个结点的下标if(i){//如果存在备用链表space[0].cur=space[i].cur;//备用链表头结点指向原备用链表的第二个结点的下标

//备用结点的第一个结点将被使用，于是备用结点下标往后一个结点移动

}returni;//返回新开辟结点的下标}静态链表的基本操作03Jerry5Kate0Rose6Alice1Bob8Jane2Adam0Henry70

40123456789备用链表头结点链表头结点如何释放无用结点空间？释放下标为5的结点35voidFree_SL(SLinkList&space,intk){

//将k下标的空闲结点回收到备用链表中去（成为备用链//表的首元结点）space[k].cur=space[0].cur;

//将之前的备用链表首元结点的下标存到space[k]的cur中

space[0].cur=k;

//备用链表的头结点指向新回收的结点}voidInitList_SL(SLinkList&L){

//构造空的静态链表L，表头为L的最后一个单元，其余单元形//成一个备用链表，表头为L[0]L[MAXSIZE-1].cur=0;for(i=0;i<MAXSIZE-2;++i){//其余单元链接成以L[0]为头结点//的备用链表L[i].cur=i+1;}L[MAXSIZE-2].cur=0;}

01234567890123456780intLocateElem_SL(SLinkListL,ElemTypee){//在静态链表L中查找第1个值为e的元素，若找到返回其位序，//否则返回0i=L[MAXSIZE-1].cur;//链表首元结点的位置while(i&&L[i].data!=e)i=L[i].cur;//沿着链（游标）寻找下一个结点returni;}StatusListInsert(SLinkList&L,inti,ElemTypee){

//在静态链表L的第i个元素前插入新元素ek=MAXSIZE-1;if(i<1||i>ListLength(L)+1)returnERROR;j=Malloc_SL(L);//为新元素分配空间if(j)//如果空间分配成功{L[j].data=e;for(m=1;m<i;++m)//得到第i-1个元素的下标k=L[k].cur;L[j].cur=L[k].cur;L[k].cur=j;

//将第i-1个元素的cur设置为新结点的下标，将新加结点的下标设置为之//前第i-1个元素存储的cur值returnOK;}returnERROR;}StatusListDelete(SLinkList&L,inti,ElemType&e){//删除静态链表中的第i个元素，并返回其值

if(i<1||i>ListLength(L))returnERROR;k=MAXSIZE-1;for(j=1;j<i;++j)//找到第i-1个元素（下标存入k中）k=L[k].cur;j=L[k].cur;//找到待删除元素（下标存入j中）L[k].cur=L[j].cur;//将第i-1个元素的cur值置为待删元素的后继

Free_SL(L,j);//释放需删除的元素returnOK;}静态链表的特点后继结点的位置信息结点空间生成释放结点插入、删除结点单链表next，为指针类型malloc()free()修改指针静态链表cur，为基本整型静态数组自己管理操作备用链表、链表2.3.2循环链表循环链表：是一种头尾相接的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。优点：从表中任一结点出发均可找到表中其他结点。

由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于头指针。

a1an…H非空表空表

H单链表

a1an…H非空表空表

H头指针表示单循环链表若在循环链表中设立尾指针而不设头指针，可使某些操作简化。

a1an…

R找a1的时间复杂度：O(1)找an的时间复杂度：O(n)尾指针表示单循环链表不方便

a1的存储位置是：Rnextnextan

的存储位置是：R时间复杂度：O(1)当线性表以上图的循环链表作存储结构时，此操作仅需改变两个指针即可。时间复杂度是

O(1)。

a1an…

…b1bm

BABnext=C

Anext=BnextnextC=Anext例：将两个线性表合并成一个线性表。仅需将一个表的表尾和另一个表的表头相接。AB

a1an…

b1bm…

ABA=B2.3.3双向链表

双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表。

为什么要讨论双向链表： →无指示前驱的指针域→找前驱结点难：

从表头出发查找。

即：查找某结点的前驱结点的执行时间为O(n)。

可用双向链表来克服单链表的这种缺点。单链表的结点→有指示后继的指针域→找后继结点方便；即：查找某结点的后继结点的执行时间为O(1)。双向链表的结构可定义如下：typedefstructDuLNode{Elemtypedata;structDuLNode*prior,*next;}DuLNode,*DuLinkList;和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点。空表

H

H

非空表结点结构priorelementnext双向链表结构的对称性（设指针p指向某一结点）：ppriornext=p=pnextprior在双向链表中有些操作(如：ListLength、GetElem等)，因仅涉及一个方向的指针，故它们的算法与线性链表的相同。但在插入、删除时，则需同时修改两个方向上的指针，两者的操作的时间复杂度均为O(n)。a

x

b

插入结点p删除结点pa

b

c

voidListInsert_DuL(DuLinkList&L,Inti,ElemTypee){//在带头结点的双向循环链表L中第i个位置之前插入元素e。

s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;

}//ListInsert_DuLa

e

b

插入结点psvoidListDelete_DuL(DuLink&L,Inti,ElemType&e){//删除带头结点的双向循环链表L的第i个元素，

//并用e返回。

e=p->data;

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

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

free(p);returnOK;

}//ListDelete_DuLa

b

c

删除结点p

链式存储结构的优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。

链式存储结