《数据结构课件、代码》第2章线性表.ppt

《《数据结构课件、代码》第2章线性表.ppt》由会员分享，可在线阅读，更多相关《《数据结构课件、代码》第2章线性表.ppt（71页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章 线性表(二)张成文张成文北京邮电大学计算机学院北京邮电大学计算机学院主要内容2.7 2.7 线性表的链式存储结构表示线性表的链式存储结构表示2.8 2.8 单链表单链表2.9 2.9 循环链表循环链表2.10 2.10 双向链表双向链表2.112.11各种链式存储结构的比较各种链式存储结构的比较2.122.12顺序表与链表的比较顺序表与链表的比较 2.132.13小结小结线性表的链式存储结构表示结点结点(Node):既要存储线性表的每个既要存储线性表的每个数据元素值数据元素值,又要存储指示其后继结点的又要存储指示其后继结点的地址地址(或位置或位置)信息信息,以以表示结点间的逻辑关系。这

2、两部分信息组成的存表示结点间的逻辑关系。这两部分信息组成的存储映象叫做结点储映象叫做结点(Node)。1 线性表的链式存储结构表示让每个存储结点都包含两部分：让每个存储结点都包含两部分：数据域数据域和和指针域指针域指针指针数据数据指针指针数据数据指针指针或或样式：样式：数据域：数据域：存储存储元素的值元素的值指针域：指针域：存储直接后继或存储直接后继或直接前驱元素的存储地址直接前驱元素的存储地址设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率其其结结点点在在存存储储器器中中的的位位置置是是随随意意的的，即逻逻辑辑上相邻的数据元素在物理上不一定相邻。上相邻的数据元素在物理上不

3、一定相邻。如何实现？通过指针指针来实现！链式存储结构特点La1a2a3与链式存储有关的术语与链式存储有关的术语1）结点：）结点：数据元素的存储映像。由数据域和指针域数据元素的存储映像。由数据域和指针域两部分两部分组成；组成；2）链表：）链表：n n 个结点由个结点由指针链指针链组成一个链表。它是线性表的链式组成一个链表。它是线性表的链式存储映像存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。3）单链表、双向链表、循环链表）单链表、双向链表、循环链表：结点只有一个指针域的链表，称为结点只有一个指针域的链表，称为单链表单链表或或线性链表线性链表；有两个指针域（直接前驱和直接后继）的链表

4、，称为有两个指针域（直接前驱和直接后继）的链表，称为双双向向链链表表；首尾相接的链表称为首尾相接的链表称为循环链表循环链表。a1heada2an循环链表示意图：循环链表示意图：headhead4）头指针、头结点和首元结点的区别）头指针、头结点和首元结点的区别 示意图如下：示意图如下：头指针头指针头结点头结点首元结点首元结点a1heada2infoan头指针头指针是指向链表中第一个结点（或为头结点或为首元结是指向链表中第一个结点（或为头结点或为首元结点）的指针；点）的指针；头结点头结点是在链表的首元结点之前是在链表的首元结点之前附设附设的一个结点；数据域的一个结点；数据域内只放空表标志和表长等信

5、息，它不计入表长度。内只放空表标志和表长等信息，它不计入表长度。首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1的结点。的结点。下面举例说明。下面举例说明。头指针L头指针L头结点首元结点首元结点空表：L=NULLL 1264126440164016头结点的作用头结点的作用：插入和删除第一个数据元素时不必对头指针进行特殊处理。与链式存储有关的术语与链式存储有关的术语一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WA

6、NG），其存），其存储结构用储结构用单链表单链表表示如下，表示如下，请问其请问其头指针头指针的的值值是多少是多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例1：答：答：头指针头指针是指向链是指向链表中表中第一个第一个结点的指结点的指针，因此关键是要寻针，因此关键是要寻找找第一个结点第一个结点的的地址地址。7ZHAOH31称：头指针称：头指针H的值是的值是31例例例例2 2 2 2：线线性性表表具具有有两两种种存存储储方方式式，即即顺顺序序方方式式和和链链接接方方式式。现现有一个

