chapt线性表二PPT课件

1、第二章第二章 线性表线性表o 线性表概念及其逻辑结构o 线性表的存储结构o 顺序存储o 链式存储o 数组o 一维数组o 结构数组o 二维数组o 链表o 单链表o 双链表o 循环链表o 静态链表o 线性表应用实例o 有序线性表第1页/共46页线性表（二）线性表（二）o 链表o 单链表o 双链表o 循环链表o 静态链表o 线性表应用实例o 有序线性表第2页/共46页4 4 链表具备链式存储结构的线性表也可称之为链表。链表串联的方式通常有两种：一种是利用数组结构串联的有序列表：利用两个数组，一个存放数据，另一个存放链接关系。 另一种是以结点形式串接的链表，通常我们所指的链表就是这种动态内存配置的链表

2、。 结点（node）：数据元素的存储映像,包含数据域和指针域信息。数据域：存储数据元素的域称作数据域，指针域（链域）：存储直接后继元素存储位置的域称作指针域。指针域中存储的信息称作指针或链。 n个结点链接成一个链表，即为线性表（a1 , a2 , a3 , , an）的链式存储结构。第3页/共46页一、单链表31头指针Head存储地址数据域指针域 1LI43 7QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25ZHAOQIANSUNLIZHOUWUZHENGWANG NULL链表中若每个结点指针域中只包含一个链，称为单链表或线性链表。单链表

3、存储示意图：内存空间的分配表示。【例】线性表（zhao, qian, sun, li, zhou, wu, zheng, wang） 单链表逻辑状态示意图 ： Head第4页/共46页整个链表的存取必须从头指针开始进行，头指针指示链表中的首结点（第一个元素的存储映像）的存储位置，这里用Head表示；由于最后一个元素没有直接后继，最后一个结点的指针是NULL（指针为空），表示这是链表的结尾。由于取得任意一个数据元素都必须从头指针出发寻找，所以单链表是非随机存储的存储结构。这种单链表数据元素之间的逻辑关系是由结点中的指针指示的，只要确定头指针的位置，就可以确定链表中所有元素的位置。换句话说，单链表

4、由头指针唯一确定。可以借助高级语言中的“指针”数据类型来描述线性链表。 链式结构的存储效率： 存储密度=结点数据信息所占存储空间 / / 结点结构所占全部空间第5页/共46页带头结点单链表示意图带头结点单链表示意图 在线性表的链式存储中，为了便于插入和删除算法的实现，可以使用带头结点的链表结构，每个链表带有一个头结点，并通过头结点的指针惟一标识该链表。头结点数据域不需要赋值，指针指向链表的首个含有实质信息的结点。第6页/共46页1、单链表内结点的配置链表的内存空间动态配置，在程序运行过程中才向系统配置所需空间。使用链表之前，先要定义出每一个结点的数据结构。 C语言中，结点的格式声明如下： st

5、ruct 结构名称 数据类型 数据变量； 数据类型 数据变量； . struct 结构名称 *next； ； typedef struct 结构名称 Node；/定义Node为使用上述结构的结点类型 typedef Node *link； /定义指向Node结点的指针类型定义了上述结点，在程序中使用结点结构之前，需要声明新结点： Link 变量名称; （一个具备Node类型的结点）第7页/共46页程序运行中用到所声明结点时，还需要配置结点： 向系统申请结点所需内存空间； 为结点数据域赋值，并标记指针域。 例如，已定义一个名称为Student的结点，使用到这个结点时，还需利用malloc函数向系

6、统要求配置内存空间。 Student = （Link）malloc（sizeof（Node）； 内存配置成功，则为该结点返回一个指针；内存配置不成功时，返回NULL指针。 另外，调用malloc函数，还需在程序开头使用包含命令注明其头文件：#include 第8页/共46页结点空间配置成功则赋值： 为结点的数据域赋值： New-Data(结点结构中数据变量名) = 23; 若结点结构中定义了多个变量，则可逐一赋值。 如：New-Number = 23; New-Namei = Datanamei; 为结点的指针域赋值： New-Next = NULL; 内存配置成功，且为结点赋值之后结构如下：

