,Click to edit Master title style,Click to edit Master text styles,第,3,章 线性表的链式存储,本章介绍线性表的另一种存储方式：链式存储。链式存储结构通过“链”建立起数据元素之间的逻辑关系。它不要求逻辑上相邻的两个数据元素物理上也相邻，也不需要用地址连续的存储单元来实现，因此在操作上使得插入和删除操作不需要移动大量的结点。本章主要讲解线性表的链式存储结构、链表的创建及它的基本运算和实现算法。,3.1,线性表的链式存储结构,线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这使得可以随机存取表中的任一结点，但也使得插入和删除操作会移动大量的数据元素，而且线性表的容量难以扩充。,下面介绍的链式存储结构具有很多优点，它可以避免插入和删除操作带来的大量结点的移动，能给结点动态分配存储空间等优点。下面介绍几种常用的链表。,3.1.1,单链表,在链式存储中，逻辑上相邻的数据元素在物理存储位置不一定也相邻。那么，怎么表示两个数据元素逻辑上的相邻关系呢？可以这样解决，把原来的数据元素结点存储信息进行扩展，每个存储结点不仅存储数据元素本身的信息，而且需要存储数据元素之间逻辑关系的信息。,3.1.1,单链表,3.1.2,循环链表,循环链表就是将单链表中的最后一个结点的,next,指针指向链表中第一个结点。链的表头和表尾相接，使整个链表构成一个环形。这样做的好处是对表的链接方式改变后，无须增加存储量，即可使得表处理更加方便灵活。,3.1.3,双向链表,在单链表结点中只有一个指向其后继结点的,next,指针域，而找其前驱则只能从该链表的头指针开始，顺着各结点的,nex,t,指针域进行,查找，也就是说找后继的时间复杂度是,O(1),，找前驱的时间复杂度是,O(n,),。如果也希望找前驱像后继那样快，则只能付出空间的代价：每个结点再加一个指向前驱的指针域,prior,，结点的结构修改为下图，这样链表中有两个方向不同的链，用这种结点组成的链表称为双向链表。,3.1.3,双向链表,3.1.4,静态链表,静态链表就是用一维数组来描述线性链表，结点中使用游标（即数组下标）指示直接后继结点在数组中的相对位置。这种描述方法便于在没有指针类型的高级程序设计语言（如,FORTRAN,）中使用链表结构。这种存储结构，虽然仍需要预先分配一个较大的空间，但在做线性表的插入和删除操作时不需移动元素，仅需修改指针，故仍具有链式存储结构的主要优点。,3.1.4,静态链表,3.2,单链表创建算法的实现,单链表的建立与顺序表的建立不同，它是一种动态管理的存储结构，链表中的每个结点占用的存储空间不是预先分配，而是运行时系统根据需求而动态生成的。单链表的建立分为在头部插入结点建立单链表和在尾部插入结点建立单链表（分别简称为头插法和尾插法）。下面分别介绍两种创建算法的实现过程。,3.2.1,头插法单链表的创建实现,用头插法实现单链表的创建是从一个空表开始重复读入数据，每读入一个数据元素则申请一个结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。因为是在链表的头部插入，读入数据的顺序和链表中的逻辑顺序是相反的。,1,字符型单链表算法,2,整数型单链表算法,3,不带头结点的单链表算法,3.2.2,尾插法单链表的创建实现,用头插法实现单链表的创建，比较简单，但读入的数据元素的顺序与生成的链表中元素的顺序是相反的。若希望两者次序一致，则用尾插法创建单链表。为了快速找到新结点插入到链表的尾部位置，所以需加入一个尾指针,r,用来始终指向链表中的尾结点。初始状态：头指针,L,和尾指针,r,均为空，把各数据元素按顺序依次读入，申请结点，将新结点插入到,r,所指结点的后面，然后,r,指向新结点，直到读入结束标志为止。,3.2.2,尾插法单链表的创建实现,3.3,单链表运算的实现,单链表建立之后，如果要进行一些如查找、插入、删除等操作该如何实现？所以还须掌握一些单链表的各种算法，来实现这些操作。单链表的运算和顺序表类似，比较多。它的运算包括链表初始化、判表空、清空辅助运算和求表长、查找、插入和删除基本运算。下面分别介绍各运算的算法的实现过程。,3.3.1,单链表辅助运算的实现,单链表辅助运算主要是指在对单链表进行插入、删除和查找等操作时的执行条件或准备工作的检查和判断。具体分为链表初始化、判表空、清空三个操作。,1,初始化链表,L,2,清空链表,L,3,判链表,L,是否为空,3.3.2,单链表求表长的实现,求单链表的长度与顺序表不同，顺序表可以通过保存表的实际长度,length,的值直接求得；而单链表需要从第一个结点开始，一个一个结点进行遍历，直到表的末尾。下面对单链表是否带头结点分别介绍实现算法。,1,带头结点的单链表,2,不带头结点的单链表,3.3.3,单链表插入操作的实现,单链表的插入操作是指在表的第,i,个位置结点处插入一个值为,data,的新结点。插入操作需要从单链表的第一个结点开始遍历，直到找到第,i,个位置的结点。插入操作分为在结点之前插入的前插操作和在结点之后插入的后插操作。,1,前插操作,2,后插操作,3.3.3,单链表插入操作的实现,3.3.4,单链表删除操作的实现,单链表的删除操作是指删除第,i,个结点。通过改变待删除结点的前驱结点指针，让它直接指向待删除结点的后继就可以实现删除操作。删除操作和插入操作相同的是需要从开始结点进行遍历，直到找到第,i,个位置的结点。如果删除的是第一个结点，情况有所不同，需要把该结点的直接后继结点的地址赋给头指针。对于其它结点，需要保存被遍历到的结点的直接前驱，找到第,i,个结点后，把该结点的直接后继作为它的直接前驱的直接后继。,3.3.4,单链表删除操作的实现,3.3.5,单链表查找操作的实现,单链表查找分为按照序号查找和按照值查找两种。按值查找是指在表中查找其值满足给定值的结点，它是从开始结点进行遍历，将被遍历到的结点的值与给定值比较，如果相等，则返回在单链表中首次出现与给定值相等的数据元素的序号；否则，返回一个特殊值表示查找失败。按序号查找比较简单，实际上就是与序号对应相同的元素的值。,1,按序号查找,2,按值查找,3.4,双向链表基本运算的实现,在双向链表中，除插入、删除操作差别较大外，其它基本运算均与单链表相同。所以在讨论其基本运算时，只讨论双向链表插入、删除操作实现的过程。由于双向链表其特有的存储结构，这两个操作相对比较复杂，读者在学习时要理解插入、删除操作实现过程，并与单链表的插入、删除操作对比，找出相同和不同的地方。,3.4.1,双向链表插入操作的实现,双向链表插入操作是在链表的第,i,个元素前插入一个结点。设,p,指向双向链表中某结点，,s,指向待插入的值为,x,的新结点，将,s,插入到,p,的前面。,3.4.2,双向链表删除操作的实现,双向链表删除操作实现相对比较简单。在双向链表中删除一个结点时，用指针,p,指向该结点，然后将,p,结点的直接前驱结点的,next,指向,p,结点的下一个结点，再将,p,的直接后继结点的,prior,指向,p,的直接前驱结点。,3.5,顺序表与链表的比较,顺序存储有三个优点：,实现方法简单，各种高级语言中都有数组，容易实现。,不用为表示结点间的逻辑关系而增加额外的存储开销。,顺序表具有按元素序号随机访问的特点。,但它也有两个缺点：,在顺序表中做插入删除操作时，平均移动大约表中一半的元 素，因此对表长较大的顺序表效率低。,需要预先分配足够大的存储空间，且大小不容易确定。,3.6,链表的典型例题,本节将介绍链表相关的典型例题。由于链表存储结构相对于顺序表比较复杂，特别是涉及指针的操作，所以这部分例题读者理解起来感觉也困难些。,3.7,算法设计实训,前面讨论了线性表的链式存储结构表示的操作实例，本节主要介绍链式存储结构的上机实训。通过对算法设计的学习，可以理解线性表在链式存储结构下的操作方法，掌握链式存储结构的常见算法。下面介绍采用链式存储结构实现的约瑟夫（,Joseph,）问题实例的详细设计过程。,3.7.1,需求分析,约瑟夫（,Joseph,）问题：编号为,1,，,2,，,，,n,的,n,个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值,m,，然后，从第一个人开始按顺时针方向自,1,开始顺序报数，报到,m,的人离开桌旁，并将他手中的密码作为新的,m,值，从顺时针方向的下一个就坐在桌旁的人开始重新从,1,报数，如此下去，直至所有人全部离开桌旁为止。,3.7.1,需求分析,3.7.2,约瑟夫问题的数据结构,假设有,7,个人，编号从,1,到,7,，他们手中的密码分别是,3,，,1,，,7,，,2,，,4,，,8,，,4,，最初的,m=2,，通过报数，这,7,个人离开桌旁的顺序应该是：,2,，,3,，,5,，,4,，,7,，,6,，,1,。这个问题的对象是,n,个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。,编号,密码,在桌旁的状态,1,3,1,2,1,1,3,7,1,4,2,1,5,4,1,6,8,1,7,4,1,3.7.3,约瑟夫问题的算法实现,根据给出的数据结构，建立一个具有无头结点、有,n,个链结点的循环链表。确定第,1,个报数人的位置，不断地从链表中删除链结点，直到链表为空。,3.8,本章小结,本章介绍线性表的另一种存储：链式存储。链式存储结构不要求逻辑上相邻的两个数据元素物理上也相邻，也不需要用地址连续的存储单元来实现。因此在操作上，它也使得插入和删除操作不需要移动大量的结点。线性表的链式存储结构主要介绍了单链表、循环链表、双向链表和静态链表四种类型，讨论了各种链表的基本运算和实现算法。,