chapt2+线性表（二）.ppt

第二章线性表,线性表概念及其逻辑结构线性表的存储结构顺序存储链式存储数组一维数组结构数组二维数组链表单链表双链表循环链表静态链表线性表应用实例有序线性表,线性表（二）,链表单链表双链表循环链表静态链表线性表应用实例有序线性表,4链表,具备链式存储结构的线性表也可称之为链表。链表串联的方式通常有两种：一种是利用数组结构串联的有序列表：利用两个数组，一个存放数据，另一个存放链接关系。另一种是以结点形式串接的链表，通常我们所指的链表就是这种动态内存配置的链表。结点（node）：数据元素的存储映像,包含数据域和指针域信息。数据域：存储数据元素的域称作数据域，指针域（链域）：存储直接后继元素存储位置的域称作指针域。指针域中存储的信息称作指针或链。n个结点链接成一个链表，即为线性表（a1,a2,a3,an）的链式存储结构。,一、单链表,31,头指针Head,链表中若每个结点指针域中只包含一个链，称为单链表或线性链表。单链表存储示意图：内存空间的分配表示。【例】线性表（zhao,qian,sun,li,zhou,wu,zheng,wang）单链表逻辑状态示意图：,Head,整个链表的存取必须从头指针开始进行，头指针指示链表中的首结点（第一个元素的存储映像）的存储位置，这里用Head表示；由于最后一个元素没有直接后继，最后一个结点的指针是NULL（指针为空），表示这是链表的结尾。由于取得任意一个数据元素都必须从头指针出发寻找，所以单链表是非随机存储的存储结构。这种单链表数据元素之间的逻辑关系是由结点中的指针指示的，只要确定头指针的位置，就可以确定链表中所有元素的位置。换句话说，单链表由头指针唯一确定。可以借助高级语言中的“指针”数据类型来描述线性链表。链式结构的存储效率：存储密度=结点数据信息所占存储空间/结点结构所占全部空间,带头结点单链表示意图,在线性表的链式存储中，为了便于插入和删除算法的实现，可以使用带头结点的链表结构，每个链表带有一个头结点，并通过头结点的指针惟一标识该链表。头结点数据域不需要赋值，指针指向链表的首个含有实质信息的结点。,1、单链表内结点的配置链表的内存空间动态配置，在程序运行过程中才向系统配置所需空间。使用链表之前，先要定义出每一个结点的数据结构。C语言中，结点的格式声明如下：struct结构名称数据类型数据变量；数据类型数据变量；.struct结构名称*next；typedefstruct结构名称Node；/定义Node为使用上述结构的结点类型typedefNode*link；/定义指向Node结点的指针类型定义了上述结点，在程序中使用结点结构之前，需要声明新结点：Link变量名称;（一个具备Node类型的结点）,程序运行中用到所声明结点时，还需要配置结点：向系统申请结点所需内存空间；为结点数据域赋值，并标记指针域。例如，已定义一个名称为Student的结点，使用到这个结点时，还需利用malloc函数向系统要求配置内存空间。Student=（Link）malloc（sizeof（Node）；内存配置成功，则为该结点返回一个指针；内存配置不成功时，返回NULL指针。另外，调用malloc函数，还需在程序开头使用包含命令注明其头文件：#include,结点空间配置成功则赋值：为结点的数据域赋值：New-Data(结点结构中数据变量名)=23;若结点结构中定义了多个变量，则可逐一赋值。如：New-Number=23;New-Namei=Datanamei;为结点的指针域赋值：New-Next=NULL;内存配置成功，且为结点赋值之后结构如下：（若新结点为New）New,单链表类型定义也可如下表示(本教材定义方法)：在单链表中，假定每个结点类型用LinkList表示，它应包括存储元素的数据域，这里用data表示，其类型使用通用类型标识符ElemType表示；还包括存储后继元素位置的指针域，这里用next表示。则LinkList类型的定义如下:typedefstructLNode/*定义单链表结点类型*/ElemTypedata;structLNode*next;/*指向后继结点*/LinkList;/*定义单链表*/定义了上述结点，在程序中使用结点结构之前，声明新结点：LinkList*结点名称；,如，定义结点s：LinkList*s；则配置（建立）新结点s的过程为：s=(LinkList*)malloc(sizeof(LinkList);s-data=ai;s-next=NULL;,2、单链表的建立单链表的建立就是从首结点开始，将每个结点单向串联起来。建立步骤：为每一个结点配置空间；为结点赋值；挂接结点。（1）头插法先声明一个头结点Head，为其配置空间；令Head-Next=NULL。（空头结点，便于链表的插入和删除操作。）每输入一笔数据就声明一个新结点New，为其配置空间；为新结点数据域赋值，令New-Next=Head-Next（即将新结点链接到链表头结点之后）；令头结点指针指向New。教材p39、p40,i=0,i=1,i=2,i=3,head,采用头插法建立单链表的过程,head,head,head,head,第1步:建头结点,第2步:i0,新建a结点,插入到头结点之后,第3步:i1,新建d结点,插入到头结点之后,第4步:i2,新建c结点,插入到头结点之后,第5步:i3,新建b结点,插入到头结点之后,（2）尾插法先声明一个头结点Head，为其配置空间；令Head-Next=NULL。（空头结点，便于链表的插入和删除操作。）每输入一笔数据就声明一个新结点New，为其配置空间；为新结点数据域赋值，令New-Next=NULL；将新结点链接到链表尾结点之后；令尾结点为New。教材p39、p40,b,c,d,a,i=0,i=1,i=2,i=3,head,头结点,a,d,c,采用尾插法建立单链表的过程,3、单链表的释放链式结构使用结束须向系统释放使用的空间，以节省内存空间，保持内存配置的动态特性。单链表的释放就是将结点逐个释放。释放内存空间需调用free函数，声明格式如下：free(变量名称)如上例free(New)单链表释放步骤：先将工作指针指向第一个结点，将当前结点释放后，再将工作指针指向其下一个结点。重复该步骤直至工作指针指向NULL。教材p41DestroyList(L)【例】VoidClearList(LinkList/释放首元结点16.,4、单链表的基本操作定义好单链表结构，基于该结构通常定义如下一组基本操作：（1）初始化单链表InitList(L)建立一个空头结点。算法时间复杂度O(1)。（2）销毁单链表DestoryList(L)即释放单链表L。算法时间复杂度O(n)。（3）判断单链表是否为空ListEmpty(L)返回值为1或0。算法时间复杂度O(1)。（4）求取单链表长度ListLength(L)即返回单链表的结点个数，作为链表长度。算法时间复杂度O(n)。（5）输出单链表DispList(L)从首结点起，将结点数据域纸打印在标准输出。算法时间复杂度O(n)。（6）从单链表中取得指定结点的数据元GetElem(L,i,e)从首结点起，找到指定的第i个结点，并取出数据值赋给变量e。属于线性查找，算法时间复杂度O(n)。,（7）从单链表中查找指定数据元的结点LocateElem(L,e)从首结点起，找到关键字值为e的结点，并返回结点位置（第i个）。属于线性查找，算法时间复杂度O(L-length)或O(n)。（8）在单链表中插入结点ListInsert(L,i,e)令e成为链表中第i个结点。从首结点起，找到第i-1个结点，并将数据元为e的新结点插入其后。插入位置i:1iListLength(L)+1该算法查找结点属于线性查找，算法时间复杂度O(n)。（9）从单链表中取得指定结点的数据元GetElem(L,i,e)从首结点起，找到指定的第i个结点，取出数据值赋给变量e保留，而后删除结点i。属于线性查找，算法时间复杂度O(n)。两种常规操作：在单链表中插入结点操作和删除结点操作,插入结点运算插入运算是将值为x的新结点插入到单链表的第i个结点的位置上。先在单链表中找到第i-1个结点,再在其后插入新结点。单链表插入结点的过程如下图所示。,插入结点示意图,删除结点运算删除运算是将单链表的第i个结点删去。先在单链表中找到第i-1个结点,再删除其后的结点。删除单链表结点的过程如下图所示。,删除结点示意图,5、单链表的应用单链表在系统设计中应用十分广泛，是实现链式存储的最基础的数据结构。单链表的三项基本操作：定位（查找结点）、插入结点、删除结点。定位操作的时间复杂度为O（n）；插入与删除结点算法的时间复杂度均为O（1）。下面讨论几个基于单链表的典型操作：（1）单链表的反转把单链表的指针从头至尾反转方向，原先的头结点作为尾结点，指针指向NULL，逐个反转指针方向，原先的尾结点变为头结点。设计思路：可分三种情况首结点的指针反转；中间结点的指针反转；尾结点的指针反转。具体方法：需要设置三个指针Back、pointer、Next。以pointer为当前结点（也是行走结点）。,步骤一：先将Back指向首结点；Pointer指向第二个结点；反转首结点（Back）的指针，指向NULL。Back=Head;Pointer=Back-NextBack-Next=NULL然后定义Next结点为第三个结点；将第二个结点Pointer指针反转；将Back结点后移一位；将Pointer结点也后移一位。（红色）Next=Pointer-Next;Pointer-Next=Back;Back=Pointer;Pointer=Netx;,步骤二：经过步骤一后图示如下：此时，Back、Pointer、Next均为中间结点。从设立Next结点开始，重复第二种情况，逐个反转Pointer所指向的结点（当前结点）指针，直到Pointer结点的指针指向NULL为止。步骤三：反转尾结点的指针，并令尾结点为首结点。Pointer-Next=Back;Head=Pointer;总结：1）总是在反转某个结点指针之前定义好其下一个结点的指针2）每一步均完成对Pointer结点的反转3）Next比Back、Pointer滞后一步定义，作为后半截链表首节点,LinkInvert_List(LinkHead)Linkpointer;LinkBack;Linknext;Back=Head;Pointer=Back-Next；Back-Next=NULL；/*反转首结点*/While(Pointer-Next!=NULL)Next=Pointer-Next;Pointer-Next=Back;Back=Pointer;Pointer=Netx;/*反转中间结点*/Pointer-Next=Back;Head=Pointer;returnHead;/*反转尾结点*/,【例2.5】设C=a1,b1,a2,b2,an,bn为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得:A=a1,a2,an,B=b1,b2,bn,解:设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点*ha和*hb,它们用于存放拆分后的线性表A和B。ra和rb分别指向这两个单链表的表尾,用p指针扫描单链表hc,将当前结点*p链到ha未尾,p沿next域下移一个结点,若不为空,则当前结点*p链到hb未尾,p沿next域下移一个结点,如此这样,直到p为空。最后将两个尾结点的next域置空。对应算法如下:,voidfun(LinkList*hc,LinkList*/*rb始终指向hb的末尾结点*/,while(p!=NULL)ra-next=p;ra=p;/*将*p链到ha单链表未尾*/p=p-next;if(p!=NULL)rb-next=p;rb=p;/*将*p链到hb单链表未尾*/p=p-next;ra-next=rb-next=NULL;/*两个尾结点的next域置空*/,【例2.6】有一个带头结点的单链表head,其ElemType类型为char,设计一个算法使其元素递增有序。解:若原单链表中有一个或以上的数据结点,先构造只含一个数据结点的有序表(只含一个数据结点的单链表一定是有序表)。扫描原单链表余下的结点*p(当前结点，行走直到p=NULL为止),在有序表中通过比较找到插入*p的前驱结点*q,然后将*p插入到*q之后(这里实际上采用的是直接插入排序方法)。,voidSort(LinkList*/r保存p结点后继结点的指针/,q=head;while(q-next!=NULL/扫描原单链表余下的结点/,二、双链表,单链表的结点中只有一个指向其直接后继的指针。由此，从某个结点出发只能顺着指针方向向后寻找其它的结点。若要寻找某个结点的直接前趋，仍需要从首结点出发，找到那个直接后继为该结点的结点。为了克服单链表这种单向性的缺点，我们可以使用双向链表。顾名思义，在双向链表中有两个指针域，一个指向结点的直接前趋；另一个指向结点的直接后继。1、双向链表的建立对于双链表，采用类似于单链表的类型定义，其DLinkList类型的定义如下：typedefstructDNode/*定义双链表结点类型*/ElemTypedata;structDNode*prior;/*指向前驱结点*/structDNode*next;/*指向后继结点*/DLinkList;/*定义双链表*/,双链表的内存定位，仍可由首结点或尾结点确定。我们可根据通常在哪一端操作确定来保留定位结点，当然也可以保留首尾两个结点。双链表建立：如上图三个结点(node1-back=NULL;)node1-next=node2;node2-back=node1;node2-next=node3;node3-bake=node2;(node3-next=NULL;)编制具体算法时，仍可如单链表一样采用头插法和尾插法实现。教材p44-45,3、双链表的基本操作在双链表中,有些操作如求长度、取元素值、查找元素、输出和释放链表等操作算法与单链表中相应算法是相同的。双链表插入和删除与单链表有较大差别。单链表中,进行结点插入和删除时涉及到前后结点的一个指针域的变化。双链表中,结点的插入和删除操作涉及到前后结点的两个指针域的变化。（1）在双链表中插入结点在双链表中p所指的结点之后插入一个s结点，其操作语句描述为:s-next=p-next;/*将s插入到p之后*/s-prior=p;p-next-prior=s;仍需注意链表断裂问题！p-next=s;插入结点操作算法的时间复杂度为O(n)【例】在双链表中插入元素算法教材p45,双链表中插入结点示意图,（1）在双链表中删除结点删除双链表L中*p结点的后续结点。其操作语句描述为:p-next=q-next;q-next-prior=p;双链表中删除结点操作算法的时间复杂度为O(n),三、循环链表循环链表是另一种形式的链式存储结构。特点是链表的尾指针不指向NULL，而是指向Head，整个链表形成一个环链。由此，从任意一个结点出发均可找到链表中的其它结点。仍可设立头结点来确定整条链表的位置。因为其首尾相接的特性，有时候只需要设立一个尾指针确定链表的内存位置，并可不再设立头指针以简化操作。对当前指针在行走一遍的相关操作中，通常不再判断其是否为NULL，而是是否为Head（或空头结点L）。1、建立循环单链表如同建立单链表算法，可使用尾插法，结点插入结束后将尾结点指针指向头结点。教材P40尾插法算法修改尾指针：r-next=L;,带头结点的循环单链表和循环双链表示意图,3、释放循环链表的结点方法一：如果确定了头结点的位置，则释放循环链表的结点时，通常从第二个结点开始，这是为了保存整个环链的完整性。比如先将头结点与第三个结点链接，释放第二个，再与第四个链接，释放第三个如此依序，释放完尾结点时，头结点的指针指向自己，直接释放头结点。如此操作，在整个释放过程中可以不必重新为系统确定整条链表的位置，头结点一直存在至最后一个才被释放。另外环链一直不会断裂，不影响其他操作。算法实现如下：（使用pointer指针指向当前欲释放的结点：）next=head-next;/*next先指向第二个结点*/While(next!=head)pointer=next;/*next做为行走结点，从第二个走向尾*/next=next-next;head-next=next;/*头结点不变，并且环链不断裂*/free(pointer);free(head);,方法二：先将循环链表断为单链表，再从首结点一直释放到尾结点。将首结点做为尾结点，则第二个结点为新的首结点，然后从新的首结点一直释放到尾结点。（释放每一个首结点，所以需考虑重新定位）实际上与上一种释放方式一样，都从原循环链表第二个开始，只是首尾指针有所变化，变成了单链表。这种方法破坏了环链的特性，适合于单一的释放结点操作。具体算法：Pointer=head-next;headHead-next=NULL;(head)While(pointer!=NULL)pointerpointerHead=pointer;pointer=pointer-next;free(head);,【例】编写出判断带头结点的双向循环链表L是否对称相等的算法。p从左向右扫描L，q从右向左扫描L，若对应数据结点的data域不相等，则退出循环，否则继续比较，直到p与q相等或p的下一个结点为*q为止。对应算法如下:,intEqueal(DLinkList*L)intsame=1;DLinkList*p=L-next;/*p指向第一个数据结点*/DLinkList*q=L-prior;/*q指向最后数据结点*/while(same=1)if(p-data!=q-data)same=0;elseif(p=q)break;/*数据结点为奇数的情况*/q=q-prior;if(p=q)break;/*数据结点