7、（若新结点为New） NewData Next 23第9页/共46页 单链表类型定义也可如下表示( (本教材定义方法) )： 在单链表中，假定每个结点类型用LinkList表示，它应包括存储元素的数据域，这里用 data 表示，其类型使用通用类型标识符ElemType 表示；还包括存储后继元素位置的指针域，这里用 next表示。则LinkList类型的定义如下类型的定义如下: typedef struct LNode /*定义单链表结点类型定义单链表结点类型*/ ElemType data; struct LNode *next; /*指向后继结点指向后继结点*/ LinkList; /*定义

8、单链表*/ 定义了上述结点，在程序中使用结点结构之前，声明新结点： LinkList *结点名称；第10页/共46页 如，定义结点s： LinkList *s ； 则配置（建立）新结点s的过程为： s=(LinkList * *)malloc(sizeof(LinkList); s- -data=ai i; s- -next=NULL;第11页/共46页2 2、单链表的建立单链表的建立就是从首结点开始，将每个结点单向串联起来。建立步骤：为每一个结点配置空间；为结点赋值；挂接结点。（1）头插法先声明一个头结点Head，为其配置空间；令Head-Next =NULL。 （空头结点，便于链表的插入和

9、删除操作。）每输入一笔数据就声明一个新结点New，为其配置空间；为新结点数据域赋值，令New-Next = Head -Next （即将新结点链接到链表头结点之后）；令头结点指针指向New 。教材p39p39、p40p40第12页/共46页adc bi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程headaheaddaheadcdaheadbcda第第1 1步步: :建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入到头结点之后插入到头

10、结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后第13页/共46页（2）尾插法先声明一个头结点Head，为其配置空间；令Head-Next =NULL。 （空头结点，便于链表的插入和删除操作。）每输入一笔数据就声明一个新结点New，为其配置空间；为新结点数据域赋值，令New-Next = NULL； 将新结点链接到链表尾结点之后；令尾结点为New 。教材p39p39、p40p40第14页/共46页bcdai=0 i=1 i=2 i=3head头结点头结点a

11、dcbb采用尾插法建立单链表的过程采用尾插法建立单链表的过程第15页/共46页3 3、单链表的释放链式结构使用结束须向系统释放使用的空间，以节省内存空间，保持内存配置的动态特性。单链表的释放就是将结点逐个释放。 释放内存空间需调用free函数，声明格式如下： free(变量名称) 如上例 free(New) 单链表释放步骤：先将工作指针指向第一个结点，将当前结点释放后，再将工作指针指向其下一个结点。重复该步骤直至工作指针指向NULL。 教材p41 DestroyList(L) 【例】Void ClearList(LinkList &L) / 初始条件：线性表L已存在。操作结果：将L重置

12、为空表 。 LinkList *p; while(L) / L不空 p=L; / p指向首元结点 L=L-next; / L指向第2个结点(新首元结点) free(p); / 释放首元结点 16. 第16页/共46页4 4、单链表的基本操作定义好单链表结构，基于该结构通常定义如下一组基本操作：（1）初始化单链表InitList(L) 建立一个空头结点。算法时间复杂度O(1)。（2）销毁单链表DestoryList(L) 即释放单链表L。算法时间复杂度O(n)。（3）判断单链表是否为空ListEmpty(L) 返回值为1或0。算法时间复杂度O(1)。（4）求取单链表长度ListLength(L)

13、 即返回单链表的结点个数，作为链表长度。算法时间复杂度O(n)。（5）输出单链表DispList(L) 从首结点起，将结点数据域纸打印在标准输出。算法时间复杂度O(n)。（6）从单链表中取得指定结点的数据元GetElem(L,i,e) 从首结点起，找到指定的第i个结点，并取出数据值赋给变量e。属于线性查找，算法时间复杂度O(n)。第17页/共46页（7）从单链表中查找指定数据元的结点LocateElem(L,e) 从首结点起，找到关键字值为e的结点，并返回结点位置（第i个）。属于线性查找，算法时间复杂度O(L-length)或O(n)。（8）在单链表中插入结点ListInsert(L,i,e)

14、 令e成为链表中第i个结点。从首结点起，找到第i-1个结点，并将数据元为e的新结点插入其后。 插入位置i: 1iListLength(L)+1 该算法查找结点属于线性查找，算法时间复杂度O(n)。（9）从单链表中取得指定结点的数据元GetElem(L,i,e) 从首结点起，找到指定的第i个结点，取出数据值赋给变量e保留，而后删除结点i。属于线性查找，算法时间复杂度O(n)。两种常规操作：在单链表中插入结点操作和删除结点操作 第18页/共46页 插入结点运算 插入运算是将值为x的新结点插入到单链表的第i个结点的位置上。先在单链表中找到第i-1个结点,再在其后插入新结点。 单链表插入结点的过程如下

15、图所示。第19页/共46页插入结点示意图第20页/共46页 删除结点运算 删除运算是将单链表的第i个结点删去。先在单链表中找到第i-1个结点,再删除其后的结点。 删除单链表结点的过程如下图所示。第21页/共46页删除结点示意图第22页/共46页5 5、单链表的应用单链表在系统设计中应用十分广泛，是实现链式存储的最基础的数据结构。单链表的三项基本操作：定位（查找结点）、插入结点、删除结点。定位操作的时间复杂度为O（n）；插入与删除结点算法的时间复杂度均为O（1）。 下面讨论几个基于单链表的典型操作：（1）单链表的反转 把单链表的指针从头至尾反转方向，原先的头结点作为尾结点，指针指向NULL，逐个

16、反转指针方向，原先的尾结点变为头结点。 设计思路：可分三种情况首结点的指针反转；中间结点的指针反转；尾结点的指针反转。具体方法：需要设置三个指针 Back、pointer、Next。以pointer为当前结点（也是行走结点）。 第23页/共46页步骤一： 先将Back指向首结点；Pointer指向第二个结点；反转首结点（Back）的指针，指向NULL。 Back=Head; Pointer=Back-Next Back-Next=NULL 然后定义Next结点为第三个结点；将第二个结点Pointer指针反转；将Back结点后移一位；将Pointer结点也后移一位。（红色） Next= Poin

17、ter- Next; Pointer- Next=Back; Back=Pointer; Pointer=Netx;BackPointerHeadNull Back NextPointer第24页/共46页步骤二： 经过步骤一后图示如下： 此时，Back、Pointer、Next均为中间结点。 从设立Next结点开始，重复第二种情况，逐个反转Pointer所指向的结点（当前结点）指针，直到Pointer结点的指针指向NULL为止。步骤三： 反转尾结点的指针，并令尾结点为首结点。 Pointer-Next=Back; Head=Pointer; 总结：1）总是在反转某个结点指针之前定义好其下一个

18、结点的指针 2）每一步均完成对Pointer 结点的反转 3）Next比Back、Pointer滞后一步定义，作为后半截链表首节点NullBackPointerNext第25页/共46页Link Invert_List (Link Head) Link pointer; Link Back; Link next; Back=Head; Pointer=Back-Next； Back-Next=NULL； /*反转首结点*/ While(Pointer- Next!=NULL) Next= Pointer- Next; Pointer- Next=Back; Back=Pointer; Poin

19、ter=Netx; /*反转中间结点*/ Pointer-Next=Back; Head=Pointer; return Head; /*反转尾结点*/第26页/共46页 【例】 设C=a1,b1,a2,b2,an,bn为一线性表,采用带头结点的hchc单链表存放,编写一个算法,将其拆分为两个线性表,使得: A=a1,a2,an,B=b1,b2,bn 解: 设拆分后的两个线性表都用带头结点的单链表存放。 先建立两个头结点*ha和*hb,它们用于存放拆分后的线性表A和B。ra和rb分别指向这两个单链表的表尾,用p指针扫描单链表hc,将当前结点*p链到ha未尾,p沿next域下移一个结点,若不为空

20、,则当前结点*p链到hb未尾,p沿next域下移一个结点,如此这样,直到p为空。最后将两个尾结点的next域置空。 对应算法如下:第27页/共46页 void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的头结点利用的头结点利用hc的头结点的头结点*/ ra=ha; /*ra始终指向始终指向ha的末尾结点的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList); /*创建创建hb头结点头结点*/ rb=hb; /

21、*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域置空域置空*/第28页/共46页 【例】 有一个带头结点的单链表head,其ElemType类型为char,设计一个算法使其元素递增有序。 解:若原单链表中有一个或以上的数据结点,先构造只含一个数据结点

22、的有序表(只含一个数据结点的单链表一定是有序表)。扫描原单链表余下的结点*p(当前结点，行走直到p=NULL为止),在有序表中通过比较找到插入*p的前驱结点*q,然后将*p插入到*q之后(这里实际上采用的是直接插入排序方法)。第29页/共46页 void Sort(LinkList *&head) LinkList *p=head-next,*q,*r; /p指向首个数据结点/if (p!=NULL) /head有一个或以上的数据结点/ r=p-next; /r保存p结点后继结点的指针/ p-next=NULL; /构造只含一个数据结点的有序表,头结点仍为head/ p=r; whil

23、e (p!=NULL) r=p-next; /r保存p结点后继结点的指针/ q=head; while (q-next!=NULL & q-next-datadata) q=q-next; /在有序表中寻找插入*p的前驱结点*q/ p-next=q-next;/将*p插入到*q之后/ q-next=p; p=r; /扫描原单链表余下的结点/ 第30页/共46页二、双链表单链表的结点中只有一个指向其直接后继的指针。由此，从某个结点出发只能顺着指针方向向后寻找其它的结点。若要寻找某个结点的直接前趋，仍需要从首结点出发，找到那个直接后继为该结点的结点。为了克服单链表这种单向性的缺点，我们可以

24、使用双向链表。顾名思义，在双向链表中有两个指针域，一个指向结点的直接前趋；另一个指向结点的直接后继。1、双向链表的建立对于双链表，采用类似于单链表的类型定义，其DLinkList类型的定义如下： typedef struct DNode /*定义双链表结点类型*/ ElemType data; struct DNode *prior; /*指向前驱结点*/ struct DNode *next; /*指向后继结点*/ DLinkList; /*定义双链表*/第31页/共46页双链表的内存定位，仍可由首结点或尾结点确定。我们可根据通常在哪一端操作确定来保留定位结点，当然也可以保留首尾两个结点。双

25、链表建立： 如上图三个结点 ( node1-back=NULL; ) node1-next=node2; node2-back=node1; node2-next=node3; node3-bake=node2; ( node3-next=NULL; )编制具体算法时 ，仍可如单链表一样采用头插法和尾插法实现。教材p44-45 node1 node3 node2第32页/共46页3、双链表的基本操作在双链表中,有些操作如求长度、取元素值、查找元素、输出和释放链表等操作算法与单链表中相应算法是相同的。双链表插入和删除与单链表有较大差别。单链表中,进行结点插入和删除时涉及到前后结点的一个指针域的变

26、化。双链表中,结点的插入和删除操作涉及到前后结点的两个指针域的变化。（1）在双链表中插入结点 在双链表中p所指的结点之后插入一个s结点，其操作语句描述为: s-next=p-next; /*将s插入到p之后*/ s-prior=p; p-next-prior=s; 仍需注意链表断裂问题！ p-next=s; 插入结点操作算法的时间复杂度为O O(n)(n)【例】在双链表中插入元素算法 教材p45第33页/共46页双链表中插入结点示意图第34页/共46页（1）在双链表中删除结点 删除双链表L中*p结点的后续结点。其操作语句描述为: p-next=q-next; q-next-prior=p; 双

27、链表中删除结点操作算法的时间复杂度为O(n)第35页/共46页三、循环链表循环链表是另一种形式的链式存储结构。特点是链表的尾指针不指向NULL，而是指向Head，整个链表形成一个环链。由此，从任意一个结点出发均可找到链表中的其它结点 。仍可设立头结点来确定整条链表的位置。因为其首尾相接的特性，有时候只需要设立一个尾指针确定链表的内存位置，并可不再设立头指针以简化操作。对当前指针在行走一遍的相关操作中，通常不再判断其是否为NULL，而是是否为Head（或空头结点L）。1、建立循环单链表 如同建立单链表算法，可使用尾插法，结点插入结束后将尾结点指针指向头结点。 教材P40尾插法算法 修改尾指针：

28、r-next=L;第36页/共46页 带头结点的循环单链表和循环双链表示意图第37页/共46页3、释放循环链表的结点方法一：如果确定了头结点的位置，则释放循环链表的结点时，通常从第二个结点开始，这是为了保存整个环链的完整性。 比如先将头结点与第三个结点链接，释放第二个，再与第四个链接，释放第三个如此依序，释放完尾结点时，头结点的指针指向自己，直接释放头结点。 如此操作，在整个释放过程中可以不必重新为系统确定整条链表的位置，头结点一直存在至最后一个才被释放。另外环链一直不会断裂，不影响其他操作。 算法实现如下： （使用pointer指针指向当前欲释放的结点：） next=head-next; /

29、*next先指向第二个结点*/ While ( next!=head) pointer=next; /*next做为行走结点，从第二个走向尾*/ next=next-next; head-next=next; /*头结点不变，并且环链不断裂*/ free(pointer); free(head);第38页/共46页方法二：先将循环链表断为单链表，再从首结点一直释放到尾结点。 将首结点做为尾结点，则第二个结点为新的首结点，然后从新的首结点一直释放到尾结点。（释放每一个首结点，所以需考虑重新定位） 实际上与上一种释放方式一样，都从原循环链表第二个开始，只是首尾指针有所变化，变成了单链表。这种方法破

30、坏了环链的特性，适合于单一的释放结点操作。 具体算法： Pointer=head-next; head Head-next=NULL; ( head ) While (pointer!=NULL) pointer pointer Head=pointer; pointer=pointer-next; free(head); 第39页/共46页【例】编写出判断带头结点的双向循环链表L是否对称相等的算法。 p从左向右扫描L，q从右向左扫描L，若对应数据结点的data域不相等，则退出循环，否则继续比较，直到p与q相等或p的下一个结点为*q为止。对应算法如下:int Equeal(DLinkList

31、*L) int same=1; DLinkList *p=L-next; /*p指向第一个数据结点*/ DLinkList *q=L-prior; /*q指向最后数据结点*/ while (same=1) if (p-data!=q-data) same=0; else if (p=q) break;/*数据结点为奇数的情况*/ q=q-prior; if (p=q) break;/*数据结点为偶数的情况*/ p=p-next; return same; 第40页/共46页四、静态链表 静态链表借用一维数组来描述线性链表。通过定义一个较大的结构体数组来作为备用结点空间(即存储池)，每个结点应至少含有两个域：data域和cursor域。 一维数组中的一个分量（元素）表示一个结点，使用游标(指示器cur，即伪指针)代替指针以指示结点在数组中的相对位置。数组中的第0个分量可以看成头结点，其指针域指示静态链表的第一个结点。 这种存储结构仍然需要预先分配一个较大空间，但是在进行线性表的插入和删除操作时不需要移动元素，仅需要修改“指针”，因此仍然具有链式存储结构的主要优点。 下页图给出了一