7、具有五个元素的线性表有一个具有五个元素的线性表L=23L=23，1717，4747，0505，3131，若若它它以以链链接接方方式式存存储储在在下下列列100100119119号号地地址址空空间间中中，每每个个结结点点由数据（占由数据（占2 2个字节个字节）和指针（占）和指针（占2 2个字节个字节）组成，如下图所示。）组成，如下图所示。其其中中指指针针X X，Y Y，Z Z的的值值分分别别为为多多少少？该该线线性性表表的的首首结结点点起起始始地址地址为多少？为多少？末结点的起始地址末结点的起始地址为多少？为多少？Z Z47474747Y Y3131V V23232323X X1717U U05

8、05100100100100119119119119答：答：X=X=Y=Y=Z=Z=,首址首址=末址末址=.104104104104108108108108116116116116112112112112116116116116NULL/0NULL/0NULL/0NULL/0100100100100108108108108112112112112单链表 单链表单链表:链表中的每个结点只有一个指针域链表中的每个结点只有一个指针域,我们将这种链表称为单链表。我们将这种链表称为单链表。单链表包括单链表包括两个域两个域:数据域数据域用来存储结点的值用来存储结点的值;指针域指针域用来存储数据元素的直接后

9、继的地用来存储数据元素的直接后继的地址址(或位置或位置)。从链表的整体结构上看，链表可以是空链，也可以由一个或多个结点组成。每条链有一个入口的头结点，该结点仅指示链中第一个结点的地址。如是空链，则可表示为“0”或“”，它类似于一个常量。每条链的最后一个结点的链指针为“0”，也可用“”作为链的结束标志。下图给出了链表的示意形式。图(a)中有一个头结点和具有A、B、C、D数据元素的链，图(b)所示为线性链表的一般表示，结点与结点之间用箭头链接。单链表 链表图示(a)链表的图示；(b)链表的一般表示 以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。头结点头结点 a1 a2

10、.an 头指针头指针 有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。空指针线性表为空表时，头结点的指针域为空 讨论:链表的数据元素有两个域，不再是简单数据类链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。以要采用结构数据类型。答：答：以以2626个字母的链表为例，每个结点都有两个分量：个字母的链表为例，每个结点都有两个分量：字符型字符型指针型指针型假设每个结点用变量假设每个结点用变量nodenod

11、enodenode表示，结点表示，结点指针用指针用p p p p表示，其中两个分量分别用表示，其中两个分量分别用datadata和和*next*next表示，该如何书写？表示，该如何书写？p*next*nextdatadatanodenode方式方式1：直接表示为直接表示为 node.dataaa；node.next=q q方式方式2：p指向结点首地址，然后指向结点首地址，然后 p-data=aa;p-next=q q;方式方式3：p指向结点首地址，然后指向结点首地址，然后(*p).data=aa；(*p).nextq qaabq qp p单链表的存储结构描述typedef struct No

12、de typedef struct Node /结点类型定义结点类型定义 ElemType data ElemType data；struct Node *next struct Node *next；Node,*LinkListNode,*LinkList；/LinkList/LinkList为结构指针类型为结构指针类型设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址链表不具备的特点是链表不具备的特点是 。A A、可随机访问

13、任何一个元素、可随机访问任何一个元素 B B、插入、删除操作不需要移动元素、插入、删除操作不需要移动元素 C C、无需事先估计存储空间大小、无需事先估计存储空间大小 D D、所需存储空间与线性表长度成正比、所需存储空间与线性表长度成正比 静态链表静态链表 用数组模拟可利用空间表 0 1 2 3 4 5 6 7 8 9 3 8 1 -1 6 cur(游标)a2 a1 a4 a3 data#define MAXSIZE 10 /链表的最大长度typedef struct ElemType data;int cur;componet,SLinkListMAXSIZE;第第1 1个元素的下标：个元素的

