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

第2章 线性表(二),张成文北京邮电大学计算机学院,主要内容,2.7 线性表的链式存储结构表示2.8 单链表2.9 循环链表2.10 双向链表2.11各种链式存储结构的比较2.12顺序表与链表的比较 2.13小结,线性表的链式存储结构表示,结点(Node):既要存储线性表的每个数据元素值,又要存储指示其后继结点的地址(或位置)信息,以表示结点间的逻辑关系。这两部分信息组成的存储映象叫做结点(Node)。,1 线性表的链式存储结构表示,让每个存储结点都包含两部分：数据域和指针域,数据域：存储元素的值,指针域：存储直接后继或直接前驱元素的存储地址,设计思想：牺牲空间效率换取时间效率,其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。,如何实现？,通过指针来实现！,链式存储结构特点,a1,a2,a3,与链式存储有关的术语,1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双向链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域（直接前驱和直接后继）的链表，称为双向链表；首尾相接的链表称为循环链表。,循环链表示意图：,head,4）头指针、头结点和首元结点的区别,示意图如下：,头指针,头结点,首元结点,头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。,下面举例说明。,头指针L,头指针L,头结点,首元结点,首元结点,空表：L=NULL,L,1264,1264,4016,4016,头结点的作用：插入和删除第一个数据元素时不必对头指针进行特殊处理。,与链式存储有关的术语,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,例1：,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,称：头指针H的值是31,例2：线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31，若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。,其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？,100,119,答：X=Y=Z=,首址=末址=.,104,108,116,112,116,NULL/0,100,108,112,单链表,单链表:链表中的每个结点只有一个指针域,我们将这种链表称为单链表。单链表包括两个域:数据域用来存储结点的值;指针域用来存储数据元素的直接后继的地址(或位置)。,从链表的整体结构上看，链表可以是空链，也可以由一个或多个结点组成。每条链有一个入口的头结点，该结点仅指示链中第一个结点的地址。如是空链，则可表示为“0”或“”，它类似于一个常量。每条链的最后一个结点的链指针为“0”，也可用“”作为链的结束标志。下图给出了链表的示意形式。图(a)中有一个头结点和具有A、B、C、D数据元素的链，图(b)所示为线性链表的一般表示，结点与结点之间用箭头链接。,单链表,链表图示(a)链表的图示；(b)链表的一般表示,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时，头结点的指针域为空,讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？,因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。,答：,以26个字母的链表为例，每个结点都有两个分量：,假设每个结点用变量node表示，结点指针用p表示，其中两个分量分别用data和*next表示，该如何书写？,方式1：直接表示为 node.dataa；node.next=q方式2：p指向结点首地址，然后 p-data=a;p-next=q;方式3：p指向结点首地址，然后(*p).data=a；(*p).nextq,单链表的存储结构描述,typedef struct Node/结点类型定义 ElemType data；struct Node*next；Node,*LinkList；/LinkList为结构指针类型,设p为指向链表的第i个元素的指针,则第i个元素的数据域写为，指针域写为。,练习：,p-data,ai的值,p-next,ai+1的地址,链表不具备的特点是。A、可随机访问任何一个元素 B、插入、删除操作不需要移动元素 C、无需事先估计存储空间大小 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个元素的下标：SLinkList0.cur,带头结点的单链表上的基本运算,1 建立单链表2 单链表查找3 单链表插入4 单链表删除第i个结点,建立单链表,1)头插法建表（逆序）,操作步骤：,建立一个“空表”；,输入数据元素an，建立结点并插入；,输入数据元素an-1，建立结点并插入；,an,an-1,依次类推，直至输入a1为止。,头插法建表算法,Linklist CreateFromHead()LinkList L;Node*s;int flag=1;/标志flag初值为1 L=(Linklist)malloc(sizeof(Node);/分配头结点 L-next=NULL;while(flag)/输入“$”时,flag置0,建表结束 c=getchar();if(c!=$)/为新结点分配存储空间 s=(Node*)malloc(sizeof(Node);s-data=c;s-next=L-next;L-next=s;/链接 else flag=0;return L；,2)尾插法建表：设尾指针r建立一个“空表”,r 指向头结点;输入数据元素C1,建立结点并链接,r指向该结点；输入数据元素C2,建立结点并链接,r指向该结点；输入数据元素Cn,建立结点并链接,r指向该结点；,尾插法建表算法,Linklist CreateFromTail()/新结点加到链表末尾 LinkList L;Node*r,*s;int flag=1;/flag初值 L=(Node*)malloc(sizeof(Node);/分配头结点 L-next=NULL;r=L;/r始终指向链表的表尾 while(flag)/输入“$”时flag为0，建表结束 c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s/链接 else flag=0;r-next=NULL;return L；,单链表查找,1)按序号查找 算法描述：设带头结点的单链表的长度为n,要查找表中第i个结点,则需要从单链表的头指针L出发,从头结点（L-next）开始顺着链域扫描,用指针p指向当前扫描到的结点,初值指向头结点(p=L),用j做记数器,累计当前扫描过的结点数(初值为0),当j=i 时,指针p所指的结点就是要找的第i个结点。算法实现,算法演示。,线性表的操作 Get(L,i)在单链表中i=3时,Get的实现过程:,j,1,2,3,P-data=30,因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i。,令指针 p 始终指向线性表中第 j 个数据元素。,单链表是一种顺序存取的结构,为找第 i 个数据元素,必须先找到第 i-1个数据元素。,按序号查找算法实现,/找第i个结点,找到返回指向它的指针;否则返回空Node*Get(LinkList L,int i)Node*p；p=L；j=0；/从头结点开始扫描 while(p-next!=NULL)&(jnext；j+；/扫描下一结点 if（i=j）return p；/找到了第i个结点 else return NULL；/找不到,i0或in,算法时间复杂度为:,O(Length(*L),2)按值查找算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。,按值查找算法实现,/查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL*/Node*Locate(LinkList L,ElemType key)Node*p;p=L-next;/从表中第一个结点比较 while(p!=NULL)if(p-data!=key)p=p-next;else break;/找到结点key，退出循环 return p;,算法时间复杂度为:,O(Length(*L),3.单链表插入操作 InsList(L,i,e)的实现：,有序对 改变为 和,可见,插入结点需要修改第 i-1 个结点的指针和新结点的指针。,在单链表第i个结点之前插入结点的步骤为:,1)找到单链表的第i-1个结点并由指针pre指示。,2)然后申请一个新结点并由指针s指示。,3)将pre指示结点的指针值赋给s指示结点的指针域。(将第i个结点链接到新结点上),4)然后修改pre指示结点的指针域,使它等于s。(新结点链接到第i-1个结点上),单链表插入,int InsList(LinkList L,int i,ElemType e)/在单链表L第i个结点前插入值为e的新结点 Node*pre,*s;pre=L;int k=0;/先找到第i-1个结点的存储位置,让Pre指向它 while(pre!=NULL,算法时间复杂度为:,O(Length(*L),s=(Node*)malloc(sizeof(Node);/申请新结点 s-data=e;/将e赋给s的数据域 s-next=pre-next;pre-next=s;/链接,如下图所示的是链表插入前、后的逻辑状态。从图中可以看出，要插入一个结点，首先要从空间表中取一个空结点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)插入位置在表中第一个结点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-1个结点*p,修改其指针域让它指向第i+1个结点。释放第i个结点的空间。,r=p-next;p-next=r-next;free(r);,p,r,int DelList(LinkList L,int i,ElemType*e)/删除单链表L中第i个元素,并保存其值到变量*e中 Node*p,*r;p=L;int k=0;while(p-next!=NULL,算法的时间复杂度为:,O(Length(*L),链表删除的逻辑示意图(a)删除前；(b)删除后,从上图中可以看出，要删除某一个结点，必须知道被删除结点的前趋结点。设被删除结点的地址为s，s的前趋结点为q，s的后继结点为p，则被删除的基本操作步骤为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)被删除的结点在链尾，其中删除结点的地址为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(i)；,用上述定义的单链表实现线性表的操作时，存在的问题：,改进链表的设置：,1单链表的表长是一个隐含的值；,1增加表长、表尾指针 和 当前位置指针；,2在单链表的最后一个元素之后插入元素时，需遍历整个链表；,3在链表中，元素的“位序”概念淡化，结点的“位置”概念加强。,2将基本操作中的“位序 i”改变为“指针 p”。,3 循环链表,最后一个结点的指针域的指针又指回第一个结点（或头结点）的链表,和单链表的差别:判别链表中尾结点的条件不再是“后继指针是否为空”，而是“后继指针是否为头指针”。,带头结点的循环单链表示意图,通过查询，确定关键字值KEY不在链中，该结点插入的位置和插入的操作有如下几种情况：(1)若表空(Head=NULL)，则插入结点后是只有一个结点的环链表。(2)若表非空，则分为三种情况：插入的位置是在第一个结点，即原表的第一个结点成为结点插入后新表的第二个结点，同时为了保持循环链表的结构特征，在形成新的入口后，链表中最末一个结点的链指针应修正指向新的入口结点。,循环链表的插入操作,插入的位置是在最末一个结点之后，那么，最末一个结点的指针指向插入的结点，插入结点的指针仍指向首结点。插入的位置是在链的中间，那么可通过插入位置的前趋结点的指针，完成新结点的插入。下图所示为四种插入操作的示意图。,循环有序链表的插入操作示意图,下图给出了循环链表删除关键字值为KEY的结点的算法框图。,循环链表的删除操作,循环链表删除算法框图,必须注意，在循环链表中，要充分考虑到可能出现被删除结点位置不同的各个边界条件。若被删除结点在链首，则必须修改入口Head，而且还要考虑到链表中最末一个记录的指针要指向结点删除后的新入口，该情况的操作示意图如下图所示；特殊情况下，被删除结点是第一个且仅只有这一个结点，那么循环链表入口因设置为空，Head=NULL；其他情况与单链表的删除结点的算法相似。,循环链表删除首结点(a)删除结点之前；(b)删除结点之后,例 有两个带头结点的循环单链表LA、LB，编写算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。,算法思想：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。,LinkList merge_1(LinkList LA,LinkList LB)/*此算法将两个循环单链表的首尾连接起来*/Node*p,*q;p=LA;q=LB;while(p-next!=LA)p=p-next;/找到LA的表尾 while(q-next!=LB)q=q-next;/找到LB的表尾 p-next=LB-next;/使LA尾指针指向LB第1个结点 q-next=LA;/使LB的尾指针指向表LA的头结点 free(LB);/释放LB的头结点空间 return(LA);,4 双向链表,typedef struct Node/结点类型定义 ElemType data；struct Node*next；struct Node*prior;Node,*LinkList；/LinkList为结构指针类型,双向链表的结构,双向链表的结构有以下特点：(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这个表达式非常直观地反映了双向链表结构的本质特点，即无论是沿着表向前，还是向后都同样方便。,双向链表的操作特点：,“查询”和单链表相同。可增加一种从后向前的“查询”方式。,“插入”和“删除”时需要同时修改两个方向上的指针。,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,s,插入,删除,q=p-next;p-next=q-next;p-next-prior=p;free(q);,p,双向链表删除操作是否可不用工作指针q?,q,删除,p-next=p-next-next;free(p-next-prior);p-next-prior=p;,p,空表,非空表,he,he,双向循环链表,单链表和循环单链表均只有一个链指针next，指向后继结点，而双向链表有两个指针，即向前指针Lnext和向后指针Rnext。单链表结构的查询只能从链表入口开始，按结点的链指针逐个查询，直至结束；循环单链表可以从任意一个结点入口，按结点的指针循环查遍全表；双向链表按其结构特征可以同时向前和向后进行查询而搜索全表。从存储空间的占有量分析，单链表和循环单链表所需的存储空间是相同的，而双链表由于增加了一个向前指针Lnext，因此大约需要增加一倍的指针存储空间。,5 各种链式存储结构的比较,空间存储空间静态分配，需事先确定存储密度高(d=1)(不考虑空闲区)时间是随机存取结构，可以根据序号直接定位插入/删除结点操作时数据元素要移动,空间存储空间动态分配，可以按需要使用每一结点附加指针域(d1)时间是非随机存取结构，定位需从头指针扫描插入/删除结点操作时通常只要修改指针,6 顺序表与链表的比较,顺序表和链表的存储结构(a)顺序表；(b)单链表,线性表的存储方式对比,小结,本章主要介绍了如下一些基本概念：线性表：一个线性表是n0个数据元素a0，a1，a2，an-1的有限序列。线性表的顺序存储结构：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，称作线性表的顺序存储结构。线性表的链式存储结构：线性表的链式存储结构就是用一组任意的存储单元结点（可以是不连续的）存储线性表的数据元素。表中每一个数据元素，都由存放数据元素值的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。,循环链表：循环链表(Circular Linked List)是将单链表的表中最后一个结点指针指向链表的表头结点，整个链表形成一个环，从表中任一结点出发都可找到表中其他的结点。双向链表：双向链表中，在每一个结点除了数据域外，还包含两个指针域，一个指针（next）指向该结点的后继结点，另一个指针（prior）指向它的前驱结点。除上述基本概念以外，还应该了解：线性表的基本操作（初始化、插入、删除、存取、复制、合并）、顺序存储结构的表示、线性表的链式存储结构的表示，掌握顺序存储结构（初始化、插入操作、删除操作）、单链表（单链表的初始化、单链表的插入、单链表的删除）。,