数据结构（思政版）课件 第2章 线性表

第2章线性表主讲教师:***时间:2025.07.01目录CONTENTS01线性表的类型定义02线性表的顺序存储结构及算法实现03线性表的链式存储结构及算法实现目录CONTENTS线性表的类型定义2.12.1.1线性表的概念、特点与逻辑结构线性表（表）：n（n≥0）个具有相同类型的数据元素的有限序列（a1,a2,…,ai,…,an）线性表的长度：线性表中数据元素的个数空表：长度等于零的线性表ai（1≤i≤n）称为数据元素下角标

i表示该元素在线性表中的位置或序号元素ai（1≤i≤n）只是一个抽象的符号，其具体含义在不同的情况下可以不同。2.1.1线性表的概念、特点与逻辑结构逻辑特征1.数据元素个数的有限性a1ai-1aiana22.数据元素类型的相同性3.数据元素类型的抽象性4.相邻数据元素的序偶关系，且a1无前驱，an无后继序偶：两个具有固定次序的元素组成的序列，记作<a，b>，且称a是b

的前驱，b是a

的后继L1=(1,3,5,7,9)L2=('a','e','i','o','u')L3=((Li,8,3),(Wang,7,4),(Zhang,5,5))数据元素的类型需要根据实际的具体问题而确定，在定义中是不具体的，而是抽象的2.1.1线性表的概念、特点与逻辑结构2025/8/116（A,B,C,D,……,Z）例2分析学生成绩表数据元素都是学生记录，

元素间关系是线性。同一线性表中的元素必定具有相同特性。数据元素都是字母，元素间关系是线性。例1

分析26个英文字母组成的英文表学号姓名数学/分语文/分英语/分20200701张三91958820200702李四75898020200703王五95888020200704赵六809085：：：

：：物理/分89669482：化学/分96908572：2.1.1线性表的概念、特点与逻辑结构思考题

列出几个你在现实生活中看见的线性表。2.1.2线性表的ADT定义ADTList{数据对象：D={ei|1≤i≤n，n≥0，ei为ElemType类型}基本运算}数据关系：R={<ei-1,ei>ei-1,ei£D,i=2,…,n}InitList（&L）：表的初始化，建一个空表DestroyList（&L）：销毁表，释放表所占用的存储空间ListEmpty（&L）：判断表是否为空ClearList（&L）：清空一个线性表DispList（L）：输出线性表GetElem（L，i，&e）：在表中取序号为i

的数据元素LocateElem（L，e）：在线性表中查找值等于e

的元素ListInsert（&L，i，e）：在表的第i

个位置处插入一个新元素eListDelete（&L，i，e）：删除表中的第i

个元素2.1.2线性表的ADT定义线性表中数据元素的类型可以为简单类型，也可以为复杂类型。许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一个程序。从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。030102线性表的顺序存储结构及其算法实现2.2使用数组存储，大小在程序运行期间固定。存储方式是按逻辑顺序依次存储数据元素。存储结构定义需指定数组大小。静态顺序表01增加表头结点，包含数组首地址、实际元素个数和数组大小。数组空间在程序执行过程中动态申请和释放。动态顺序表02优点是存储密度大、便于随机访问、存储实现简单。缺点是连续性、静态性和运算不方便性。适用于数据量基本不变、查找频繁的场景。特点032.2.1线性表的顺序存储结构2.2.1线性表的顺序存储结构typedefstruct{ElemType*elem;

//指向数据元素的基地址intlength;

//线性表的当前长度intListSize;//数组的大小}SeqList; //顺序表类型其中elem成员存放元素，length成员存放线性表的实际长度。动态顺序表类型定义说明：注意逻辑位序和物理位序相差1。这里，假设ElemType为char类型补充：C语言的动态分配函数（<stdlib.h>）malloc(m)开辟m字节长度的地址空间，并返回这段空间的首地址sizeof(x)计算变量x的长度。free(p)释放指针p所指变量的存储空间，即彻底删除一个变量补充：数组定义typedefstruct{ElemType*elem;intlength;}SqList//顺序表类型typedefstruct{ElemTypeelem[MAXSIZE];intlength;}SqList//顺序表类型数组静态分配数组动态分配SqListL;L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);2.2.1线性表的顺序存储结构

有序顺序表的存储方式与顺序表类似，不同的是将数据元素按某个（或多个）数据项的值升序或降序排列。这种存储结构主要用于查找算法，可以提高查找算法的效率。有序顺序表通常采用数组来定义不需要增加头结点。有序顺序表2.2.2顺序表的基本运算的实现初始化基本操作插入删除创建查找154322.2.2顺序表的基本运算的实现1.初始化线性表InitList(L)

构造一个空的线性表L。实际上只需将length成员设置为0即可。void

InitList(SeqList&L){L.elem=(ElemType*)malloc(sizeofElemType)*Maxsize);

//分配存放线性表的顺序表空间

L.length=0;L.ListSize=MAXSIZE；

}2.2.2顺序表的基本运算的实现voidCreateList(SeqList&L，intn){intk=;InitList（L）；for（k=0;k<n;k++)scanf(&L.elem[k]);L.length=k;}2、创建顺序表初始化新表

