数据结构与算法基础课件章节2

第2章线性表2.1线性表的定义

线性表（linearlist）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列，线性表中数据元素之间的关系是一对一的关系。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。

在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。

线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。

线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱。我们可以根据定义得出线性表有以下的特点：表中元素的个数有限。表中元素具有逻辑上的顺序性，表中元素有其先后次序。表中元素都是数据元素，每个元素都是单个元素。表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。2.2顺序表的定义和基本操作的实现2.2.1顺序表的定义采用顺序存储结构的线性表通常称为顺序表。顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，故顺序表表中元素的逻辑顺序和其物理顺序相同。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。第1个元素存储在线性表的起始位置，第i个元素的存储位置后面紧接着存储的是第i+1个元素。假设顺序表L存储的起始位置为LOC(A)，SIZE为每个数据元素所占用存储空间的大小，则顺序表L所对应的顺序存储如图所示。顺序表最主要的特点是随机访问，即通过元素序号可在时间O(1)内找到指定的元素。顺序表的存储密度高，每个结点只存储数据元素。顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素，故顺序表的插入或删除元素时效率会比较低。2.2.2顺序表上基本操作的实现顺序表有插入、删除、查找等基本操作。1．按索引位置插入操作要在顺序表L的第i（1≤i≤L.length+1）个位置插入新元素e，需要输入的参数分别为待插入的索引位置（0≤pos≤L.length，索引是从0开始）和待插入的元素。若pos的输入不合法，则抛出异常，表示插入失败；否则将顺序表的第pos个元素及其后的所有元素后移一个位置，腾出一个空位置插入新元素e，如图所示。此时顺序表的长度会增加1，该插入操作成功。

2．按索引删除操作

要在顺序表L的第i（1≤i

≤L.length）个位置删除一个元素e，需要输入的参数为待删除的元素索引位置（0≤pos＜L.length）。若pos的输入不合法，则抛出异常，表示插入失败；否则将顺序表中的该元素其后的所有元素前移一个位置，删除原先的元素，如图所示。此时顺序表的长度减1，该删除操作成功。

2.3链表的定义和基本操作的实现2.3.1链表的定义链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表允许插入和移除表上任意位置上的结点，但是不允许随机存取。链表查找某个特定结点时，必须要从头开始找起，十分麻烦。链表有很多种不同的类型：单向链表，双向链表以及循环链表。单链表结构如图所示，其中data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。

通常用头指针来标识一个单链表，比如有一个单链表L，头指针为NULL时即表示L是一个空表。除此之外，为了便于对链表的操作，会在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长信息等信息。头结点的指针域指向线性表的第一个元素结点，如图所示。引入头结点，有以下两个优点：

1）第一个数据结点会被存放在头结点的指针域中，所以在处理链表第一个结点时，其操作和在表中其他位置的操作一致，无需特殊处理。比如在第一个位置插入新结点，没有头结点的链表需要先将原链表第一个结点作为新结点的指向结点，并且将新结点作为新的表头指针；而有头结点的链表只需将该新结点插入到头结点之后即可，不需要更新表头指针，与基本的插入操作无异。

2）无论链表是否为空，其头指针都是指向头结点的非空指针，这样子空表和非空表的处理就得到了统一。2.3.2单链表上基本操作的实现1．使用头插法建立单链表该方法从一个空表开始，生产新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即空白头结点之后，如图所示。当采用头插法来建立单链表时，单链表中元素的顺序和读入数据的顺序是相反的。在链表中，每个结点插入的时间为O(1)，设单链表的长度为n，则头插法的总时间复杂度为O(n)。