14、下标：SLinkList0.cur SLinkList0.cur带头结点的单链表上的基本运算1 1 建立单链表建立单链表2 2 单链表查找单链表查找3 3 单链表插入单链表插入4 4 单链表删除第单链表删除第i i个结点个结点建立单链表1)头插法建表（逆序）头插法建表（逆序）操作步骤：操作步骤：建立一个建立一个“空表空表”；输入数据元素输入数据元素an，建立结点并插入；建立结点并插入；输入数据元素输入数据元素an-1，建立结点并插入；建立结点并插入；ananan-1依次类推，直至输入依次类推，直至输入a1为止。为止。ss头插法建表算法Linklist CreateFromHead()Linkl

15、ist CreateFromHead()LinkList L;Node*s;int flag=1;LinkList L;Node*s;int flag=1;/标志标志flagflag初值为初值为1 1 L=(Linklist)malloc(sizeof(Node);L=(Linklist)malloc(sizeof(Node);/分配头结点分配头结点 L-next=NULL;L-next=NULL;while(flag)while(flag)/输入输入“$”“$”时时,flag,flag置置0,0,建表结建表结束束 c=getchar();c=getchar();if(c!=$)if(c!=$

16、)/为新结点分配存储空间为新结点分配存储空间 s=(Node*)malloc(sizeof(Node);s-data=c;s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;s-next=L-next;L-next=s;/链接链接 else flag=0;else flag=0;return L return L；r c c1 1 s sLc cn n s srr 2)尾插法建表：设尾指针r建立一个建立一个“空表空表”,r 指向头结点指向头结点;输入数据元素输入数据元素C1,建立结点并链接建立结点并链接,r指向该结点；指向该

17、结点；输入数据元素输入数据元素C2,建立结点并建立结点并链接链接,r指向该结点；指向该结点；输入数据元素输入数据元素Cn,建立结点并建立结点并链接链接,r指向该结点；指向该结点；c c2 2 s sr 尾插法建表算法Linklist CreateFromTail()Linklist CreateFromTail()/新结点加到链表末尾新结点加到链表末尾 LinkList L;Node*r,*s;int flag=1;LinkList L;Node*r,*s;int flag=1;/flag/flag初值初值 L=(Node*)malloc(sizeof(Node);L=(Node*)mallo

18、c(sizeof(Node);/分配头结点分配头结点 L-next=NULL;r=L;L-next=NULL;r=L;/r/r始终指向链表的表尾始终指向链表的表尾 while(flag)while(flag)/输入输入“$”“$”时时flagflag为为0 0，建表结，建表结束束 c=getchar();c=getchar();if(c!=$)if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=sr-next=s;r=s /链接链接 else flag=0;

19、r-next=NULL;else flag=0;r-next=NULL;return L return L；单链表查找1)按序号查找按序号查找 算算法法描描述述：设设带带头头结结点点的的单单链链表表的的长长度度为为n,要要查查找找表表中中第第i个个结结点点,则则需需要要从从单单链链表表的的头头指指针针L出出发发,从从头头结结点点（L-next）开开始始顺顺着着链链域域扫扫描描,用用指指针针p指指向向当当前前扫扫描描到到的的结结点点,初初值值指指向向头头结结点点(p=L),用用j做做记记数数器器,累累计计当当前前扫扫描描过过的的结结点点数数(初初值值为为0),当当j=i 时时,指指针针p所所指指

20、的的结结点点就就是是要要找找的的第第i个个结结点点。算算法法实实现现,算法演示。算法演示。L 线性表的操作 Get(L,i)在单链表中i=3时,Get的实现过程:211830754256pppj1 2 3P-data=30 因此，查找第因此，查找第 i 个数据元素的基本个数据元素的基本操作为：操作为：移动指针，比较移动指针，比较 j 和和 i。令指针令指针 p 始终始终指向指向线性表中第线性表中第 j 个数据元素。个数据元素。单链表是一种单链表是一种顺序存取顺序存取的结构的结构,为为找第找第 i 个数据元素个数据元素,必须先找到第必须先找到第 i-1个个数据元素。数据元素。按序号查找算法实现/

21、找第找第i i个结点个结点,找到返回指向它的指针找到返回指向它的指针;否则返回空否则返回空Node*Get(LinkList L,int i)Node*Get(LinkList L,int i)Node *p Node *p；p=L p=L；j=0j=0；/从头结点开始扫描从头结点开始扫描 while(p-next!=NULL)&(jnext!=NULL)&(jnext p=p-next；j+j+；/扫描下一结点扫描下一结点 if if（i=ji=j）return preturn p；/找到了第找到了第i i个结点个结点 else return NULL else return NULL；/找

22、不到找不到,i0,i0或或inin 算法算法时间复杂度时间复杂度为为:O(Length(*L)2)2)按值查找按值查找算算法法描描述述：按按值值查查找找是是指指在在单单链链表表中中查查找找是是否否有有结结点点值值等等于于e e的的结结点点，若若有有的的话话，则则返返回回首首次次找找到到的的其其值值为为e e的的结结点点的的存存储储位位置置，否否则则返返回回NULLNULL。查查找找过过程程从从单单链链表表的的头头指指针针指指向向的的头头结结点点出出发发，顺顺着着链链逐逐个个将将结结点点的的值值和和给给定定值值e e作作比比较较。算算法法实实现现，算算法法演演示。示。按值查找算法实现/查找其结点

23、值等于查找其结点值等于keykey的结点，若找到则返回该结的结点，若找到则返回该结点的位置点的位置p p，否则返回，否则返回NULL*/NULL*/Node*Locate(LinkList L,ElemType key)Node*Locate(LinkList L,ElemType key)Node*p;Node*p;p=L-next;p=L-next;/从表中第一个结点比较从表中第一个结点比较 while(p!=NULL)while(p!=NULL)if(p-data!=key)if(p-data!=key)p=p-next;p=p-next;else break;else break;/找

24、到结点找到结点keykey，退出循环，退出循环 return p;return p;算法算法时间复杂度时间复杂度为为:O(Length(*L)ai-13.单链表插入操作单链表插入操作 InsList(L,i,e)的实现的实现：有序对有序对 改变为改变为 和和 eaiai-1 可见可见,插入结点需要修改第插入结点需要修改第 i-1 个结点的个结点的指针和新结点的指针。指针和新结点的指针。在单链表第在单链表第i i个结点之前插入结点的步骤为个结点之前插入结点的步骤为:pres1)1)找到单链表的第找到单链表的第i-1i-1个结点并由指针个结点并由指针prepre指示。指示。2)2)然后申请一个新结

