线性表的定义和基本操作

线性表是具有相同数据类型的$n$个数据元素的有限序列，其中$n$为表长，当$n=0$时线性表是一个空表。若用$L$命名线性表，则其一般表示为

式中，$a_1$是唯一的“第一个“数据元素，又称表头元素；$a_n$是唯一的“最后一个“数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。数据元素的位序从$1$开始，数组下标从$0$开始。

线性表的特点如下：

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下：

• $InitList~(\&L)$：初始化表。构造一个空的线性表。

• $DestroyList~(\&L)$：销毁操作。销毁线性表，并释放线性表$L$所占用的内存空间。

   

• $ListInsert~(\&L,i,e)$：插入操作。在表$L$中的第$i$个位置上插入指定元素$e$。

• $ListDelete~(\&L,i,\&e)$：删除操作。删除表$L$中第$i$个位置的元素，并用$e$返回删除元素的值。

   

• $LocateElem~(L,e)$：按值查找操作。在表$L$中查找具有给定关键字值的元紊。

• $GetElem~(L,i)$：按位查找操作。获取表$L$中第$i$个位置的元素的值。

   

• $Length~(L)$：求表长。返回线性表$L$的长度，即$L$中数据元素的个数。

• $PrintList~(L)$：输出操作。按前后顺序输出线性表$L$的所有元素值。

• $Empty~(L)$：判空操作。若$L$为空表，则返回$true$，否则返回$false$。

基本操作的实现取决于采用哪种存储结构，存储结构不同，算法的实现也不同。

线性表的顺序表示(顺序表)

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第$1$个元素存储在线性表的起始位置，第$i$个元素的存储位置后面紧接着存储的是第$i+1$个元素，称$i$为元素$a_i$在线性表中的位序。线性表中元素的位序是从$1$开始的。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。

常用数组来描述线性表的顺序存储结构。一维数组可以是静态分配的，也可以是动态分配的。

• 在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。
• 在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的，而不需要为线性表一次性地划分所有空间。动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化。

顺序表的特点：

• 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数，线性表中的任一数据元素都可以随机存取(通过首地址和元素序号可在时间$O(1)$内找到指定的元素)，所以线性表的顺序存储结构是一种随机存取的存储结构。
• 顺序表的存储密度高，每个结点只存储数据元素。
• 顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。拓展容量不方便。

顺序表的插入：在顺序表$L$的第$i$个位置插入新元素$e$。若$i$的输入不合法，则返回$false$，表示插入失败；否则，将第$i$个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素$e$，顺序表长度增加$1$，插入成功，返回$true$。

• 最好情况：在表尾插入，时间复杂度为$O(1)$。
• 最坏情况：在表头插入，时间复杂度为$O(n)$。
• 平均情况：所需移动结点的平均次数为$\Large\frac{n}{2}$，时间复杂度为$O(n)$。

顺序表的删除：删除顺序表$L$中第$i$个位置的元素，用引用变量$e$返回。若$i$的输入不合法，则返回$false$；否则，将被删元素赋给引用变量$e$，并将第$i+1$个元素及其后的所有元素依次往前移动一个位置，返回$true$。

• 最好情况：删除表尾元素，时间复杂度为$O(1)$。
• 最坏情况：删除表头元素，时间复杂度为$O(n)$。
• 平均情况：所需移动结点的平均次数为$\Large\frac{n-1}{2}$，时间复杂度为$O(n)$。

顺序表的查找：如果是按位查找的话，直接将位序减一作为数组下标进行随机存取，无论好坏，时间复杂度均为$O(1)$；如果是按值查找的话，用循环语句从表头到表尾，在顺序表$L$中查找第一个元素值等于$e$的元素，并返回其位序。

• 最好情况：查找的元素就在表头，时间复杂度为$O(1)$。
• 最坏情况：查找的元素在表尾(或不存在)，时间复杂度为$O(n)$。
• 平均情况：所需比较元素的平均次数为$\Large\frac{n+1}{2}$，时间复杂度为$O(n)$。

线性表的链式表示

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立起数据元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

单链表

线性表的链式存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针$next$。

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但单链表附加指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构，即不能直接找到表中某个特定的结点。查找某个特定的结点时，需要从表头开始遍历，依次查找。

通常用头指针来标识一个单链表，头指针为$NULL$时表示一个空表。为了操作上的方便，在单链表第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。

引入头结点后，可以带来两个优点：

• 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
• 无论链表是否为空，其头指针都指向头结点的非空指针(空表中头结点的指针域为空)，因此空表和非空表的处理也就得到了统一。

单链表的插入：将值为$x$的新结点插入到单链表的第$i$个位置上。先检查插入位置的合法性，然后找到待插入位置的前驱结点，即第$i-1$个结点，再在其后插入新结点。本算法主要的时间开销在于查找第$i-1$个元素，时间复杂度为$O(n)$。

如果采用不带头节点的方式，需要特殊考虑第一个节点。如果在第一个节点处插入，需要修改头指针。