可以试着思考一下，如果使用头插法建立没有头结点的单链表，代码会有怎样的变化？与带头结点的单链表相比，哪一个更易于使用，更易于理解？2．使用尾插法建立单链表使用头插法建立的单链表中结点次序和输入数据的顺序不一致，若希望两者次序一致，可采用尾插法。尾插法是将新结点插入到当前链表的表尾，为此必须增加一个尾指针rear，使其始终指向当前链表的尾结点。尾插法建立单链表的算法如下：与头插法相比，增加了一个指向表尾结点的指针，故尾插法的时间复杂度与头插法相同。3．按值查找表结点从单链表的第一个结点出发，顺着指针next逐个往下比较各结点数据域的值，若某结点数据域的值等于给定值e，则返回该结点的位序，否则返回-1。

按值查找表结点的算法如下：

在查找过程中，最坏需要遍历整个链表，故按值查找操作的时间复杂度为O(n)。4．按位序查找表结点从单链表的第一个结点出发，顺着指针next逐个往下查找到第i个（0≤i＜n，n为链表长度）结点，若输入i合法，则返回该结点的数据域，否则返回None。按位序查找表结点的算法如下：5．插入结点操作插入结点操作将值为x的新结点插入到单链表的第i个位置上。首先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第i–1个结点，再在其后面插入新结点，如图所示。假设结点p为待插入的新结点，实现插入结点操作的代码片段如下：在该算法中，需要注意的是步骤1必须要在步骤2之前，如果先执行步骤2，将前驱结点的指针指向新结点s，那么原来结点p后面的结点都找不到了，无法再获取到后面的那些结点，故要注意链表的执行步骤顺序。该算法的主要时间开销在于去寻找第i-1个元素，故插入结点操作的时间复杂度为O(n)。但如果在给定的结点后面插入一个结点，那么此时的时间复杂度仅为O(1)。6．删除结点操作删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，后查找表中第i–1个结点，即被删结点的前驱结点，再将其删除，如图所示。与插入结点操作类似，删除结点操作主要耗费在查找上，故时间复杂度为O(n)。7．求表长操作求链表的长度就是统计单链表中结点的数量，需要从第一个结点开始遍历，直到遍历到最后一个结点。该过程需要设置一个计数器，每访问一个结点，计数器就加1。求表长操作的算法如下：上述方法中，该单链表是带头结点的，如果是不带头结点的单链表，在求表长的操作中会有所不同。由于求表长操作需要遍历整个单链表，故该算法的时间复杂度为O(n)。2.3.3双链表单链表只有一个指向其后继的指针，使得单链表只能从头到尾的顺序来遍历，在某些操作中会有一定的局限性。为克服单链表的局限性，故引入双链表结构。双链表也叫双向链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，如图所示。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。双链表由于增加了一个指向其前驱的prior指针，在插入和删除操作的实现上，与单链表有较大的不同。1．双链表的插入操作假设在双链表中p所指的结点之后插入结点s，其插入过程如图所示。上述代码的语句顺序不是唯一但不是任意的，不需要死记硬背。读者只要加深理解，便能写出正确的语句顺序。如果把题目改成在结点p之前插入结点s，请读者思考具体的操作步骤。双链表插入操作具体代码如下：2．双链表的删除操作假设删除在双链表中结点p的后继结点q，双链表的删除操作如图所示。删除操作的代码片段如下：删除操作的具体代码如下：2.3.4循环链表循环链表是另一种形式的链式存储结构。顾名思义，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。循环链表可分为循环单链表和循环双链表。1．循环单链表循环单链表和单链表的区别在于表中最后一个结点的指针不是NULL，而是指向头结点，从而使整个链表形成一个环，如图所示。

对于循环单链表，插入、删除操作与单链表基本一致。不同的是，由于循环单链表是一个环，因此在任何一个位置上的插入和删除操作都是等价的，无须判断结点是否为表尾。在循环单链表L中，若循环单链表L为空，则L.next==L；若结点p为尾结点，则p.next=L。2．循环双链表与循环单链表类似，在循环双链表中，头结点的prior指针还要指向表尾结点。在循环双链表L中，若循环双链表L为空，则L.prior==L，L.next==L；若结点p为尾结点，则p.next==L。小结（1）线性表是n个具有相同特性的数据元素的有限序列，线性表中数据元素之间的关系