25、点并由指针然后申请一个新结点并由指针s s指示。指示。3)3)将将prepre指示结点的指针值赋给指示结点的指针值赋给s s指示结点的指针域。指示结点的指针域。(将第将第i i个结点链接到新结点上个结点链接到新结点上)4)4)然后修改然后修改prepre指示结点的指针域指示结点的指针域,使它等于使它等于s s。(新结点链接到第新结点链接到第i-1i-1个结点上个结点上)单链表插入int InsList(LinkList L,int i,ElemType e)int InsList(LinkList L,int i,ElemType e)/在单链表在单链表L L第第i i个结点前插入值为个结点前

26、插入值为e e的新结点的新结点 Node*pre,*s;pre=L;int k=0;Node*pre,*s;pre=L;int k=0;/先找到第先找到第i-1i-1个结点的存储位置个结点的存储位置,让让PrePre指向它指向它 while(pre!=NULL&ki-1)while(pre!=NULL&knext;pre=pre-next;k=k+1;k=k+1;if(k!=i-1)return 0;if(k!=i-1)return 0;s=(Node*)malloc(sizeof(Node);s=(Node*)malloc(sizeof(Node);/申请新结点申请新结点 s-data=e;

27、s-data=e;/将将e e赋给赋给s s指示的数据域指示的数据域 s-next=pre-next;pre-next=s;s-next=pre-next;pre-next=s;/链接链接 return 1;return 1;算法算法时间复杂度时间复杂度为为:O(Length(*L)s=(Node*)malloc(sizeof(Node);s=(Node*)malloc(sizeof(Node);/申请新结点申请新结点 s-data=e;s-data=e;/将将e e赋给赋给s s的数据域的数据域 s-next=pre-next;pre-next=s;s-next=pre-next;pre-n

28、ext=s;/链接链接 ai-1 eaiai-1pres 如下图所示的是链表插入前、后的逻辑状态。从图中可以看出，要插入一个结点，首先要从空间表中取一个空结点k，使得q结点（前趋结点的地址）的指针指向k，k结点的指针指向p（存储ai值的结点地址），同时把数据x存入k，即q-next=k;k-next=p;链表插入逻辑示意图(a)插入前；(b)插入后在链表的插入操作中，结点插入的位置可能有四种情况，下面分别加以介绍。设Head是链表入口或表头，x是插入结点的存储地址。(1)原来链表为空表，即Head=NULL，则插入结点为表首结点，表示为Head=x；x-next=NULL；(2)插入位置在表中

29、第一个结点Head之前，则插入结点为新的表头，表示为x-next=Head；Head=x；(3)插入位置在表的中间，为q结点之后，p结点之前，表示为q-next=x；x-next=p；(4)插入位置在链尾，即新结点x作为原表尾结点p之后的新表尾，表示为x-next=p-next；p-next=x；或 p-next=x；x-next=NULL；单链表删除第i个结点操作为操作为:找到线性表中第找到线性表中第i-1i-1个结点个结点*p,*p,修改其指针域修改其指针域让它指向第让它指向第i+1i+1个结点。释放第个结点。释放第i i个结点的空间。个结点的空间。ai-1aiai+1ai-1r=p-ne

30、xt;p-next=r-next;r=p-next;p-next=r-next;free(r);free(r);print DelList(LinkList L,int i,ElemType*e)int DelList(LinkList L,int i,ElemType*e)/删除单链表删除单链表L L中第中第i i个元素个元素,并保存其值到变量并保存其值到变量*e*e中中 Node*p,*r;p=L;int k=0;Node*p,*r;p=L;int k=0;while(p-next!=NULL&knext!=NULL&knext;k=k+1;p=p-next;k=k+1;if(k!=i-1

31、)if(k!=i-1)/即循环因即循环因p-next=NULLp-next=NULL而跳出而跳出 return 0;return 0;r=p-next;p-next=r-next;r=p-next;p-next=r-next;/删除结点删除结点 free(r);free(r);/释放被删除结点所占空间释放被删除结点所占空间 return 1;return 1;算法的算法的时间复杂度时间复杂度为:O(Length(*L)链表删除的逻辑示意图(a)删除前；(b)删除后 从上图中可以看出，要删除某一个结点，必须知道被删除结点的前趋结点。设被删除结点的地址为s，s的前趋结点为q，s的后继结点为p，则被

32、删除的基本操作步骤为q-next=p；或q-next=s-next；删除操作和插入操作相同，即在链表中搜索到被删除的结点，修改相应的指针，同时把被删除的结点通过调用free(x)，将该结点的空间送空间表。根据被删除结点在链表中的位置，删除操作有如下四种情况：(1)链表中只有一个结点，该结点就是被删除的结点，其操作为Head=NULL；或 Head=Head-next；(2)被删除的结点是链中第一个结点，其操作为 Head=Head-next；(3)被删除的结点在链的中间，其中删除结点的地址为p，前趋结点的地址为q，其操作为q-next=p-next；(4)被删除的结点在链尾，其中删除结点的地址

33、为p，前趋结点的地址为q，其操作为q-next=NULL；或 q-next=p-next；下图给出了线性表删除算法的框图。线性链表删除算法框图删除算法：DELETE(head，key)/*在head为入口的链表中删除值为key的结点*/i=head；w=i；/*设置前趋结点的地址*/while(i!=NULL)&(i-data!=key)w=i；i=i-next；/*查找删除结点的位置*/if(i=NULL)printf(无此结点)；return；else if(head=i)head=i-next；/*删除头结点*/else w-next=i-next；/*删除链中间和链尾结点*/free(

34、i)；用上述定义的单链表实现线性表的操作时，用上述定义的单链表实现线性表的操作时，存在的存在的问题问题：改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值；1增加表长、增加表长、表尾指针表尾指针 和和 当前位置指针当前位置指针；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时，需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i”改变为改变为“指针指针 p”。3 循环链表 最后一个结点的指针域的

35、指针又指回最后一个结点的指针域的指针又指回第一个结点（或头结点）的链表第一个结点（或头结点）的链表 a1 a2 .an 和单链表的差别:判别链表中尾结点的条件不再是“后继指针是否为空”，而是“后继指针是否为头指针”。rear L空链表空链表a1ai-1aian L设头指针的一般形式设头指针的一般形式 a1ai-1aian 设尾指针的一般形式设尾指针的一般形式 rear-next带头结点的循环带头结点的循环单链表示意图单链表示意图通过查询，确定关键字值KEY不在链中，该结点插入的位置和插入的操作有如下几种情况：(1)若表空(Head=NULL)，则插入结点后是只有一个结点的环链表。(2)若表非空

36、，则分为三种情况：插入的位置是在第一个结点，即原表的第一个结点成为结点插入后新表的第二个结点，同时为了保持循环链表的结构特征，在形成新的入口后，链表中最末一个结点的链指针应修正指向新的入口结点。循环链表的插入操作 插入的位置是在最末一个结点之后，那么，最末一个结点的指针指向插入的结点，插入结点的指针仍指向首结点。插入的位置是在链的中间，那么可通过插入位置的前趋结点的指针，完成新结点的插入。下图所示为四种插入操作的示意图。循环有序链表的插入操作示意图下图给出了循环链表删除关键字值为KEY的结点的算法框图。循环链表的删除操作循环链表删除算法框图必须注意，在循环链表中，要充分考虑到可能出现被删除结点

37、位置不同的各个边界条件。若被删除结点在链首，则必须修改入口Head，而且还要考虑到链表中最末一个记录的指针要指向结点删除后的新入口，该情况的操作示意图如下图所示；特殊情况下，被删除结点是第一个且仅只有这一个结点，那么循环链表入口因设置为空，Head=NULL；其他情况与单链表的删除结点的算法相似。循环链表删除首结点(a)删除结点之前；(b)删除结点之后例例 有两个带头结点的循环单链表有两个带头结点的循环单链表LALA、LBLB，编，编写算法，将两个循环单链表合并为一个循环单写算法，将两个循环单链表合并为一个循环单链表，其头指针为链表，其头指针为LALA。算法思想：算法思想：先找到两个链表的尾，

38、并分别由指先找到两个链表的尾，并分别由指针针p p、q q指向它们，然后将第一个链表的尾与第指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个二个表的第一个结点链接起来，并修改第二个表的尾表的尾q q，使它的链域指向第一个表的头结点。，使它的链域指向第一个表的头结点。LinkList merge_1(LinkList LA,LinkList LB)LinkList merge_1(LinkList LA,LinkList LB)/*/*此算法将两个循环单链表的首尾连接起来此算法将两个循环单链表的首尾连接起来*/*/Node*p,*q;p=LA;q=LB;Node*p,*

39、q;p=LA;q=LB;while(p-next!=LA)p=p-next;while(p-next!=LA)p=p-next;/找到找到LALA的表尾的表尾 while(q-next!=LB)q=q-next;while(q-next!=LB)q=q-next;/找到找到LBLB的表尾的表尾 p-next=LB-next;p-next=LB-next;/使使LALA尾指针指向尾指针指向LBLB第第1 1个结点个结点 q-next=LA;q-next=LA;/使使LBLB的尾指针指向表的尾指针指向表LALA的头结点的头结点 free(LB);free(LB);/释放释放LBLB的头结点空间的头

40、结点空间 return(LA);return(LA);4 双向链表双向链表typedef struct Nodetypedef struct Node /结点类型定义结点类型定义 ElemType data ElemType data；struct Node *next struct Node *next；struct Node *prior;struct Node *prior;Node,*LinkListNode,*LinkList；/LinkList/LinkList为结构指针类型为结构指针类型后继指针域后继指针域prior data next前驱指针域前驱指针域数据域数据域双向链表的结

41、构双向链表的结构有以下特点：(1)若Head为空(NULL)，则双向链表为空。(2)在双向链表中，若结点i有i-Lnext=NULL则该结点是链的第一个结点；若结点i有i-Lnext=i-Rnext=NULL 则该结点i是链的第一个结点且该链仅有这个结点i。(3)在双链表中，若结点i有i-Rnext=NULL则该结点是链的最末一个结点。(4)在双向链表中，若结点i是表中任意结点的地址，则该结点的前趋结点是iLnext，后继结点的地址是iRnext，对结点i也可以表示为i=i-Rnext-Lnext=i-Lnext-Rnext这个表达式非常直观地反映了双向链表结构的本质特点，即无论是沿着表向前，

42、还是向后都同样方便。双向链表的操作特点：双向链表的操作特点：“查询查询”和单链表相同。可增加和单链表相同。可增加一种从后向前的一种从后向前的“查询查询”方式。方式。“插入插入”和和“删除删除”时需要同时修时需要同时修改两个方向上的指针。改两个方向上的指针。ai-1aies-next=p-next;p-next=s;s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;s-next-prior=s;s-prior=p;sai-1ai插入插入pai-1删除删除aiai+1q=p-next;p-next=q-next;q=p-next;p-next=q-ne

43、xt;p-next-prior=p;p-next-prior=p;free(q);free(q);pai-1q双向链表删除操作是否可不用工作指针双向链表删除操作是否可不用工作指针q?q?q qai-1删除删除aiai+1p-next=p-next-next;p-next=p-next-next;free(free(p-next-priorp-next-prior););p-next-prior=p;p-next-prior=p;pai-1空表空表非空表非空表a1 a2 .an hehe 双向循环链表双向循环链表单链表和循环单链表均只有一个链指针next，指向后继结点，而双向链表有两个指针，即向

44、前指针Lnext和向后指针Rnext。单链表结构的查询只能从链表入口开始，按结点的链指针逐个查询，直至结束；循环单链表可以从任意一个结点入口，按结点的指针循环查遍全表；双向链表按其结构特征可以同时向前和向后进行查询而搜索全表。从存储空间的占有量分析，单链表和循环单链表所需的存储空间是相同的，而双链表由于增加了一个向前指针Lnext，因此大约需要增加一倍的指针存储空间。5 各种链式存储结构的比较空间空间存储空间静态分配，需事先确定存储密度高(d=1)(不考虑空闲区)时间时间是随机存取结构，可以根据序号直接定位插入/删除结点操作时数据元素要移动空间空间存储空间动态分配，可以按需要使用每一结点附加指

45、针域(d1)时间时间是非随机存取结构，定位需从头指针扫描插入/删除结点操作时通常只要修改指针6 顺序表与链表的比较 顺序表和链表的存储结构(a)顺序表；(b)单链表线性表的存储方式对比小结本章主要介绍了如下一些基本概念：线线性性表表：一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。线线性性表表的的顺顺序序存存储储结结构构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。线线性性表表的的链链式式存存储储结结构构：线性表的链式存储结构就是用一组任意的存储单元结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的

46、数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。循循环环链链表表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。双向链表：双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。除上述基本概念以外，还应该了解：线性表的基本操作（初始化、插入、删除、存取、复制、合并）、顺序存储结构的表示、线性表的链式存储结构的表示，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。