后插：若在给定的结点后面插入新结点，则时间复杂度仅为$O(1)$。

前插：在某结点$p$的前面插入一个新结点，因为只有后继指针，无法直接得到该结点$p$的前驱节点，因此有两种方法：

• 先按值查找到$p$结点的前驱结点，然后使用后插的方式插入新结点，则时间复杂度为$O(n)$。
• 采用后插的方式将新结点插入到$p$结点的后面，然后交换两个结点的数据部分，则时间复杂度仅为$O(1)$。

单链表的删除：将单链表的第$i$个结点删除。该算法的主要时间也耗费在查找操作上，时间复杂度为$O(n)$。

• 查找后删除：先检查删除位置的合法性，后查找表中第$i-1$个结点，即被删结点的前驱结点，再将第$i$个删除，时间复杂度为$O(n)$。
• 复制后删除：若给出了要删除的结点$p$，可以将$p$的后继结点的值赋予其自身，然后删除$p$的后继结点，能使得时间复杂度为$O(1)$。

删除操作为将被删结点的前驱结点的指针域$next$，指向被删结点的后继结点，即让指针链跳过被删结点。然后释放被删结点的资源。

单链表的查找：

• 按位序查找：在单链表中从第一个结点出发，顺指针$next$域逐个往下搜索，直到找到第$i$个结点为止，否则返回最后一个结点指针域$NULL$。时间复杂度为$O(n)$。
• 按值查找：从单链表的第一个结点开始，由前往后依次比较表中各结点数据域的值，若某结点数据域的值等于给定值$e$，则返回该结点的指针；若整个单链表中没有这样的结点，则返回$NULL$。时间复杂度为$O(n)$。

求表长：计算单链表中数据结点(不含头结点)的个数，需要从第一个结点开始顺序依次访问表中的每个结点，为此需要设置一个计数器变量，每访问一个结点，计数器加$1$，直到访问到空结点为止。算法的时间复杂度为$O(n)$。

单链表的长度是不包括头结点的，因此不带头结点和带头结点的单链表在求表长操作上会略有不同。对不带头结点的单链表，当表为空时，要单独处理。

单链表的建立：核心就是初始化操作、指定结点的后插操作。

• 头插法：该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。采用头插法建立单链表时，读入数据的顺序与生成的链表中的元素的顺序是相反的。每个结点插入的时间为$O(1)$，设单链表长为$n$，则采用头插法建立单链表时的总时间复杂度为$O(n)$。

  头插法可以实现链表的逆置。

• 尾插法：该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针$r$，使其始终指向当前链表的尾结点。因为附设了一个指向表尾结点的指针，故时间复杂度和头插法的相同。

  如果没有尾指针$r$的话，每次插入都需要查找尾结点，建立单链表的时间复杂度为$O(n^2)$。

双链表

双链表结点中有两个指针：前驱结点$prior$和后继结点$next$。双链表在单链表的结点中增加了一个指向其前驱的$prior$指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有着较大的不同。这是因为“链“变化时也需要对$prior$指针做出修改，其关键是保证在修改的过程中不断链。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除操作的时间复杂度仅为$O(1)$(给定结点的情况下)。

双链表不可随机存取，按位查找、按值查找操作都只能用遍历(后向遍历、前向遍历)的方式实现，时间复杂度为$O(n)$。

在进行算法设计的过程中，需要注意有无头结点，以及对头结点的考虑。对于插入删除操作，需要注意前驱后继指针修改的顺序，不能发生断链的情况。当操作链头链尾(边界)时，要注意指针为$NULL$时的情况。

循环链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是$NULL$，而改为指向头结点，从而整个链表形成一个环。在循环单链表中，表尾结点$*r$的$next$域指向$L$，故表中没有指针域为$NULL$的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针。

循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。在任何一个位置上的插入和删除操作都是等价的，无须判断是否是表尾。循环单链表可以从表中的任意一个结点开始遍历整个链表。

由循环单链表的定义不难推出循环双链表。不同的是在循环双链表中，头结点的$prior$指针还要指向表尾结点，尾结点的$next$指针还要指向表头结点$L$。当循环双链表为空表时，其头结点的$prior$域和$next$域都等于$L$。

静态链表

静态链表借助数组来描述线性表的链式存储结构，结点也有数据域$data$和指针域$next$，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址(数组下标)，又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。$0$号结点充当头结点。指针表示的是下一个元素在数组中的位置。

静态链表以$next==-1$作为其结束的标志，静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素。总体来说，静态链表没有单链表使用起来方便，但在一些不支持指针的语言中，这是一种非常巧妙的设计方法。

• 优点：增、删操作不需要大量移动元素。
• 缺点：不能随机存取，只能从头结点开始依次往后查找；容量固定不可变。

顺序表和链表的比较

使用链表的情况：

• 表长难以预估，需要扩容
• 经常要增加/删除元素

使用顺序表的情况：

• 表长可预估，不需要扩容
• 查询(搜索)操作较多