逐个输入数据元素2.2.2顺序表的基本运算的实现voidCreateList(SqList&L，ElemTypea[]，intn){inti=0,k=0;L=(SqList*)malloc(sizeof(SqList));while(i<n) //i扫描a中元素{L->data[k]=a[i];k++;i++; //k记录插入到L中的元素个数}L->length=k;}2、创建顺序表a[0..n-1]

顺序表L─整体创建顺序表。传递顺序表指针2.2.2顺序表的基本运算的实现顺序表？？？L1010

顺序表指针的含义顺序表的空间顺序表LSeqList*L;L=(SeqList*)malloc(sizeof(SeqList));1010通过顺序表指针L操作顺序表算法参数说明2.2.2顺序表的基本运算的实现

顺序表指针引用voidCreateList(SqList*&L，ElemTypea[]，intn)引用参数：将执行结果回传给实参引用符号“&”放在形参L的前面。输出型参数均为使用“&”，不论参数值是否改变。2.2.2顺序表的基本运算的实现3.插入算法ListInsert(&L，i，x)在顺序表L的第i（1≤i≤ListLength(L)+1）个位置上插入新的元素x。

01i-1n-1nia1a2…aiai+1…anxi+1插入完成lengthnn+12.2.2顺序表的基本运算的实现boolListInsert(SeqList&L，inti，ElemTypex){intj;if(L.length==Maxsize||i<1||i>L.length+1)returnfalse; //参数错误时返回false

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

//将elem[i-1..n-1]元素后移一个位置

L.elem[j+1]=L.elem[j];L.elem[i-1]=x; //插入元素eL.length++; //顺序表长度增1returntrue; //成功插入返回true}插入算法如下：a1a2…ai…an…ai+1i2.2.2顺序表的基本运算的实现算法最好时间复杂度为O(1)算法最坏时间复杂度为O(n)当i=1时，移动次数为n，达到最大值。当i=n+1时，移动次数为0；

对于本算法来说，元素移动的次数不仅与表长L->length=n有关，而且与插入位置i有关：

2.2.2顺序表的基本运算的实现平均情况分析：

a1

a2

…

aiai+1

…

an

在线性表L中共有n+1个可以插入元素的地方因此插入算法的平均时间复杂度为O(n)。此时需要将ai～an的元素均后移一个位置，共移动n-i+1个元素。在长度为n的线性表中插入一个元素时所需移动元素的平均次数为：2.2.2顺序表的基本运算的实现4.删除算法ListDelete(L，i)删除顺序表L的第i（1≤i≤ListLength(L)）个元素。

0i-1n-1ia1a2ai+1…anaien-2an-1length删除完成nn-1…2.2.2顺序表的基本运算的实现boolListDelete(SeqList&L，inti，ElemType&e){intj;if(i<1||i>L.length)

//参数错误时返回falsereturnfalse;

e=L->data[i-1];for(j=i;j<=L.length-1;j++)

//将data[i..n-1]元素前移

L->elem[j-1]=L->elem[j];L->length--; //顺序表长度减1returntrue; //成功删除返回true}删除算法如下：a1a2…ai…an…ai+1ianai+12.2.2顺序表的基本运算的实现当i=n时，移动次数为0；当i=1时，移动次数为n-1。删除算法最好时间复杂度为O(1)删除算法最坏时间复杂度为O(n)对于本算法来说，元素移动的次数也与表长n和删除元素的位置i有关：2.2.2顺序表的基本运算的实现平均情况分析：a1

a2

…

ai

ai+1…

an

在删除元素ai时，若为等概率情况，则pi=在线性表L中共有n个可以删除元素的地方此时需要将ai+1～an的元素均前移一个位置，共移动n-(i+1)+1=n-i个元素。所以在长度为n的线性表中删除一个元素时所需移动元素的平均次数为：因此删除算法的平均时间复杂度为O(n)。2.2.2顺序表的基本运算的实现intLocateElem(SeqList*L，ElemTypex){inti=0;while(i<L.length&&L->elem[i]!=x)i++;if(i>=L.length)return0;elsereturni+1;}5.按元素值查找LocateElem(&L，x)

顺序查找第一个值域与x相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。平均时间复杂度为O(n)2.2.2顺序表的基本运算的实现boolGetElem(SqList*L，inti，ElemType&e){if(i<1||i>L->length)returnfalse;e=L.elem[i-1];returntrue;}

6.取第i个数据元素值GetElem(L，i，e)

返回L中第i（1≤i≤ListLength(L)）个元素的值，存放在e中。体现顺序表的随机存取特性本算法的时间复杂度为O(1)。2.2.2顺序表的基本运算的实现boolListEmpty(SeqList*L){return(L->length==0);}7.判定是否为空表ListEmpty(L)回一个值表示L是否为空表。若L为空表，则返回true，否则返回false。2.2.2顺序表的基本运算的实现intListLength(SqList*L){return(L.length);}8.求线性表的长度ListLength(L)返回顺序表L的长度。实际上只需返回length成员的值即可。2.2.2顺序表的基本运算的实现查找、插入、删除算法的平均时间复杂度为：O(n)显然，顺序表的空间复杂度S(n)=O(1)（没有占用辅助空间）。2.2.3顺序表的应用举例顺序表应用算法设计：

数据采用顺序表存储，利用顺序表的基本操作来完成求解任务。2.2.3顺序表的应用举例【例2.2】将两个有序表A和B，归并成一个有序顺序表voidMergeSqList(SeqListA，SeqListB，，SeqList&C){inti=j=k=0;C.elem=(ElemType*)malloc(sizeof(ElemType)*(A.length+B.length));while(i<A.length&&j<B.length)if(A.elem[i]<B.elem[j])C.elem[k++]=A.elem[i++];elseC.elem[k++]=B.elem[j++];两个有序表均没有遍历完2.2.3顺序表的应用举例while(i<A.length)C.elem[k++]=A.elem[i++];while(j<B.length)C.elem[k++]=B.elem[j++];C.length=kC.ListSize=C.length}本算法的时间复杂度为O(m+n)，空间复杂度为O(m+n)。2.2.3顺序表的应用举例【例2.3】求两个集合的并、交和差。（1）求A∪B的算法思想viodunion(SeqListA,B,&C){inti,j,k;c.elem=(ElemType*)malloc(sizeof(ElemType)*(A.length+B.length));for(i=0;i<A.length;i++)C[i]=A[i]k=A.length;for(j=0;j<B.length;j++

{i=0;while(i<A.length&&B[j]!=A[i])i++;

if(i>=A.length)C[k++]=B[j];}//endforC.lenght=k;C.ListSize=(A.length+B.length);}2.2.3顺序表的应用举例【例2.3】求两个集合的并、交和差。（2）求A∩B的算法viodintersection(SeqListA,B,&C){inti,j,k=0;C.elem=(ElemType*)malloc(sizeof(ElemType)*min(A.length,B.length));for(i=0;i<A.length;i++)//逐个取a中的元素

{j=0;while(j<B.length&&B[j]!=A[i])j++;//与b中的元素逐个比较

if(j<B.length)C[k++]=A[i];}C.lenght=k;C.ListSize=max(A.length,B.length);}2.2.3顺序表的应用举例【例2.3】求两个集合的并、交和差。（3）求A­-B的算法思想voiddifference(SeqListA,B,&C){inti,j,k=0;C.elem=(ElemType*)malloc(sizeof(ElemType)*max(A.length，B.length));for(i=0;i<A.length;i++)//逐个取a中的元素

{j=0;while(j<B.length&&B[j]!=A[i])j++;//与b中的元素逐个比较

if(j>=B.length)C[k++]=A[i];}//endforC.lenght=k;C.ListSize=max(A.length,B.length);}顺序表（顺序存储结构）的特点利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构一致。在访问线性表时，可以快速地计算出任何一个数据元素的存储地址。因此可以粗略地认为，访问每个元素所花时间相等。这种存取元素的方法被称为随机存取法。01OPTION02OPTION顺序表的优缺点时间：可以随机存取表中任一元素。空间：存储密度大（结点本身所占存储量/结点结构所占存储量）。优点：时间：在插入、删除某一元素时，需要移动大量元素。空间：浪费存储空间，属于静态存储形式，数据元素的个数不能

自由扩充。链表为克服这一缺点线性表的链式存储结构及其算法实现2.32.3.1单链表存储结构单链表：线性表的链接存储结构存储思想：用一组任意的存储单元存放线性表0200020803000325…………a1a2a3a4例：(a1,a2,a3,a4)的单链表存储0200

3250300∧存储特点：逻辑次序和物理次序不一定相同2.元素之间的逻辑关系用指针表示1.存储方式连续不连续零散分布2.3.1单链表存储结构0200020803000325…………a1a2a3a40200

3250300∧观察1：单链表由若干结点构成观察2：单链表的结点只有一个指针域结点数据域指针域datanext单链表的结点结构数据域data：存储数据元素指针域next：存储指向后继结点的地址1存储方式2.3.1单链表存储结构0200020803000325…………a1a2a3a40200

3250300∧头指针：指向第一个结点的存储地址尾标志：终端结点的指针域为空La1a2an∧非空表L=null空表空表和非空表不统一，有什么缺点？L1存储方式2.3.1单链表存储结构头指针：指向第一个结点的存储地址尾标志：终端结点的指针域为空La1a2an∧L∧非空表空表头结点简化了对边界的处理——插入、删除、构造等头结点：在第一个元素结点之前附设一个类型相同的结点2.3.1单链表存储结构typedefstructLNode{ElemTypedata;//数据域

structLNode*next;//指针域}LNode,*LinkList;//*LinkList为LNode类型的指针LNode*pLinkList

p2.存储结构定义2.3.1单链表存储结构LNode*p注意区分指针变量和结点变量两个不同的概念若p->data=ai,则p->next->data=ai+1指针变量p：表示结点地址结点变量*p：表示一个结点2.3.1单链表存储结构时间：插入、删除等操作不必移动数据，只需修改链接指针，修改

效率较高。空间：数据元素的个数可以自由扩充。优点：时间：存取效率不高，必须采用顺序存取，即存取数据元素时，只能按链表的顺序进行访问（顺藤摸瓜）。空间：存储密度小。缺点：3.存储结构的特点2.3.1单链表存储结构4.不带头结点的单链表表头之前插入结点（1）p->next=L;（2）L=p;2.3.1单链表存储结构4.不带头结点的单链表在表尾之后插入结点q->next=p;p->next=NULL;2.3.1单链表存储结构4.不带头结点的单链表在链表中间插入结点（1）p->next=q->next;（2）q->next=p;2.3.1单链表存储结构5.带头结点的单链表p->next=q->next;q->next=p;2.3.1单链表存储结构6．带结构信息的单链表typedefstructLNode{//定义单链表结点类型

ElemTypedata;structLNode*next;}LNode,*LinkList;typedefstructHNode{LinkListhead,rear;intlength;}HNode2.3.1单链表存储结构思考题：线性表的顺序存储结构和链式存储结构的差异？2.3.2单链表的基本运算1.初始化线性表InitList(&L)

该运算建立一个空的单链表，即创建一个头结点。voidInitList(LinkList&L){L=(LinkList*)malloc(sizeof(LNode));

//创建头结点

L->next=NULL;}∧L2.3.2单链表的基本运算从一个空表开始，创建一个头结点。依次输入数据元素，生成新结点将新结点插入到当前链表的表头上，直到结束为止。Lai-1a1…ais（1）头插法建表注意：链表的结点顺序与逻辑次序相反。2.创建单链表CreateList(&L)2.3.2单链表的基本运算void

CreateListF(LinkList&L){InitList(L)；//初始化为空表，

创建头结点，其next域置为NULLLNode*s;intx;//设数据元素的类型为intscanf(＂%d＂,&x);

头插法建表算法如下：∧L2.3.2单链表的基本运算while(x!=Minint){s=(LinkList)malloc(sizeof(LNode));//创建数据结点ss->data=x;s->next=L->next;L->next=s;//将s插在原开始结点之前，头结点之后scanf(＂%d＂,&x);}}Lai-1a1…aiss->next=L->next;L->next=s;2.3.2单链表的基本运算La1aj…aisr

（2）尾插法建表注意：链表的结点顺序与逻辑次序相同。从一个空表开始，创建一个头结点。依次输入数据元素，生成新结点将新结点插入到当前链表的表尾上，直到结束为止。增加一个尾指针r，使其始终指向当前链表的尾结点2.3.2单链表的基本运算voidCreateListR(LinkNode&L){InitList(L)；//初始化为空表Lnode*s,*r=L;//r始终指向尾结点，开始时指向头结点

intx;//设数据元素的类型为intscanf(＂%d＂,&x);

尾插法建表算法如下：∧Lr2.3.2单链表的基本运算while(x!=flag)//flag为输入结束标志

{s=（LinkList）malloc(sizeof(LNode));s->data=x;r->next=s;//将结点s插入结点r的后面

r=s;//r指向新的尾结点

scanf(＂%d＂,&x);}r->next=NULL;//对于非空表，最后结点的指针域放空指针

//尾结点next域置为NULL}rLa1ai-1…aisr->next=s2.3.2单链表的基本运算3.求线性表的长度ListLength(L)

返回单链表L中数据结点的个数。

intListLength(LinkList*L){

LNode*p=L;/*p指向头结点*/intj=0;//p指向头结点，j置为0（即头结点的序号为0）

初始时L∧…pj=02.3.2单链表的基本运算while(p->next){p=p->next;j++;}//p所指的是第j个结点

returnj;

//循环结束，p指向尾结点，其序号j为结点个数}循环结束时L∧pj为结点个数…2.3.2单链表的基本运算

（1）按序号查找GetElem(L，i，&e)

在单链表L中从头开始找到第i个结点，若存在第i个数据结点，则将其data域值赋给变量e。4.查找算法2.3.2单链表的基本运算boolGetElem(LinkList*L，inti，ElemType&e){intj=1;LinkNode*p=L->next; //p指向第一个数据元素结点，j置为1while(j<i&&p!=NULL)

{ j++; p=p->next;}找第i个结点p循环结束时Lean∧…i…p2.3.2单链表的基本运算if(!p||j>i) //不存在第i个数据结点，返回falsereturnfalse;else //存在第i个数据结点，返回true{e=p->data;returntrue;}}Lean∧…i…p算法的时间复杂度为O(n)

不具有随机存取特性2.3.2单链表的基本运算（2）按元素值查找LocateElem(L，x)

在单链表L中从头开始找第一个值域与x相等的结点，若存在这样的结点，则返回位置，否则返回0。

intLocateElem(LinkNode*L，ElemTypeX){inti=1;LinkNode*p=L->next; //p指向开始结点，i置为1while(p!=NULL&&p->data!=x){p=p->next; //查找data值为x的结点，其序号为ii++;}

循环结束时Lx∧…i…p2.3.2单链表的基本运算Lx∧…i…if(p==NULL) //不存在元素值为x的结点，返回0return(0);else //存在元素值为x的结点，返回其逻辑序号ireturn(i);}2.3.2单链表的基本运算5.插入算法（1）后插结点操作插入操作：将值为x的新结点s插入到p结点之后。特点：只需修改相关结点的指针域，不需要移动结点。2.3.2单链表的基本运算abx…p…s

s->next=p->next

p->next=s插入操作语句描述如下：

s->next=p->next;

p->next=s;单链表插入结点演示P结点next的修改尽可能放在后面执行2.3.2单链表的基本运算5.插入算法（2）前插结点操作插入操作：将值为x的新结点s插入到q结点之后。查找操作：查找p结点的前驱结点q。2.3.2单链表的基本运算插入算法ListInsert(&L，i，e)

先在单链表L中找到第i-1个结点p，若存在这样的结点，将值为x的结点结点s插入到其后。boolListInsert(LinkList&L，inti，ElemTypex){intj=0;LNode*p=L，*s; //p指向头结点，j置为0

if(i<=0)returnfalse;//参数i错误，返回falsewhile(j<i-1&&p!=NULL)

{ j++; p=p->next;}查找第i-1个结点L∧…i-1…p2.3.2单链表的基本运算if(p==NULL) //未找到第i-1个结点，返回falsereturnfalse;else //找到第i-1个结点p，插入新结点并返回true{ s=(LinkList*)malloc(sizeof(LNode)); s->data=x; //创建新结点s，其data域置为x s->next=p->next; //将s插入到p之后

p->next=s; returntrue;}}插入L∧…i-1…pes2.3.2单链表的基本运算abx…p…p->next=p->next->next删除操作语句描述如下：

p->next=p->next->next;单链表删除结点演示为了释放被删除结点，操作语句描述如下：

q=p->next;p->next=q->next;free(q);2.3.2单链表的基本运算6.删除算法（删除第i个结点）

先在单链表L中找到第i-1个结点q，若存在这样的结点，且也存在后继结点，则删除该后继结点。

boolListDelete(LinkNode*&L，inti，ElemType&e){intj=0;LNode*p=L，*q; //p指向头结点，j置为0if(i<=0)returnfalsewhile(j<i-1&&p!=NULL) //查找第i-1个结点

{ j++; p=p->next;}查找第i-1个结点L∧…i-1…p2.3.2单链表的基本运算if(p==NULL) //未找到第i-1个结点，返回false returnfalse;else //找到第i-1个结点p{s=p->next; //q指向第i个结点

if(s==NULL) //若不存在第i个结点，返回false returnfalse;e=s->data;p->next=s->next; //从单链表中删除q结点

free(s); //释放q结点

returntrue; //返回true表示成功删除第i个结点

}}删除第i个结点L∧…i-1…p2.3.2单链表的基本运算6.删除算法（删除值为x的结点）

先在单链表L中找到值为x结点p，若存在这样的结点，则删除该结点。

boolListDelete(LinkList&L，ElemType&e){LinkLists,p=L;while(p->next&&p->next->data!=x)p=p->next;//查找值为x的结点

if(!p){printf(＂结点不存在\n＂);returnfalse;}else{s=p->next;//s指向第i个结点

p->next=s->next;//从链表中删除

free(s);//释放*sreturntrue;}}查找值为x的结点L∧…x…p2.3.2单链表的基本运算7.归并算法ListMerge(L1,L2,&L)两个有序单链表L1和L2。设计一个算法，将它们合并成一个有序单链表L。二路归并示意图二路归并L1L2L2.3.2单链表的基本运算voidListMerge(LinkListL1,L2,&L)

{LinkListL,h1,h2,h;h1=L1->next;h2=L2->next;//初始化L=L1;h=L;while(h1&&h2)//从h1和h2选择较小者链接到*h后

if(h1->data<=h2->data){h->next=h1;h=h1;h1=h1->next;}//h1小，链接*h1else{h->next=h2;h=h2;h2=h2->next;}//h2小，链接*h2if(h1)h->next=h1;//链接h1的剩余部分if(h2)h->next=h2;//链接h2的剩余部分

}2.3.2单链表的基本运算8.逆置算法ListReverse(&L)

【例（补充）】假设有一个带头结点的单链表L=（a1，a2，…，an）。设计一个算法将所有结点逆置，即：

L=（an，an-1，…，a1）∧La1a2an∧…p头插法建表2.3.2单链表的基本运算8.逆置算法ListReverse(&L)voidReverse(LinkNode*&L){LinkNode*p=L->next，*q;L->next=NULL;

∧La1a2an∧…p将L拆分为两个部分2.3.2单链表的基本运算8逆置算法ListReverse(&L)while(p!=NULL){q=p->next; //临时保存p的后继结点p->next=L->next;

//将p结点采用头插法连接

L->next=p;p=q;}}∧La1a2an∧…p头插法建表2.3.3双向链表在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域和一个指向前驱结点的指针域

双链表。2.3.3双向链表为什么要讨论双向链表?p单链表：单链表的结点有指示直接后继的指针域找后继结点方便即：查找某结点的后继结点的执行时间为

O(1)双向链表：在单链表的每个结点里面再增加一个指向其直接前驱的指针域prior，使得链表中形成两个方向不同的链。没有指示之间前驱的指针域找前驱结点难，必须从表头指针出发即：查找某结点的前驱结点的执行时间为

O(n)2.3.3双向链表线性表(a1,a2,…,ai,…,an)映射逻辑结构存储结构a1an∧…L带头结点双链表示意图2.3.3双向链表从任一结点出发可以快速找到其前驱结点和后继结点；从任一结点出发可以访问其他结点。双链表的优点：a1an∧…L2.3.3双向链表typedefstructDLNode //双链表结点类型{ElemTypedata;structDLNode*prior，*next; //指向前驱、后继结点}DLNode，*DLinkList;

对于双链表，采用类似于单链表的类型定义，其结点类型DLinkList声明如下：2.3.3双向链表abc…ps操作语句：

s->prior=p->prior

p->prior->next=s

s->next=p

p->prior=s

在p结点之前插入结点s…（1）双链表插入结点操作插入完毕p结点next的修改尽可能放在后面执行2.3.3双向链表abcp操作语句：

p->prior->next=p->next；

p->next->prior=p>prior；

free(p)…

删除p结点（2）双链表删除结点操作删除完毕2.3.4循环链表循环链表是另一种形式的链式存储结构形式。

单循环链表：将表中尾结点的指针域改为指向表头结点，整个链表形成一个环。由此从表中任一结点出发均可找到链表中其他结点。双循环链表：形成两个环。结点类型与非循环单链表的相同结点类型与非循环双链表的相同2.3.4循环链表线性表(a1,a2,…,ai,…,an)映射逻辑结构存储结构a1a2an…L带头结点单循环链表示意图1、单循环链表2.3.4循环链表链表中没有空指针域p所指结点为尾结点的条件：p->next==L与非循环单链表相比，单循环链表：a1a2an…Lp1、单循环链表2.3.4循环链表

某线性表最常用的操作是在尾元素之后插入一个元素和删除第一个元素，故采用（）存储方式最节省运算时间。A.单链表B.仅有头结点指针的单循环链表C.双链表

D.仅有尾结点指针的单循环链表示例1、单循环链表