数据结构与算法之线性表前言线性表

前言

上一篇《数据结构和算法之时间复杂度和空间复杂度》中介绍了时间复杂度的概念和常见的时间复杂度，并分别举例子进行了一一说明。这一篇主要介绍线性表。 线性表属于数据结构中逻辑结构中的线性结构。回忆一下，数据结构分为物理结构和逻辑结构，逻辑结构分为线性结构、几何结构、树形结构和图形结构四大结构。其中，线性表就属于线性结构。剩余的三大逻辑结构今后会一一介绍。

线性表

基本概念

线性表（List）：由零个或多个数据元素组成的有限序列。 注意： 1.线性表是一个序列。 2.0个元素构成的线性表是空表。 3.线性表中的第一个元素无前驱，最后一个元素无后继，其他元素有且只有一个前驱和后继。 4.线性表是有长度的，其长度就是元素个数，且线性表的元素个数是有限的，也就是说，线性表的长度是有限的。 如果用数学语言来进行定义，可如下： 若将线性表记为（a1,…,ai-1,ai,ai+1,…an）,则表中ai-1领先于ai,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。

线性表的定义

线性表基本操作

InitList(L): 初始化操作，建立一个空的线性表L。 ListEmpty(L): 判断线性表是否为空表，若线性表为空，返回true，否则返回false。 ClearList(L): 将线性表清空。 GetElem(L,i,e): 将线性表L中的第i个位置元素值返回给e。 LocateElem(L,e): 在线性表L中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。 ListInsert(L,i,e): 在线性表L中第i个位置插入新元素e。 ListDelete(L,i,e): 删除线性表L中第i个位置元素，并用e返回其值。 ListLength(L): 返回线性表L的元素个数。

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的。 对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

两种不同的线性表

我们知道，数据结构分为逻辑结构和物理结构，逻辑结构分为集合结构、线性结构、树形结构和图形结构四大类。物理结构分为顺序存储结构和链式存储结构。我在之前写的《数据结构和算法》中已经介绍过。 线性表是线性结构的一种，那么线性表当然也有物理结构，也就是说，线性表有两种，分别是顺序结构的线性表（叫做顺序表）和链式结构的线性表（叫做链表）。

1.顺序存储结构的线性表

顺序表是指顺序存储结构的线性表，指的是用一段地址连续的存储单元依次存储线性表的数据元素。 顺序表表现在物理内存中，也就是物理上的存储方式，事实上就是在内存中找个初始地址，然后通过占位的形式，把一定的内存空间给占了，然后把相同数据类型的数据元素依次放在这块空地中。注意，这块物理内存的地址空间是连续的。 举 个例子，比如C语言中的基本变量的存储就是连续的存储在内存中的，比如声明一个整数i，在64位系统中整数i在内存中占8字节，那么系统就会在内存中为这 个整型变量分配一个长度为8个字节的连续的地址空间，然后把这个i的二进制形式从高地址向低地址存储，长度不足时候，最高位用0补齐。

顺序表的结构体定义

#define MAXSIZE 20  // 顺序表的最大存储容量
typedef int ElemType; // 顺序表存储的数据类型 
typedef struct
{ 
    ElemType data[MAXSIZE]; // 用数组表示顺序表 
    int length; // 线性表当前长度
} SqList;

通过上面用结构体定义顺序表，我们可以看出顺序表的封装需要三个属性： 1.存储空间的起始位置。数组data的存储位置就是线性表存储空间的存储位置 2.线性表的最大存储容量。数组长度MAXSIZE 3.线性表的当前长度。length 注意：数组的长度与线性表的当前长度是不一样的。数组的长度是存放线性表的存储空间的总长度，一般初始化后不变。而线性表的当前长度是线性表中元素的个数，是会改变的。

顺序表查找元素操作

代码实现：

顺序表插入元素操作

思路如下：

1.如果插入位置不合理，抛出异常；

2.如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量；

3.从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；

4.将要插入元素填入位置i处； 5.线性表长+1。 代码实现：

顺序表删除元素操作

思路如下： 1.如果删除元素的位置不合理，抛出异常。比如用户删除第0个位置的元素（线性表是从1开始的）、删除元素的位置大于线性表的长度也要抛出异常。 2.删除第i个位置的元素。 3.把第i个位置的元素后面的所有的元素的位置加一。 4.线性表长度减一。 代码实现：

顺序表优缺点

由以上代码可以看出： 线性表的顺序存储结构，在存、读取数据时，不管是在哪个位置，时间复杂度都是O(1)。而在插入或者删除时，时间复杂度都是O(n)。 这也就是线性表的顺序存储结构比较适合存取数据，不适合经常插入和删除数据的应用。

优点：

1.无需为了表示表中元素之间的逻辑关系而增加额外的存储空间（相对于链式存储而言）。 2.可以快速的存取表中任意位置的元素。

缺点：

1.插入和删除操作需要移动大量的元素。 2.当线性表长度变化较大时，难以确定存储空间的容量。 3.容易造成存储空间的“碎片”(因为线性表的顺序存储结构申请的内存空间都以连续的，如果因为某些操作（比如删除操作）导致某个部分出现了一小块的不连续内存空间，因为这一小块内存空间太小不能够再次被利用/分配，那么就造成了内存浪费，也就是“碎片”) PS：windows系统有磁盘碎片整理工具，而Linux系统没有，因为Linux系统内核优化的很好，几乎是没有磁盘碎片的。

2.链式存储结构的线性表

前面我们讲的线性表的顺序存储结构，它最大的缺点就是插入和删除时需要移动大量元素，这显然就需要耗费时间。 那我们能不能针对这个缺陷或者说遗憾提出解决的方法呢？要解决这个问题，我们就得考虑一下导致这个问题的原因！ 为什么当插入和删除时，就要移动大量的元素？ 原因就在于相邻两元素的存储位置也具有邻居关系，它们在内存中的位置是紧挨着的，中间没有间隙，当然就无法快速插入和删除。 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。 也就是说，链式存储结构的线性表由一个（可以使零）或者多个结点（Node）组成。每个节点内部又分为数据域和指针域（链）。数据域存储了数据元素的信息。指针域存储了当前结点指向的直接后继的指针地址。 因为每个结点只包含一个指针域，所以叫做单链表。顾名思义，当然还有双链表。

单链表

链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址（指针）。 也就是说除了存储其本身的信息外，还需存储一个指示其直接后继的存储位置的信息。 我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。

指针域中存储的信息称为指针或链。 这两部分信息组成数据元素称为存储映像，或称为结点(Node)。 n个结点链接成一个链表，即为线性表(a1, a2, a3, …, an)的链式存储结构。

因为此链表的每个结点中只包含一个指针域，所以叫做单链表。

线性表的链式存储结构

对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中的第一个结点的存储位置叫做头指针，最后一个结点指针为空(NULL)。 单链表是线性表中最具代表性的一种，下一篇文章中，本人将会拿出一章来介绍单链表，敬请期待！ 图片来源参考自:鱼C工作室。感谢鱼C工作室贡献出了这么好的图片。